Suppose we have a biased coin with probability $p = 0.4$ of landing heads. A gambler starts out with an integer $x <= n$ as capital. The gambler can bet some amount of money less than $x$ on the coin. If the coin lands heads, he doubles his stake (i.e. he bets $y$, he gets an extra $y$) otherwise, he loses his stake. His ultimate goal is to reach $n$ dollars. Going beyond this point is not worth any more points than just getting to $n$ dollars.
Let $p(x,n)$ be the optimal amount of money the gambler should bet given that he has $x$ capital and needs to get to $n$ dollars.
1) Is this unique?
2) What is $p(x,n)$?
I've performed some numerical evidence. Here's the graph of $p(\cdot,100)$:
Notice the two phenomena. Spikes and pyramids. Here's the one for $p(\cdot,101)$:
Only one pyramid! By playing around with more of these pictures, I've come up with the following conjecture:
- $p(x,2m+1) = p(2m+1-x,2m+1)$
- $p(x,2m+1) = x \text{ for } 0 \leq x \leq m$
- The number of spikes for $n = 2^k m$, $m$ odd, is $2^k -1$.
- For $m$ odd, we have: $$p(x,2^km) = \begin{cases} p(x,2^{k-1}m) & 0 \leq x < 2^{k-1}m \\ 2^{m-1}m & x = 2^{k-1}m \\ p(x-2^{k-1}m,2^{k-1}m)& x > 2^{k-1}m \end{cases}$$
In other words, it seems like in the case where $n$ is odd, $p(x,n)$ should be as large as possible, until $x > m$. At this point, betting more than $2m+1-x$ would be unnecessary. This is the pyramid phenomenon. The spike phenomenon arises when $n$ has a factor of 2.
How do I go about proving these properties for $p$? I computed the graphs using dynamic programming, and somehow messing around with those recurrence has been rough for me, but maybe that's more proof of my inexperience than of the difficulty. If this is some well-known phenomenon, I'll quite happy with a reference!
Sorry for the long post!