-1

Lets say I have 5 cards numbered from 1 to 5 shuffled

i.e 3,2,4,5,1

the main goal is to sort this deck of cards by a simple rule:

if some cards are consecutive, I attach them together and then I shuffle again

in this example I attach 4,5 together and shuffle the deck

Lets say that I get 1,4,5,2,3

then I will have to attach 2 to 3 and shuffle again until I get 1,2,3,4,5

once a pair or a triplet or 4cards are attached, they stay attached till the end

what is the expected number of shuffles until the deck is sorted?

(the first shuffle doesn't count)

the number is around 4,8 but I want the exact number and the maths behind it..

Improve this question
9
  • 5
    I'm voting to close this question as off-topic because it isn't on topic for this SE; it isn't about any game known. Recommend going to Mathematics.
    – Drunk Cynic
    Mar 21, 2017 at 1:02
  • you obviously hate probabilities.that's ok. but this kind of maths will help you in many of your known games
    – ZaMoC
    Mar 21, 2017 at 1:06
  • 2
    I answered, but I agree that the question really belongs on math.se and if you're going to treat someone who gave a polite suggestion with that kind of attitude it makes me less happy to have given an answer myself.
    – ConMan
    Mar 21, 2017 at 1:25
  • 1
    @Jenny_mathy No, because it is a math problem. Were it on Mathematics.se, I would.
    – Drunk Cynic
    Mar 21, 2017 at 1:50
  • 6
    No-one is saying they're unrelated, or that there's no place for your question. It's just that "Here's a mathematical problem that happens to involve cards" is a much better fit for math.SE because that's where people expect to answer mathematical questions. Sure there's overlap - probabilities of an opening hand in Dominion could probably go either way, for example - but if I had a question about, say, translating a Japanese Pokemon card into English, I'd go to the Japanese language SE because that's where the Japanese speakers hang out.
    – ConMan
    Mar 21, 2017 at 3:18

1 Answer 1

Reset to default
2

This is probably more of a thing for the Math SE, but here's my working:

"Attaching" cards is essentially reducing the size of the deck. For example, if we attach 2 and 3 together, then we are now shuffling the deck of {1, 23, 4, 5} which is a 4-card deck and which behaves exactly like the deck of {1, 2, 3, 4} with appropriate relabeling. We are "done" when we have a 1-card deck of {12345}.

So let us say that for a deck of n cards, we have a p_nk probability of shuffling and getting a k-card deck. For example, p_n1 = 1/n! (that's n factorial, or n×(n-1)×...×1) because there is exactly 1 way of shuffling the deck and getting all the cards in order, out of n! ways of arranging the deck in total.

The first few values, in fact, are (done from just listing all the possible permutations):

p_11 = 1/1
p_21 = 1/2  p_22 = 1/2
p_31 = 1/6  p_32 = 2/6  p_33 = 3/6
p_41 = 1/24 p_42 = 3/24 p_43 = 9/24 p_44 = 11/24

At this point I cheat a little and look up the Online Encyclopedia of Integer Sequences. Apparently, the numerators here are exactly those of sequence A010027, which then also gives me the values for the 5-card deck:

p_51 = 1/120 p_52 = 4/120 p_53 = 18/120 p_54 = 44/120 p_55 = 53/120

So, then, what now? Well, let's look at some simpler cases. If we start with a 1-card deck, it always takes us 0 shuffles. If we start with a 2-card deck, then there's a 1/2 chance it takes us 0 shuffles, a 1/4 chance it takes 1 shuffle (first shuffle is 21, second is 12), a 1/8 chance it takes 2, and so forth, resulting in an expected number of shuffles of 1 (because it's a geometric distribution with probability p=1/2).

For a 3-card deck, then there's a 1/6 chance it takes 0 shuffles, a 2/6 chance we wind up with a 2-card deck with an expected result of taking 1 more shuffle (for a total of 2), and a 3/6 chance we wind up with a 3-card deck again, in which case the total number of shuffles is expected to be 1 more than the expected number of shuffles for a 3-card deck to start with, which when running through the algebra means that the expected number of shuffles of a 3-card deck is 7/3 (or about 2.3).

For a 4-card deck, the equation is:

E(X_4) = E(X_1)×1/24 + (1 + E(X_2))×3/24 + (1 + E(X_3))×9/24 + (1 + E(X_4))×11/24
       = 0 + 6/24 + 30/24 + (1 + E(X_4))×11/24
13/24 E(X_4) = 47/24
E(X_4) = 47/13 = 3.6 or so

And finally, doing the same for a 5-card deck, we get

E(X_5) = 42133/871 = 4.8370, approximately

Turns out it's not a particularly pretty expression, but there it is.

Improve this answer
2
  • god!you are very good! thanx! what is the fractional number for 52 card deck?
    – ZaMoC
    Mar 21, 2017 at 1:30
  • 1
    No idea. Solving for 52 cards requires solving every value up to 51 cards, plus knowing the probabilities that shuffling a 52-card deck will give you 1, 2, 3, ..., 52 clumps. As far as I can tell there's no nice closed form for any of that, but if you look at the OEIS entry that should give you enough information to implement some kind of algorithm to find it.
    – ConMan
    Mar 21, 2017 at 1:33

Not the answer you're looking for? Browse other questions tagged .