Pick a red card, randomly?

[bonanova]

One of my favorite problems asks the best strategy to get the highest number possible from a finite collection (say of 100 random numbers) whose values are told to you sequentially, and you must choose one of them at the moment you hear it. It has been posted here before, so I won't repeat it as a puzzle. It's a "stopping" puzzle and you choose when to stop in a way that maximizes your expected "score." (Not that maximizes your chances of choosing the highest number from the collection.) Here's another "stopping" puzzle that uses a standard deck of cards.

A shuffled deck is placed face down, in a stack. A dealer begins turning the top card face up and placing it in a discard pile. At a time of your choosing you say "stop." The dealer then turns over the next card, and if it's a red card, you win. Note you are free to say "stop" at any time. What is your strategy?

[CaptainEd]

A trivial strategy:

keep track of Red fraction, as soon as it goes above .55, say "stop". My small number of simulations tells me you'll get that chance 88% of the games. Hmmm. that makes an expected value of .88 * .55 = .484. Sounds like you're better off to take the top card...

I wonder if there's a better result by waiting m cards, and making a different fraction threshold depending on the fraction at that time...

Edited September 18, 2015 by CaptainEd

[jasen]

 

 

in my computer simulation

the best strategy is 
1. anytime you find 2 black more then red (such as 4B 2R) then you stop the dealer
2. or all black has appear then stop the dealer
3. but if until last card no condition above appear then bet for last card.

and you will win with probability 50.030%. (very-very small)

I've tried many combination, like 1 black more, or 3 black more, or combination of them, but those do not better then solution above.

 

 

 

[jasen]

Option Explicit

Dim Cards As Variant
Dim SumRed As Variant
Dim i As Integer
Dim j As Single
Dim SumBlack As Integer
Dim YouWin As Single

Sub SuffleCards()
Dim i As Integer
Dim PosCard1 As Integer
Dim PosCard2 As Integer
Dim TempCard As Integer
Randomize
For i = 1 To 50
    PosCard1 = Int((52 * Rnd))
    PosCard2 = Int((52 * Rnd))
    If PosCard1 <> PosCard2 Then
        TempCard = Cards(PosCard1)
        Cards(PosCard1) = Cards(PosCard2)
        Cards(PosCard2) = TempCard
    End If
Next i
End Sub

Sub StopCardGame()
Dim xx As Integer
ReDim SumRed(52)
Const NumOfGames = 1000000
For xx = 1 To 10
    YouWin = 0
    Randomize
    Cards = Array(1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0)
    For j = 1 To NumOfGames
        SuffleCards
        SumRed(0) = Cards(0)
        For i = 1 To 50
            SumRed(i) = SumRed(i - 1) + Cards(i)
            SumBlack = i - SumRed(i)
            If SumBlack = 26 Or SumBlack = SumRed(i) + xx Then
                If Cards(i + 1) = 1 Then YouWin = YouWin + 1
                GoTo gameOver
            End If
        Next i
        If Cards(51) = 1 Then
            YouWin = YouWin + 1
            GoTo gameOver
        End If
gameOver:
    Next j
    Selection.TypeText Text:=vbCrLf + win + str(YouWin) + " times of " + str(NumOfGames) + " games with " + str(xx) + " more black"
Next xx
End Sub

I change my answer

With The simulation Above I get this result

 win 500096 times of  1000000 games with  1 more black
 win 500356 times of  1000000 games with  2 more black
 win 500055 times of  1000000 games with  3 more black
 win 500070 times of  1000000 games with  4 more black
 win 499398 times of  1000000 games with  5 more black
 win 500050 times of  1000000 games with  6 more black
 win 499553 times of  1000000 games with  7 more black
 win 499117 times of  1000000 games with  8 more black
 win 499168 times of  1000000 games with  9 more black
 win 500105 times of  1000000 games with  10 more black

 So, I think there is no best strategy.

Edited September 19, 2015 by jasen

[bonanova]

Can you prove it?

[bubbled]

Here's my answer:

 

I think there is no strategy that can do better than 50%. There may be a way to do a formal inductive proof. But, in lieu of that here's my thinking.

Let's say for some reason we have continued with the game until there are 2 cards. If there are two black cards or two red cards left, it doesn't matter what you do. If there 1 of each, you can say stop and be 50-50. Or, if you let the 51st card turn, you will either be 0% or 100% with total odds of 50%. No optimal strategy.

Now, let's see what happens if there are 3 card left. Again, if there are 3 red or 3 black, it doesn't matter what you do. If there are 2 red and 1 black, you can stop and be 66%, or you can wait another card. 66% of the time you will be 50%, and 33% of the time, you will be 100%, which totals 66%. If you are down to 1 red and 2 black, you can stop and be 33%, or wait another card and 33% of the time you will be 0%, and 66% of the time you will be 50%. Again, that all adds up to total EV of 33%. Again, no optimal strategy.

I'm sure I could build up from there to 4, 5, ..., 52 cards.

But, let's look at your decision with 52 cards left. You could stop immediately, and be exactly 50%. But, if you let a card turn over, it is 50% to be red and 50% to be black. So, you'd be 50% to be 26/51 or 50% to be 25/51. Again, that adds up to 50% total EV.

I'm totally open to the idea that there could be a strategy, but it appears to me, you never know what card will turn over next. Your odds of winning will change from card to card, but that change is random, and in the long run will result in a 50% win rate, no matter what you do.

[bubbled]

OK. Here's my attempt at a formal inductive proof:

 

I will show that for all N = r + b, where N = total number of cards, r = number of red cards and b = number of black cards, that no matter whether you stop immediately, or look at another card, expected chances of winning is P(win) = r / (r + b).

Base case: Clearly, if N = 1, P(win) = r / (r + b). If the one card left is red, you are P(win) = 1 / (1 + 0) = 1 and if it's black, P(win) = 0 / (0 + 1) = 0. I'm a little uncomfortable limiting the base case to just 1 card, as you don't really have the option to stop or continue. So, let's include 2 cards into the base case. 

If there are 2 red cards, P(win_stop) = 2 / (2 + 0) = 1. If you let a card turn over, P(win) = 1 / (1 + 0) = 1. If there are 2 black cards, P(win_stop) = 0 / (0 + 2) = 0. If you let a card turn over, P(win) = 0 / (0 + 1) = 0. If there is 1 red and 1 black, then P(win_stop) = 1 / (1 + 1) = .5. If you let a card turn over, P(win) = 0 * P(a red card shows) + 1 * P(a black card shows) = (0 / (0 + 1) )* (1 / (1 + 1)) + (1 /(1 + 0)) * (1 / (1 + 1)) = .5.

Assumption: We assume that if r + b = N, then whether you stop or continue, P(win) = r / (r + b).

Inductive Step: I will try to show that if r + b = N +1, whether you stop or continue, P(win) = r / (r + b). Clearly, if you stop, P(win_stop) = r / (r + b). If you let a card turn, P(win) = P(win if black card shows) * P(a black card shows) + P(win if red card shows) * P(a red card shows) = r / (r + b - 1) * b / (r + b) + ((r - 1) / (r + b -1)) * (r / (r + b )) = (r * (r + b -1)) / (r + b) * (r + b -1) = r / (r + b). 

It's been a while since I've done an inductive proof, but I think this should hold up.

Edited September 20, 2015 by bubbled