Strategy for game with two piles, maximize the payout

Question

Say I'm playing a game with two piles, both of which are initially empty. On each turn I can perform one of the following moves:

1. Add a penny to one of the two piles at random.
2. Pick a pile at random, and then take all of its contents for myself.

I have two questions based on this game.

1. Assuming I play this game for $X$ turns (let's say $X$ is $200$ if we want a concrete number) , what's the expected value for this game, and what should the strategy be I take to maximize my payout?
2. Let's now say I'm not very sure how long the game was going to be, that it lasts between $X$ and $X + \Delta X$ turns (let's say it lasts between $100$ and $200$ if we want a concrete range). How would we play the game then to maximize our payoff?

Showing my work: For the first part, my guess is that the optimal strategy is to add a penny for the first $190$ or so turns, and then withdraw with the remaining $10$ or so turns. The expected payoff following this strategy is$$(200 - n)\left(1 - {1\over{2^n}}\right),$$so we just need to find the maximum of this.

But it's unclear to me how to rigorously show this is better than any other strategy. Also, I have no clue how to do the second part.

Answer 1

Your strategy is not optimal.You can guess that by imagining the event that halfway your last 10 turns your piles get emptied. The optimal strategy cannot be "continue withdrawing".

That means that the optimal strategy must be a function, not only of time, but also of the amount of coins in each pile.

The recursion would be

$$ E^t_{x,y} = \frac12 \max\{ x+y+E^{t-1}_{0,y} + E^{t-1}_{x,0}, E^{t-1}_{x+1,y} + E^{t-1}_{x,y+1}\}, \tag1$$

where $E^t_{x,y}$ is the expected optimal gain when there are $x,y$ coins in each pile, and there remains $t$ turns.

From $(1)$ you can at least compute the optimal strategy (and its expected gain) numerically.

The first values are

$$E^1_{x,y}=\frac12(x+y);$$

$$E^2_{x,y}=\max\left\{\frac{x+y+1}{2},\frac34 (x+y)\right\}.$$

For larger values it gets more complicated, and it's not a function of $x+y$ alone.

Here's a JS Fiddle to try. For 200 turns and empty initial piles I get an expected gain of $193.66601562$, same as Apass.Jack's comment.

Answer 2

For part 1: assign an indicator variable $I_k$ to the $k$'th turn which is $1$ if I placed a coin that turn and was able to pick it up later, and $0$ otherwise. Then the value of the game is the sum of all $I_k$, and $\mathbb{E}[I_k] = 1-\frac{1}{2^{p_k}}$ where $p_k$ is the number of 'pick up' turns that come after turn $k$. If we had a strategy that had a 'pick up' on turn $t_1$ and a 'drop penny' on turn $t_2$ for $t_1<t_2$, the total expectation of all $I_k$ can be improved (or at least not reduced) by swapping these two actions. This proves your claim.