1
$\begingroup$

Consider a normal $52$-card deck. Cards are dealt one-by-one. You get to say when to stop. After you say "stop" you win $\$1$ if the next card is red, lose $\$1$ if the next card is black. Assuming you use the optimal stopping strategy, how much would you be willing to pay to play?

Is there an optimal strategy? I found someone analysing it using this table. I can understand it, but I am still confused about how much I would be willing to pay to play.

$\endgroup$
  • $\begingroup$ Easy to do by backwards induction...that is, create a state space with states $S_{r,b}$ where $r$ is the number of remaining reds, $b$ the number of remaining blacks. Easy to compute the value of ending the game on such a state, and induction lets you value the option of continuing. This is what finance people call an "American Option on a Brownian Bridge" and it's unlikely there is a simple closed formula for its value. $\endgroup$ – lulu Sep 19 '16 at 13:20
  • $\begingroup$ To be clear: "easy to do" means "easy to do with a computer". I wouldn't try to do it by hand. $\endgroup$ – lulu Sep 19 '16 at 13:21
  • $\begingroup$ Your payment rule is quite different from the rule in the link you gave. $\endgroup$ – Barry Cipra Sep 19 '16 at 13:30
  • $\begingroup$ Oh! I didn't look carefully at your rule. That is absolutely not the usual rule, nor is it the rule analyzed in the link you provide. The induction method still works. Note: it's not immediately obvious to me that your game has positive expected value. With the standard game, playing through to the end always nets $0$ and some paths have positive value so the game has positive expectation. The same argument doesn't obviously apply here. $\endgroup$ – lulu Sep 19 '16 at 13:39
  • 1
    $\begingroup$ Do I have to say "stop" before the last card is dealt? For example if I know there is just a black card left? $\endgroup$ – gnasher729 Sep 20 '16 at 12:56
3
$\begingroup$

The payment/stopping rule in the link is quite different from the rule presented in the question here. I'm going to answer the question here.

It turns out there is no strategy that will improve your odds of winning a game in which you are allowed to end the game by guessing that the next card is red; the expected value is $0$, so you shouldn't be willing to pay anything to play. (I am assuming that the cards have been shuffled, so that no one knows the status of any card until it is revealed.)

Here's a way to see that the expected value is $0$. Imagine the cards are spread out, face down, from left to right. Start by placing your finger on the rightmost card, to indicate that you tentatively intend to stop at the very end. Obviously, this card has a $50\%$ chance of being red. Now, before each card, starting from the left, is turned over, you are allowed to change your mind and stop with it instead. Whether you do or don't doesn't matter: the rightmost card and the current still-face-down leftmost card have equal probability of being red, so you may as well stick with your initial tentative decision. Although your current assessment of how much you stand to gain (or lose) will change each time a leftmost card is revealed, that has no bearing on whether to stop. In other words, even though it may feel as is you have some control over your fate, you really don't.

Remark: This answer is similar to an answer I gave to a "number battle" problem.

$\endgroup$
  • 1
    $\begingroup$ if the first card is black, then suddenly the chances of any of the next 51 cards being red has increased. I'm presuming you see the card you didn't stop at. $\endgroup$ – Cato Sep 19 '16 at 14:20
  • $\begingroup$ @AndrewDeighton: That's true, but it's equally likely that the first card will be red, in which case you're likely to lose money instead. The question isn't "what is the best strategy?", it's "what is the expectation value of this game?" $\endgroup$ – Michael Seifert Sep 19 '16 at 14:26
  • $\begingroup$ @Michael Seifert - yes but my simulations now show that is unlikely that there will be no time during the process at which the number of red remaining is not higher than the number of black - so a strategy of calling red at any time there is a red majority should yield an advantage - if the first card is red, then you play the waiting game $\endgroup$ – Cato Sep 19 '16 at 14:48
  • $\begingroup$ 0 down vote on the first choice, there is a 50% chance of black, leading to the player having a better than evens win chance at that point. If the first card is red, then his win chance at that point is <50%, however if he continues drawing cards there has to be a non-zero chance that a red majority will present itself. The odds have to be >50% with the simplistic probability of voting red where there is any red majority. $\endgroup$ – Cato Sep 19 '16 at 14:53
  • $\begingroup$ my attempt at simulating a strategy have come out with no real positive result. So I'll eat my words probably. In the rarer cases where there is never a majority of reds left, your chances of winning are quite low - which cancels the benefits I was imagining. $\endgroup$ – Cato Sep 19 '16 at 17:23
0
$\begingroup$

Problem: A friend turns over the cards of a well shuffled deck one at a time. You can stop anytime you choose and bet that the next card is red. What is the best strategy?

Solution: For $n=0,1,\dots, 51$, let $R_n$ be the number of red cards left after $n$ cards have been turned over. Then $$R_{n+1}=\cases{R_n&with probability $1-p$\\ R_n-1&with probability $p$},$$ where $p=R_n/(52-n)$, the proportion of reds left. Taking expectations we get $$\mathbb{E}(R_{n+1}\,|\, {\cal F}_n)=\mathbb{E}(R_{n+1}\,|\, R_n)=R_n-{R_n\over 52-n}=R_n\left({52-(n+1)\over 52-n}\right)$$ so that $$\mathbb{E}\left({R_{n+1}\over 52-(n+1)}\,\Bigl|\, {\cal F}_n\right)={R_n\over 52-n}.$$ Here ${\cal F}_n:=\sigma(R_0,R_1,\dots, R_n).$ This means that $M_n:=R_n/(52-n)$ is a martingale.

Now let $T$ represent your stopping strategy. Then $\mathbb{P}(T \mbox{ is successful}\,|\, {\cal F}_T)=M_T$, and by the optional sampling theorem, $$\mathbb{P}(T\mbox{ is successful})=\mathbb{E}(M_T)=\mathbb{E}(M_0)=1/2.$$

Every strategy has a 50% chance of success!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.