Probability brainteaser: expected value of these two games 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?


*

*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.


*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?

 A: 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.
A: 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.$

