7

I found this brainteaser on the internet and do not know how to solve it. For the second question, My first thought is to deduct from the situation when there is only 2 slots, then 3, 4, .., n,.. slots. But I find it not that easy. Can someone give me a hint on this?

  1. You can toss a coin 100 times or stop earlier, you are paid the percentage of heads of your tosses, estimate the upper bound of the value of the game.

  2. There is a gambling machine with n-slots. You put balls one-by-one into the machine, each ball has equal probability to get inside each slot. You can stop the game anytime. In the end you will be rewarded like this: for each 1-ball slot, you are rewarded \$1; for each k-ball slot (k>=2), you are penalized \$k; for each 0-ball slot you are rewarded nothing. What is your strategy? What is the expected value of the game?

Community
  • 1
Brain Zhang
  • 689
  • 3
    Don't use single-letter textspeak abbreviations in a mathematical text! The dangers of ambiguity $r^2$ gr8. – TonyK Oct 31 '14 at 02:52
  • @TonyK: I don't understand why you squared the $r$, but I agree with the comment. Now I see- are too great. – Ross Millikan Oct 31 '14 at 02:55
  • The second is a duplicate, https://math.stackexchange.com/questions/1706571/an-interesting-probabilistic-game – Roah Apr 11 '18 at 19:30

3 Answers3

6

Let $E(h,n)$ be the expected winnings (under the optimal stopping strategy) after flipping the coin $n$ times and obtaining $h$ heads.

If you flip again, your expected earnings will be $\dfrac{1}{2}E(h,n+1)+\dfrac{1}{2}E(h+1,n+1)$.

If you don't flip again, your expected earnings will be $\dfrac{h}{n}$.

Therefore, you flip again iff $\dfrac{1}{2}E(h,n+1)+\dfrac{1}{2}E(h+1,n+1) > \dfrac{h}{n}$, and your expected earnings satisfy $E(h,n) = \max\left\{\dfrac{h}{n},\dfrac{1}{2}E(h,n+1)+\dfrac{1}{2}E(h+1,n+1)\right\}$.

Trivally, if you flip $100$ times and get $h$ heads, your winnings are $E(h,100) = \dfrac{h}{100}$.

Using a computer, we can use the above recursion to get $E(0,0) \approx 0.783894497678384$.

As it turns out, stopping after $h > t$ is pretty close to the optimal strategy. After bashing out the above recursion, the actual optimal strategy can be phrased like "After the $n$-th flip, stop if you have gotten at least $h(n)$ heads", where $h(n)$ is given by this table:

$\begin{matrix} n&\ 1&\ \ 2&\ \ 3&\ \ 4&\ \ 5&\ \ 6&\ \ 7&\ \ 8&\ \ 9&\ 10\\ h(n)&\ 1&\ \ 2&\ \ 2&\ \ 3&\ \ 4&\ \ 4&\ \ 5&\ \ 5&\ \ 6&\ 6\end{matrix}$

$\begin{matrix} n&11&12&13&14&15&16&17&18&19&20\\ h(n)&7&8&8&9&9&10&10&11&11&12\end{matrix}$

$\begin{matrix} n&21&22&23&24&25&26&27&28&29&30\\ h(n)&12&13&13&14&14&15&15&16&16&17\end{matrix}$

$\begin{matrix} n&31&32&33&34&35&36&37&38&39&40\\ h(n)&17&18&18&19&19&20&20&21&21&22\end{matrix}$

$\begin{matrix} n&41&42&43&44&45&46&47&48&49&50\\ h(n)&22&23&23&24&24&25&25&26&26&27\end{matrix}$

$\begin{matrix} n&51&52&53&54&55&56&57&58&59&60\\ h(n)&27&28&28&29&29&30&30&31&31&32\end{matrix}$

$\begin{matrix} n&61&62&63&64&65&66&67&68&69&70\\ h(n)&32&33&33&34&34&35&35&36&36&37\end{matrix}$

$\begin{matrix} n&71&72&73&74&75&76&77&78&79&80\\ h(n)&37&38&38&39&39&40&40&41&41&42\end{matrix}$

$\begin{matrix} n&81&82&83&84&85&86&87&88&89&90\\ h(n)&42&43&43&43&44&44&45&45&46&46\end{matrix}$

$\begin{matrix} n&91&92&93&94&95&96&97&98&99&100\\ h(n)&47&47&48&48&48&49&49&50&50&0\end{matrix}$

For the pinball game, your winnings on each ball are independent of each other. So, you should either play the game all day long, or not at all depending on whether your expected earnings is positive or not. This is an easy calculation, so I'll let you do it.

JimmyK4542
  • 54,331
  • You assume you will flip when $h=t$, which is a good strategy. If you get heads, you win, if you get tails you will get back (sometime) to $h=t$. Good point. – Ross Millikan Oct 31 '14 at 03:59
  • ^Stopping any time $h > t$ was your suggestion for a good strategy. I was commenting that it was close to the optimal strategy. For not using a computer, your estimate was pretty good. – JimmyK4542 Oct 31 '14 at 04:33
  • I am struck that $h(n) \gt \frac n2 +1$ starting at $n=12$ It seems your analysis says you should stop when you are strictly ahead for odd numbers of throws below $9$ or even number of throws below $12$. Otherwise you need another $1$ of margin. It would be interesting to extend your upper bound substantially and see if the stopping point increases even higher. – Ross Millikan Oct 31 '14 at 05:23
  • What do you mean by "extend your upper bound substantially"? Do you mean I should see what happens when the maximum number of flips is something larger than $100$? – JimmyK4542 Oct 31 '14 at 05:25
  • 1
    Exactly. I am thinking that the dispersions are so much larger if you try a million flips you might want more than 1 excess of heads over tails. The required margin might increase with the square root (or a slower function) of the maximum number of flips. – Ross Millikan Oct 31 '14 at 05:28
  • 1
    For the pinball game, your winnings on each ball are independent of each other. So, you should either play the game all day long, or not at all depending on whether your expected earnings is positive or not. I don't follow that at all. Given that I won $1 on some ball, my other balls are more likely to lose me money because they are more likely to land with another ball. Obviously I should not play the game all day long because I will surely lose money, but putting in the first ball always guarantees me $1. – Caleb Stanford Sep 24 '16 at 00:01
4

For a trivial estimate of the coin flip game, you can't win more than $1$ (all heads), so that is an upper bound.

Less trivially, we need to define our strategy. Suppose you have flipped $h$ heads and $t$ tails. Let $V(h,t)$ be the value of the game at this point. Clearly $V(h,t) \ge \frac h{h+t}$ because we can stop now and get that. If we flip again, the alternative is $\frac 12(V(h+1,t)+V(h,t+1))$ We also have $V(1,0)=1$ because we can't do better and stop, while $V(0,1)=\frac 12(V(1,1)+V(0,2))$ because we can't do worse and should flip again.

I suggest that you should stop any time $h \gt t$ If you decide to flip once and stop either way, you start with $\frac h{h+t}$ and trade that for $\frac {2h+1}{2(h+t+1)}$ which is less. Repeating has you in the same boat-some handwaving here.

One strategy is as follows: You flip the first time. Heads you get $1$. Tails you will keep flipping until the law of large numbers kicks in and you have (about) half heads and get $\frac 12$. The value of the game is $\frac 34$ You can do a little better by throwing when you are at exactly half heads-if you win you are ahead, if you lose you can keep flipping and (with probability $1$) get back to at least even. The value then must be a little more than $3/4$

For the pinball case, the logic is the same. You assess whether the next ball improves your payoff and play it or not. I think you can again show that you don't need to worry about long term effects-just ask if this ball improves my payoff, but I haven't proved that at all.

Ross Millikan
  • 374,822
  • "$V(n,n)=\frac12$ by symmetry": I don't agree. After one tail and one head, you do better to continue, because the probability is very high that at some later stage you will have strictly more heads than tails. Of course you would have to do the arithmetic to check that this is true; JimmyK4542 claims to have done this. – TonyK Oct 31 '14 at 03:57
  • @TonyK: I just put a comment on the other answer agreeing with this and upvoted it. – Ross Millikan Oct 31 '14 at 04:01
2

I'll skip the first question as it's been addressed in the previous answers.

Given $n$ slots, we can represent the state of the machine with the pair $(e, u),$ where $e$ is the number of empty slots and $u$ the number of slots with exactly one ball. Suppose equivalently that rewards are given (or costs are incurred) after each ball is put in, and not when the game is stopped. The future states after putting in one ball are

  • $(e-1, u+1)$ with probability $\frac{e}{n}$ and reward 1
  • $(e, u-1)$ with probability $\frac{u}{n}$ and reward -3 (a 1 ball slot becomes a 2 ball slot so you lose the initial reward, and incur an additional cost of 2)
  • $(e, u)$ with probability $1-\frac{e}{n}-\frac{u}{n}$ and reward -1.

The expected earnings of the optimal strategy hence satisfy the following relation:

$$ \begin{align} V(e, u) &= \max \left\{ 0, \frac{e}{n}(V(e-1, u+1) + 1) + \frac{u}{n}(V(e, u-1) - 3) + \left(1-\frac{e}{n}-\frac{u}{n}\right)(V(e, u) - 1) \right\} \\ &= \frac{1}{n}\max \left\{ 0, e \cdot V(e-1, u+1) + u \cdot V(e, u-1) + (n-e-u)\cdot V(e, u) + 2e-2u-n \right\}. \end{align} $$

I couldn't come up with an analytic solution to this Bellman equation. To make the relation amenable to computation, we first deal with the $V(e, u)$ term on the right. We argue as follows.

Suppose that at the state $(e, u)$ it is favorable to keep playing. Then $$ n \cdot V(e, u) = e \cdot V(e-1, u+1) + u \cdot V(e, u-1) + (n-e-u)\cdot V(e, u) + 2e-2u-n. $$ Rearranging, $$ V(e, u) = \cfrac{e \cdot V(e-1, u+1) + u \cdot V(e, u-1) + 2e-2u-n}{e + u} $$ Let $W(e, u)$ be the above expression. If it's negative then we have a contradiction. From this we can show that writing $V(e, u) = \max\{0, W(e, u)\}$ gives an equivalent formulation. Together with the boundary condition $$ V(0, u) = 0 $$ we can compute $V(n, 0)$, the expected earnings at the initial state.

Below is a plot of $V(e, u)$ for $n = 100$. The axis on the front is $u$, and the axis on the right is $e$. I found that $V(100, 0) \approx 15.$ Plot of V(e, u) for n=100

Gary Wilson Jr.
  • 141
  • "This is an easy calculation"—Accepted Answer. Thank you for actually engaging with the problem. The only question I have is about your state equation. Should it not be $V(e, u) = \max \left{0, \frac{e+1}{n}(V(e+1, u-1) + 1) + \frac{u+1}{n}(V(e, u+1) - 3) + \left(1-\frac{e}{n}-\frac{u}{n}\right)(V(e, u) - 1) \right}$? In English, the state value is the previous possible state values plus their reward/plenty of moving from said state with such the respective probability of that state. – Novice C Oct 01 '21 at 15:54