Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
This is a random walk problem - search for that. –  Dale M Jan 13 '13 at 20:19
    
The probability of winning $n$ dollars is $0$ unless $k=0$, because the most that can be won is $n-k$. Perhaps you mean to ask for the probability of reaching a total of $n$ dollars? –  whuber Jan 13 '13 at 20:49
    
Yes, I mean the probability of reaching a total of $n$ dollars. I didn't make it clear, sorry for that. –  xan Jan 13 '13 at 21:05

2 Answers 2

up vote 1 down vote accepted

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)$$

share|improve this answer

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}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.