Highest of the lows

[bonanova]

You draw cards at random and without replacement from a deck of N cards, each of which is marked with a unique integer from 1 to N, inclusive. You create two piles, as follows. The first card is placed on the table in front of you. If the second card drawn has a smaller number, you place it to the left of the first; if it's larger, you place it to the right of the first card. You now have a left pile and a right pile.

You continue until all N cards have been drawn. Each card is placed on the left pile if it has a smaller number than the previous card, and on the right pile if its number is larger than the previously drawn card. Note, there is never a tie: each card has a unique number.

What is the expected number of cards in the left pile after all N cards have been drawn?

OK, that answer is not difficult to determine, since the definitions of the piles are symmetrical.

Here's the real question: what is the expected value of the largest number in the left pile?

Example for N=10 and the order of the shuffled deck is 2 7 5 3 6 1 4 9 10 8.

• 2 is placed on the table
• 7 is placed to the right of the 2 (7>2)

  So 2 has become the left pile, and 7 is the right pile.

• 5 is placed on the left pile (5<7)
• 3 is placed on the left pile (3<5)
• 6 is placed on the right pile (6>3)
• 1 is placed on the left pile (1<6)
• 4 is placed on the right pile (4>1)
• 9 is placed on the right pile (9>4)
• 10 is placed on the right pile (10>9)
• 8 is placed on the left pile (8<10)

The left pile contains 2 5 3 1 8, and its highest-numbered card is 8.

What is the expected value for N=1000?

[harey]

I do not follow here. Worst case: the cards are sorted.

 

 

Bonanova wrote:

What is the expected number of cards in the left pile after all N cards have been drawn?

OK, that answer is not difficult to  determine, since the definitions of the piles are symmetrical.

Edited July 13, 2015 by harey

[bonanova]

Sorry. Meant to say the deck is shuffled.

 

But since it's a random draw I guess you could consider they're drawn from a box instead of dealt from a deck.

In any case, assume you encounter the cards, sequentially, in random order.

By symmetry, the piles will be expected to have N/2 cards each, but that's not the puzzle question.

 

The question asks for the expected value of the highest-numbered card in the left pile.

In the example given, the highest-numbered card in the left pile is 8.

[dgreening]

A card will go into the low pile when it immediately follows a higher card.

card 1000 can never meet this criteria
card 999 can meet this only if it follows card 1000 [P = 0.1%]
card 998 can meet this criteria if it follows cards 1000 or 999 [P= 0.2%] ...

The expected value should be the pioint at which The sum of the probabilities = 50%

By my calculations this occurs between 968 and 969.

So the expected value will be about 968.88

[plasmid]

A card will go into the low pile when it immediately follows a higher card.

card 1000 can never meet this criteria

card 999 can meet this only if it follows card 1000 [P = 0.1%]

card 998 can meet this criteria if it follows cards 1000 or 999 [P= 0.2%] ...

The expected value should be the pioint at which The sum of the probabilities = 50%

By my calculations this occurs between 968 and 969.

So the expected value will be about 968.88

I agree that, for any given card of value M, since you can look at the card preceding it (or if M is the first card then look at the card following it) and place card M in the left pile if that other card is larger, you can say that that will happen with probability (N-M)/(N-1).

You might then be tempted to calculate the probability that card N-1 goes in the left pile as 1/(N-1), then add the probability that card N-2 goes in the left pile as 2/(N-1), then add the probability that card N-3 goes in the left pile as 3/(N-1), etc. and find out when that sum of probabilities crosses 50%. Or if it makes conceptualization any easier: calculate the probability that NONE of cards N-1, N-2, N-3 ... are in the left pile: (N-1)/(N-1) * (N-2)/(N-1) * (N-3)/(N-1) * ... and see where that crosses 50%.

But does the probability that card N-2 will go into the left pile still equal (N-M)/(N-1) if you consider only the remaining arrangements after excluding those where N-1 has already gone into the left pile? If not, then what you really need to calculate is "the probability that card M goes in the left pile if you're given that none of the larger cards will go in the left pile".

Edited July 16, 2015 by plasmid

[bonanova]

I know the answer approximately from simulations. I'm still scratching my head about calculating it.

I agree with plasmid's last statement, but how to calculate his "given" puzzles me.

[plasmid]

I can calculate the probability that at least one of card N-1 or card N-2 falls in the left pile. I think this might be extendable to larger numbers, albeit with the equations becoming somewhat unwieldy.

For any given card M, define its "determining card" D_M as the card that determines which pile it will go into – D_M would be the card in front of M if M is not the first card, or the card behind M if M is the first card. If D_M > M then M goes in the left pile, if D_M < M then M goes in the right pile.

 

If M = N, then card M can never go in the left pile because D_M can't be greater than M since M is the biggest card in the deck.

 

If M = (N-1), then card M will go in the left pile if and only if D_M = N. There are N-1 cards in the deck that could be the determining card for M, so the odds that the determining card is card N would be 1/(N-1).

 

If M = (N-2) and we just want to calculate the odds that M is in the left stack without worrying about whether card (N-1) is already in the left stack, we can use similar logic to say that the determining card for M could be any card except M (so there are N-1 cards to choose from) and M will end up in the left stack if its determining card is either N or (N-1), so the odds of that happening are 2/(N-1).

 

If we're looking for cases where either M = (N-1) or M = (N-2) are in the left deck, we can take the sum of those two probabilities and then subtract out the probability that both (N-1) and (N-2) are in the left pile since they would have been counted twice but only represent one outcome. In order for both N-1 and N-2 to fall in the left pile, three things need to occur.

 

First, D_N-1 must be card N. As was shown earlier, the odds of that are 1/(N-1).

 

Second, if you're given that D_N-1 = N, but N-1 is the last card in the deck, then obviously D_N-2 can't be N-1 or N. So only (N-1) / N of the scenarios will have a possibility of card N-2 also going to the left pile.

 

Third, if you're dealing with one of those (N-1) / N scenarios where card N-2 could potentially fall in the left pile: If you're given the positions of cards N and N-1, then there are N-2 positions left for card number N-2 to potentially be in, and exactly one of those positions would have D_N-2 being either N-1 or N. So those odds would be 1 / (N-2).

 

Since all three of those things above have to occur, the total odds are

[1 / (N-1)] x [(N-1) / N] x [1 / (N-2)] = 1 / N(N-2)

 

Finally, to calculate the odds that either card N-1 or card N-2 would fall in the left pile.

If you define P_X as the probability that card X falls in the left pile, that would be:

P_N-1 + P_N-2 – P_{N-1 and N-2}

1/(N-1) + 2/(N-1) – 1/N(N-2)

 

Edited July 26, 2015 by plasmid

[plasmid]

Correction to my previous post:

When I spoke of the second thing that needs to occur for both N-1 and N-2 to go in the left pile, I said that N-1 can't be the last card in the deck or else N-2 can't have D_N-2 be N-1 or N. That's true, but there's another situation to consider: if card N is the second card in the deck and card N-1 is the third, then card N-2 could be either the first card or the fourth card. Since there are two possible positions for card N-2 in that case, that "makes up for" the fact that there are no possible positions for N-2 in the case where N-1 is the last card.

 

So the total odds of both N-1 and N-2 going into the left pile are

1 / (N-1)(N-2)

 

And the total odds of either N-1 or N-2 being in the left pile are

P_N-1 + P_N-2 – P _{N-1 and N-2}

1/(N-1) + 2/(N-1) – 1/(N-1)(N-2)

With the formula looking like that, it becomes more tempting to try to apply the approach to cases beyond N-1 and N-2.

Edited July 26, 2015 by plasmid

[bonanova]

Could that result be programmed recursively, rather than going for closed form?

[plasmid]

If you want to solve for the probability that any cards from card N to card (N-M) are in the left deck, I guess you could try:

1. Take the sum of the (independent) probabilities that each of the cards from N to (N-M) goes in the left pile. That's just the sum of the terms X/(N-1) where X goes from 1 to M+1.

2. Subtract out the probability that any pair of two cards from N to (N-M) goes in the left pile. I did the case of two consecutive cards above; the approach for two non-consecutive cards would be different. But before you go solving the case of two non-consecutive cards, consider what you'll still have in store to calculate afterward:

3. Add back the probability that any set of three cards from N to (N-M) goes in the left pile. Why do you need to add back this probability? Consider a scenario where three cards are in the left pile. That scenario gets counted positively three times (once for each of the three individual cards during step 1) and gets counted negatively three times (once for each of the three pairs of cards out of the triplet during step 2), so it needs to be calculated and added back in positively once more. Also, this probability seems like it would be very difficult to calculate since you have to deal with separate scenarios were none, some, or all of the cards in the triplet are consecutive.

4. Deal with even higher order sets of cards going in the left pile

That looks too complicated for me to attempt without a more Ah-ha approach.

Edited July 28, 2015 by plasmid

[bonanova]

Simulation is the only I know. 

[CaptainEd]

My feeble excel simulation with n of 1000 yields 959. Sample size a meager 16 sequences. Interesting that 959 came up twice out of those 16 sequences.

[CaptainEd]

50 sequences, avg 958.14

100 sequences, avg 959.17, max 995, min 91

it is looking like about 959. Why?<shrugs emoji>

[bonanova]

50 sequences, avg 958.14

100 sequences, avg 959.17, max 995, min 91

it is looking like about 959. Why?<shrugs emoji>

I'm surprised the result is as high as that. A simple game is to use a deck of 52 cards and ordering A 2 3 4 5 6 7 8 9 10 J Q K and C D H S in ascending order the expected highest raking card in the low pile becomes the Club Queen. That's the 45th highest card out of 52.

[bonanova]

I'm going to mark this puzzle closed, with plasmid's answer as being the best statement of how to get to a proof. I may be able to resurrect my simulation computer and do a long simulation at some point. If that's successful, I'll post the result here. Best estimate, from the Queen of Spades result of a few years ago is 86% of the highest ranking card showing up in the left pile.

[Logophobic]

I'll bring this back up because I believe I have a better solution.

Spoiler

Simulated Sums:
965 0.474 | 961 0.469
964 0.493 | 962 0.488
963 0.512 | 963 0.507
962 0.531 | 964 0.526
961 0.550 | 965 0.545

Calculated Sums:
965 0.471 | 961 0.472
964 0.490 | 962 0.491
963 0.509 | 963 0.510
962 0.528 | 964 0.529
961 0.546 | 965 0.548

The probability of card M of N being the highest card in the left pile is:

(N-M)/N * (N-1)/N * (N-2)/N * (N-3)/N *...* (N-M-1)/N

 

Edited December 24, 2015 by Logophobic

[Logophobic]

OK, I realize that calculating the sums is not that simple. However, calculating the probability of card M of N being the highest card in the left pile as

X = N - M; P_X = X / (N-1) * (1 - P_X-1)

gives a close enough approximation.

My simulations show that half of the time the highest card will be greater than or equal to 963. My simulations also show that the card with the highest probability of being the highest card in the left pile is 968. Which of these is the expected value?

[bonanova]

From your post, 963 is the median and 968 is the mode. The expected value is the mean.

My simulations also give a median of 963, but the noise didn't permit an accurate value of mode. My mean value is in the vicinity of 961.x

Simulations for different size decks gave a result that I did not expect. The bigger the deck was, the higher the fraction of the top card in the left pile was:

10 cards -> ~6.5
52 cards -> ~43.6 = Queen of clubs
100 cards -> ~88.03
1000 cards -> ~961.3

After some though I think this makes sense. For a deck of N cards, the mean value of the cards in the left pile is N/3 and the mean of the right pile is 2N/3. Those values are independent of N. But we should expect the spread of the values in each pile to increase with N.

I suspect the limit of the largest card in the left pile is N itself as N -> infinity. It's hard to imagine, that is, that the limit would be bounded away from N.

[Logophobic]

Ah. In that case my simulations agree with yours. I noticed a certain relation between N and EV, so I ran a few more simulations.

The first number is N, the second is EV based on simulation. The third is a very simple calculation. (See below.)

100  88.21  87.50
200 182.96 182.32
300 278.84 278.35
400 375.62 375.00
500 472.53 472.05
600 569.96 569.38
700 667.59 666.93
800 765.54 764.64
900 863.13 862.50
1000 961.13 960.47

If that wasn't evidence enough:

1000 960.85 960.47
2000 1944.74 1944.10
3000 2932.26 2931.53
4000 3921.39 3920.94
5000 4912.13 4911.61
6000 5903.97 5903.18
7000 6896.78 6895.42
8000 7888.41 7888.20
9000 8881.87 8881.41
10000 9875.06 9875.00

The very simple calculation?

Spoiler

EV = N - 1.25 * Sqr(N)

 

[bonanova]

Which is close (enough) to

Spoiler

N -  1.2533141... * sqrt(N)