The expected value of random variable on tosses of a coin

Question

Came across an interesting problem today. You are given a coin and x money, you double money if you get heads and lose half if tails on any toss.

1. What is the expected value of your money in n tries
2. What is the probability of getting more than expected value in (1)

This is how I approached it. The probability of heads and tails is same (1/2). Expected value after first toss = $1/2(2\times x) + 1/2(1/2\times x) = 5x/4$ So expected value is $5x/4$ after first toss. Similarly repeating second toss expectation on 5x/4, Expected value after second toss = $1/2(2\times 5x/4) + 1/2(1/2\times 5x/4) = 25x/16$

So you get a sequence of expected values: $5x/4$, $25x/16$, $125x/64$, ...

After $n$ tries, your expected value should be $(5^n/4^n) \times x$.

If $n$ is large enough, your expected value should approach the mean of the distribution. So probability that value is greater than expected value should be $0.5$. I am not sure about this one.

Answer 1

If n is large enough, your expected value should approach the mean of the distribution.

Yes that's correct.

So probability that value is greater than expected value should be 0.5.

This would only be correct if the distribution is symmetric - which in your game isn't the case. You can see this easily if you think about what the median value of your winnings should be after $n$ throws.

---

You can think of your problem as a random walk. A basic one-dimensional random walk is a walk on the integer real line, where at each point we move $\pm 1$ with probability $p$. This is exactly what you have if we ignore the doubling/halving of money and set $p=0.5$. All we have to do is remap your coordinate system to this example. Let $x$ be your initial starting pot. Then we remap in the following way:

x*2^{-2} = -2
x*2^{-1} = -1 
  x = 0
 x*2 = 1  

i.e. $2^k x=k$. Let $S_n$ denote how much money we have made from the game after $n$ turns, then

\begin{equation} \Pr(S_n = 2^k x) = 2^{-n} \binom{n}{(n+k)/2} \end{equation} for $n \ge (n+k)/2 \ge 0$.

When $(n+k)$ isn't a multiple of 2, then $\Pr(S_n)=0$. To understand this, assume that we begin with £10. After $n=1$ turns, the only possible values are £5 or £20, i.e. $k=-1$ or $k=1$.

The above result is a standard result from Random walks. Google random walks for more info. Also from random walk theory, we can calculate the median return to be $x$, which is not the same as the expected value.

Note: I have assumed that you can always half your money. For example, 1pence, 0.5pence, 0.25pence are all allowed. If you remove this assumption, then you have a random walk with an absorbing wall.

---

For completeness

Here's a quick simulation in R of your process:

#Simulate 10 throws with a starting amount of x=money=10
#n=10
simulate = function(){
  #money won/lost in a single game
  money = 10
  for(i in 1:10){
    if(runif(1) < 0.5)
      money = money/2
    else
      money = 2*money
  }
  return(money)
}

#The Money vector keeps track of all the games
#N is the number of games we play
N = 1000
Money = numeric(N)
for(i in 1:N)
  Money[i]= simulate()

mean(Money);median(Money)
#Probabilities
#Simulated
table(Money)/1000
#Exact
2^{-10}*choose(10,10/2)

#Plot the simulations
plot(Money)

Answer 2

Let $S_k$ be the wealth after $k$ plays of this game, where we assume $S_0 = 1.$ The temptation here is to take $X_k = \log{S_k}$, and study $X_k$ as a symmetric random walk, with innovations of size $\pm \log{2}$. This, as it turns out, will be fine for the second question, but not the first. A bit of work will show that, asymptotically we have $X_k \sim \mathcal{N}(0,k(\log{2})^2)$. From this you cannot conclude that $S_k$ is asymptotically log normally distributed with $\mu = 0, \sigma = \log{2}\sqrt{k}.$ The log operation does not commute with the limit. If it did, you would get the expected value of $S_k$ as $\exp{(k \log{2}\log{2}/2)}$, which is nearly correct, but not quite.

However, this method is just fine for finding quantiles of $S_k$, and other questions of probability, like question (2). We have $S_k \ge (\frac{5}{4})^k \Leftrightarrow X_k \ge k \log{(5/4)} \Leftrightarrow X_k / \sqrt{k}\log{2} \ge \sqrt{k}\log{(5/4})/\log{2}.$ The quantity on the lefthand side of the last inequality is, asymptotically, a standard normal, and so the probability that $S_k$ exceeds its mean approaches $1 - \Phi{(\sqrt{k}\log{(5/4)}/\log{2})},$ where $\Phi$ is the CDF of the standard normal. This approaches zero fairly quickly.

Matlab code to check this:

top_k = 512;
nsamps = 8192;
innovs = log(2) * cumsum(sign(randn(top_k,nsamps)),1);
s_k = exp(innovs);
k_vals = (1:top_k)';
mean_v = (5/4) .^ k_vals;
exceed = bsxfun(@ge,s_k,mean_v);
prob_g = mean(double(exceed),2);

%theoretical value
%(can you believe matlab doesn't come with normal cdf function!?)
nrmcdf = @(x)((1 + erf(x / sqrt(2)))/2);
p_thry = 1 - nrmcdf(sqrt(k_vals) * log(5/4) / log(2));

loglog(k_vals,prob_g,'b-',k_vals,p_thry,'r-');
legend('empirical probability','theoretical probability');

the graph produced:

Answer 3

You're right about the expectation.

You actually also have the right answer to the probability of getting more than your original stake back, although not the right proof. Consider, instead of the raw amount of money you have, its base-2 logarithm. This turns out to be the number of times you've doubled your money, minus the number of times you've halved it. This is the sum $S_n$ of $n$ independent random variables, each equal to $+1$ or $-1$ with probability $1/2$. The probability that you want is the probability that this is positive. If $n$ is odd, then by symmetry it's exactly $1/2$; if $n$ is even (call it $2k$) then it's $1/2$ minus half the probability that $S_n = 0$. But $P(S_{2k} = 0) = {2k \choose k}/2^{2k}$, which approaches $0$ as $k \to \infty$.