[Guest]

Take a standard deck of 52 well-shuffled cards. Flip them over one at a time, counting Ace through King. Whenever the value you say matches the card that is revealed, put that card into the discard pile.

For example, if the first five cards I flip over are 7, 2, 10, 4, J, then I would discard both the 2 and the 4.

If you only go through the deck once (counting Ace through King four times), what is the expected number of cards in the discard pile? That is, if you repeat this experiment an infinite number of times, what is the average number of cards discarded each trial?

[Guest]

Trying to figure out a reason why

4. For each card, there is a 1/13 chance of it being the correct position...*52 cards = 4.

Lemme think more about the effect on a single card being in the correct position on all the other cards.

[Guest]

If you go through the deck an infinite number of times won't the average number of cards discarded approach 52?

[Molly Mae]

If you go through the deck an infinite number of times won't the average number of cards discarded approach 52?

The "experiment" is going through the deck only once. You're repeating the experiment and not actually repeating the process within the same experiment.

[Pickett]

I wrote a quick and dirty program that takes a deck of cards, shuffles them, and then runs through this experiment n-times...

When I ran through it, it looks like the average number of cards turned over is just a bit over 3.5...about 3.53 or so...so that's kind of interesting.

(As a note, I ran through the experiment up to 100,000 times, and the more I ran it, the closer to 3.53ish it would get...)...here's some of the data for running through the experiment 10,000 times, run 20 times (for a total of 200,000 times):

35433 / 10000 = 3.5433

35091 / 10000 = 3.5091

35391 / 10000 = 3.5391

35359 / 10000 = 3.5359

35269 / 10000 = 3.5269

35439 / 10000 = 3.5439

35315 / 10000 = 3.5315

35231 / 10000 = 3.5231

35462 / 10000 = 3.5462

35313 / 10000 = 3.5313

35303 / 10000 = 3.5303

35495 / 10000 = 3.5495

35464 / 10000 = 3.5464

35108 / 10000 = 3.5108

35481 / 10000 = 3.5481

35487 / 10000 = 3.5487

35575 / 10000 = 3.5575

35156 / 10000 = 3.5156

35314 / 10000 = 3.5314

35478 / 10000 = 3.5478

FINAL TOTAL AVERAGE: 3.5358199999999997

Edited October 12, 2011 by Pickett

[Guest]

i too would think 1/13 chance, and therefore 4 should be the average.

however, the draws are not independent.

on the first draw you have a 4/52 chance. on the second draw, you have one fewer card for the experiment, right or wrong.

therefore you have something slightly less than 4/52 for the second card. and so on.

so, i think it would be...

# of ways each card can be in correct position/ # of ways deck can be arranged

the denominator is easy, 52!.

the numerator, I'm not sure. each card can be in a correct spot 4 ways, and with 52 cards, i would assume the numerator is 4^52.

but this is far too small.

[Guest]

I should note that I do not know the answer to this question, although I have an answer I'm leaning toward. I have no math to back it up, however, which is why I posted here.

[Guest]

Take a standard deck of 52 well-shuffled cards. Flip them over one at a time, counting Ace through King. Whenever the value you say matches the card that is revealed, put that card into the discard pile.

For example, if the first five cards I flip over are 7, 2, 10, 4, J, then I would discard both the 2 and the 4.

If you only go through the deck once (counting Ace through King four times), what is the expected number of cards in the discard pile? That is, if you repeat this experiment an infinite number of times, what is the average number of cards discarded each trial?

If I am interpreting your intention for second part, it is an easy solution.

of the statement "That is, if you repeat this experiment an infinite number of times, what is the average number of cards discarded each trial?" your intention is to repeat the process of going through the remaining portion of the deck, guessing the cards, an infinite number of times. The math is simple average calculation. If D(n)=cards discarded during the round n and R = number of rounds executed, and A=average number of discards. we have the formula:

A=(Σ1R D(n))/R

As R approaches infinity we have (sorry for improper format)

A=Lim(as R ->∞)(Σ1R D(n))/R

we know that Σ1R D(n) as R approaches infinity = 52 however the answer does not require this knowledge since:

Lim(as R ->∞)X/R=0 for any number X

Hence: A=0

[Guest]

the chances of a correct guess on the last card is the same as for any other guess, that is 1/13. so we have:

Number of cards correct = 52 X 1/13 = 4

Now lets make the problem complex, Lets include memory and allow guessing instead of strict order. To clarify, you are attempting to guess which card is next, by remembering cards that we have already turned over, we can improve our chances of a correct guess and as we get down to fewer cards, our chances of a correct guess increases. The next to last card, we have a 50% chance of guessing right (with perfect memory) and 100% chance on last card. This is a more intriguing problem (Somewhat applicable to blackjack). Now what would the expected number of cards be? I have not worked it out but interested in seeing concept of others.

[Guest]

To clarify, Molly Mae is correct. The number I am trying to determine is the average number of cards discarded after only one round through the deck.

[Molly Mae]

the chances of a correct guess on the last card is the same as for any other guess, that is 1/13. so we have:

Number of cards correct = 52 X 1/13 = 4

Now lets make the problem complex, Lets include memory and allow guessing instead of strict order. To clarify, you are attempting to guess which card is next, by remembering cards that we have already turned over, we can improve our chances of a correct guess and as we get down to fewer cards, our chances of a correct guess increases. The next to last card, we have a 50% chance of guessing right (with perfect memory) and 100% chance on last card. This is a more intriguing problem (Somewhat applicable to blackjack). Now what would the expected number of cards be? I have not worked it out but interested in seeing concept of others.

To clarify, Molly Mae is correct. The number I am trying to determine is the average number of cards discarded after only one round through the deck.

I think Pickett's got the answer to this one, since the odds of picking a wrong card are not only higher, but lessen the chances of picking a correct card in the future (if you flip a 10 when you say 3, when you come to 10 there are fewer than 4 remaining. This happens with every flip where the card flipped is > the card said.

I am very curious, though, about thoughtfulfellow's game merged with the current game: where only the top 13 cards are drawn, but the person flipping has perfect memory and can choose any number from ace to king. On a single time through, the expected outcome should be 4/52 + 4/51 + 4/50 + ..... (since you should always choose a card that hasn't come up yet...and there's always at least 1 until the 13th card is drawn). After the 13th draw, though, going through the rest of the deck will be very tricky. If there are 4 of any card remaining, guess that card, else guess any card with 3 remaining.

[superprismatic]

I got 3.9997227 in 10,000,000 trials. So, unless I have a bug, the answer to the problem is 4.

I'm still thinking of how to attack this analytically.

[superprismatic]

The number of ways the first card can be an ace after shuffling is

4×(51!) as the ace can be one of 4 suits, and once the ace is placed,

the other 51 cards can be in any order. So the probability that an

ace is the first card is (4×(51!))/(52!) which is 1/13. The calculation

is the same for any card being in a "discard" position. Thus, at each

position, the probability that that card will be discarded is 1/13.

We want the expected value of the number of discards. By definition,

this is the sum over all positions of the probability that the card

in that position will be discarded. This sum is 52×(1/13) which is 4.

In general, if there are C cards in each suit and there are S suits,

The expected size of the discard pile is S.

[Guest]

I don't think it can be only 4, because you cannot assume each card has a probability of 1/13. You will know the last card in your hand 100% of the time. For the second to last card, you have at worst a 50% chance, if the 2 cards left are different, and at best a 100% chance if the 2 are the same.

Now if you had to guess the exact card to get it removed, then for the first card you would have a probability of 1/52, second 1/51, and so on until 1/1. This is your expected cards in the discard pile per hand, and when all of those are added up it 4.538ish. Therefore, only having to guess the number, and not the number and suit, has to give you a higher expected value.

I haven't done the math for that part but does that seem right?

Edited October 21, 2011 by grambrog24

[superprismatic]

I don't think it can be only 4, because you cannot assume each card has a probability of 1/13. You will know the last card in your hand 100% of the time. For the second to last card, you have at worst a 50% chance, if the 2 cards left are different, and at best a 100% chance if the 2 are the same.

Now if you had to guess the exact card to get it removed, then for the first card you would have a probability of 1/52, second 1/51, and so on until 1/1. This is your expected cards in the discard pile per hand, and when all of those are added up it 4.538ish. Therefore, only having to guess the number, and not the number and suit, has to give you a higher expected value.

I haven't done the math for that part but does that seem right?

I didn't assume that each card has a probability of 1/13 of being in the discard pile. I used a counting argument to prove it. The dependencies you mention have no effect on the expected value.

[Molly Mae]

I don't think it can be only 4, because you cannot assume each card has a probability of 1/13. You will know the last card in your hand 100% of the time. For the second to last card, you have at worst a 50% chance, if the 2 cards left are different, and at best a 100% chance if the 2 are the same.

Now if you had to guess the exact card to get it removed, then for the first card you would have a probability of 1/52, second 1/51, and so on until 1/1. This is your expected cards in the discard pile per hand, and when all of those are added up it 4.538ish. Therefore, only having to guess the number, and not the number and suit, has to give you a higher expected value.

I haven't done the math for that part but does that seem right?

You aren't "guessing" the number per the OP. You start at A (or 2?) and count up. And you only go through 1/4 of the deck, not the whole thing.

The number of ways the first card can be an ace after shuffling is

4×(51!) as the ace can be one of 4 suits, and once the ace is placed,

the other 51 cards can be in any order. So the probability that an

ace is the first card is (4×(51!))/(52!) which is 1/13. The calculation

is the same for any card being in a "discard" position. Thus, at each

position, the probability that that card will be discarded is 1/13.

We want the expected value of the number of discards. By definition,

this is the sum over all positions of the probability that the card

in that position will be discarded. This sum is 52×(1/13) which is 4.

In general, if there are C cards in each suit and there are S suits,

The expected size of the discard pile is S.

Is each draw independent of all previous draws, though? <- (Note that this is a serious question, not a challenge question).

[superprismatic]

You aren't "guessing" the number per the OP. You start at A (or 2?) and count up. And you only go through 1/4 of the deck, not the whole thing.

Is each draw independent of all previous draws, though? <- (Note that this is a serious question, not a challenge question).

Actually, I go through the whole deck.

No. They are not independent. But that doesn't matter to the expected value. It's the same argument that's used in proving that the expected number of fixed points in a permutation is 1.

You could probably find that proof on the web.

[bonanova]

Concepts like "order" and "previous" and "dependence" don't apply here, even tho the experiment is stated as a sequence of steps.

The chance that card x modulo 13 has a value of x does not depend on x.

I.e. there is no way to say the third card's chance of being 3 differs from the fifth card's chance of being 5.

Corollary 1: It does not matter what order you use to inspect the cards.

I.e. inspecting card number 3 before you inspect card number 5 does not alter card 5's chance of being a 5.

Corollary 2: Since the deck is well shuffled, you can call out the cards in ANY legal sequence,

e..g., AAAA222233334444 .... and get the same average number of discards.

A different number for each shuffle, of course, but the same expectation.

Sorry I can't spoiler from mt iPad, but I'm not giving a solution, just discussing the process.

[Molly Mae]

You could probably find that proof on the web.

Found it. Thanks, man.