Game with losing and winning a dollar

Question

I found an interesting problem in my book:

There is a game where player starts with $k\$$. In each step he wins or loses $1\$$ (both with probability $p=\frac{1}{2}$). The game ends when player has $0$ or $n$ dollars. Calculate:

1. probability of reaching $n$ dollars.
2. expected number of steps during the game.

This exercise is to practice Markov chains. So I imagine this as a graph: $$0\leftarrow1\leftrightarrow2\leftrightarrow...\leftrightarrow (k-1) \leftrightarrow k \leftrightarrow (k+1)\leftrightarrow...\leftrightarrow (n-1) \rightarrow n$$ where every edge has probability $\frac{1}{2}$.

And my approach was: let $f_{k,n}$ denote probability of winning $n\$$, starting with $k\$$. So we need to calculate it, and we know that $\forall_{1<i<n}$ we have: $f_{i,k}=\frac{1}{2}f_{i-1,n}+\frac{1}{2}f_{i+1,n}$ and $f_{1,n}=\frac{1}{2}f_{2,n}$ and $ f_{n,n}=1$. But this gives us system of recurrences which does not seem to be solvable (but only from my point of view, of course). I think it is a dead end, and this task need some smart observation.

Can anybody help?

Answer 1

Let $p_k$ be the probability that the player starting with $k$ dollars win i.e. reaches $n$ dollars. Hence, $$p_k = \dfrac{p_{k-1} + p_{k+1}}2 \,\,\,\,\,\,\,\,(\star)$$ for $k \in \{1,2,\ldots,n-1\}$ and $p_0 = 0$ and $p_n = 1$. The boundary condition gives us a hunch to try if $p_k = \dfrac{k}n$ is a solution. You can see if this is a solution by checking if $(\star)$ and the boundary conditions are satisfied.

For the second part, let the expected number of steps in the game for a player starting with $k$ dollars be $v_k$. We then get that $$v_k = 1 + \dfrac{v_{k-1} + v_{k+1}}2 \,\,\,\,\,\,\,\,\,\,\, (\dagger)$$ with $v_0 = v_n = 0$. Hence, $$\vec{v} = 2\begin{bmatrix}2 & -1 & 0 & 0 & \cdots & 0 & 0\\ -1 & 2 & -1 & 0 & \cdots & 0 & 0\\ 0 & -1 & 2 & -1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & 2 & -1\\ 0 & 0 & 0 & 0 & \cdots & -1 & 2 \end{bmatrix}^{-1} \begin{bmatrix} 1\\ 1\\ 1\\ \vdots \\ \vdots \\ 1 \end{bmatrix}$$ The boundary condition gives us a hunch to try $v_k = ck(n-k)$ where the constant $c$ should be such that $v_k$ satisfies $\dagger$. Hence, $$ck(n-k) = 1 + c\dfrac{(k-1)(n-k+1)+(k+1)(n-k-1)}2 = 1 + ck(n-k) - c \implies c = 1$$ Hence, $$v_k = k(n-k)$$

Answer 2

This involves the binomial expansion. It is simplified by the fact that $p=q$.

For the second part, you need to find $m$ which gives the binomial expansion such that $P(\le0)+P(\ge{n})={1\over2}$.

Consider the binomial of degree $m$ where ${m}>\max(n,2k)$, this gives a non zero probability at both ends, specifically:

$$P(\le0)=\sum_{i=1}^{\lceil{m\over2}\rceil-k}{m!\over{i!(m-i)!}}{1\over2^m}$$

$$P(\ge{n})=\sum_{i=n}^{m}{m!\over{i!(m-i)!}}{1\over2^m}$$

because of the symetry of the binomial distribution the second equation can be rewritten

$$P(\ge{n})=\sum_{i=1}^{m-n}{m!\over{i!(m-i)!}}{1\over2^m}$$

The answer to part 1 is:

$${P(\ge{n})\over{P(\ge{n})+P(\le0)}}=\lim_{m\to\infty}{{\sum_{i=1}^{m-n}{m!\over{i!(m-i)!}}{1\over2^m}}\over{\sum_{i=1}^{m-n}{m!\over{i!(m-i)!}}{1\over2^m}+\sum_{i=1}^{\lceil{m\over2}\rceil-k}{m!\over{i!(m-i)!}}{1\over2^m}}}$$

$$=\lim_{m\to\infty}{{\sum_{i=1}^{m-n}{m!\over{i!(m-i)!}}}\over{\sum_{i=1}^{m-n}{m!\over{i!(m-i)!}}+\sum_{i=1}^{\lceil{m\over2}\rceil-k}{m!\over{i!(m-i)!}}}}$$

This can be forther simplified for the cases $m-n\gt{\lceil{m\over2}\rceil-k}$,$m-n={\lceil{m\over2}\rceil-k}$ ($1\over2$) and $m-n\lt{\lceil{m\over2}\rceil-k}$, note that these cases are symetrical.

The answer to part 2, is to find $m$ such that

$${\sum_{i=1}^{m-n}{m!\over{i!(m-i)!}}{1\over2^m}+\sum_{i=1}^{\lceil{m\over2}\rceil-k}{m!\over{i!(m-i)!}}{1\over2^m}}={1\over2}$$