2
$\begingroup$

I have to simulate the following game

Suppose that two players A and B each start with a stake of \$5, and bet \$0.5 on consecutive coin flips. The game ends when either one of the players has won all the money, that amounts to \$10. Let $S_n$ be the fortune of player A at time n. Then $\{S_n, n \gt 0 \}$ is a symmetric random walk with absorbing barriers at 0 and 10. Estimate $E[S_n]$ and $V[S_n]$ for $n = 50$.

I made a program and that's ok. Now I would to compare my results with the theoretical values. I don't know almost anything in probability, so that's just a curiosity. My question is

Which are the values of $E[S_n]$ and $V[S_n]$ in general? And for $n = 50$?

If there's no closed form, I will appreciate also an approximation (I got $E[S_n] \approx 5$ and $V[S_{50}] \approx 4.8$)

Thanks in advance.

$\endgroup$
9
  • $\begingroup$ If you have simulated, I'm sure you can guess the (very simple) value of $E[S_n]$. The proper way to simulate that is to run multiple (say, 10000 or more) experiments, get a time series for each experiment $i$ to obtain the vector $(S_0^{(i)}, S_1^{(i)}, S_2^{(i)}, ..., S_{100}^{(i)})$, average those values and plot the averaged values $\frac{1}{10000}\sum_{i=1}^{10000}S_n^{(i)}$ versus $n \in \{0, 1, 2, ..., 100\}$. $\endgroup$
    – Michael
    Commented Nov 22, 2018 at 15:25
  • $\begingroup$ Yes I did, but now I want to know the theoretical results $\endgroup$
    – CNS709
    Commented Nov 22, 2018 at 15:34
  • $\begingroup$ So from those experiments you should be able to guess the value of $E[S_n]$ for each $n$ and your guess is... $\endgroup$
    – Michael
    Commented Nov 22, 2018 at 15:34
  • $\begingroup$ My guess is 5 but I want to know if it agrees with the theory $\endgroup$
    – CNS709
    Commented Nov 22, 2018 at 15:56
  • $\begingroup$ Yes $E[S_n]=5$ for all $n$ since this is a martingale, $S_{n+1} = S_n + A_n$ where $A_n=0$ if $S_n \in \{0, 10\}$ and $E[A_n|S_n]=0$ regardless the value of $S_n$. You might want to provide your simulated guesses for $E[S_{50}]$ and $Var(S_{50})$ in the question itself. Here I assume coin flips are independent and equally likely to be heads or tails. $\endgroup$
    – Michael
    Commented Nov 22, 2018 at 16:02

1 Answer 1

1
$\begingroup$

Modeling the process

Define $\mathcal{S}$ as the set of possible values for the Markov chain: $$\mathcal{S} = \{0, 0.5, 1, 1.5, …, 9.5, 10\}$$ Note that $S_0=5$ and $S_n \in \mathcal{S}$ for all $n \in \{0, 1, 2, …\}$. We have $$S_{n+1} = S_n + A_n \quad \forall n \in \{0, 1, 2, ...\} $$ where $$ A_n = \left\{ \begin{array}{ll} (1/2)B_n &\mbox{ if $S_n \notin \{0, 10\}$} \\ 0 & \mbox{ otherwise} \end{array} \right.$$ where $\{B_n\}_{n=0}^{\infty}$ is an i.i.d. sequence with $P[B_n=1]=P[B_n=-1]=1/2$. Then $$\boxed{E[A_n|S_n=s] = 0 \quad, \forall s \in \mathcal{S}} \quad (Eq. 1) $$


Mean

So for each $n \in \{0, 1, 2, ...\}$ we have \begin{align} E[S_{n+1}] &\overset{(a)}{=} \sum_{s \in \mathcal{S}}E[S_{n+1}|S_n=s]P[S_n=s] \\ &\overset{(b)}{=} \sum_{s \in \mathcal{S}}E[S_n + A_n|S_n=s]P[S_n=s] \\ &= \sum_{s \in \mathcal{S}}E[s + A_n|S_n=s]P[S_n=s] \\ &= \sum_{s \in \mathcal{S}}(s + E[A_n|S_n=s])P[S_n=s] \\ &\overset{(c)}{=} \sum_{s \in \mathcal{S}}sP[S_n=s] \\ &\overset{(d)}{=} E[S_n] \end{align} where (a) holds by the law of total expectation; (b) holds by the fact $S_{n+1}=S_n+A_n$; (c) holds by Eq. (1); (d) holds by definition of expectation. Since $E[S_0]=5$ we conclude: $$\boxed{E[S_n]=5 \quad \forall n \in \{0, 1, 2, … \}}$$


Limiting variance

We know $E[S_n]=5$ for all $n$ and so $$Var(S_n) = E[(S_n-5)^2] = \sum_{s \in \mathcal{S}}(s-5)^2P[S_n=s] $$ Since the process is equally likely to end up at state $0$ or $10$ we have \begin{align} \lim_{n\rightarrow\infty} P[S_n=0] &= 1/2\\ \lim_{n\rightarrow\infty} P[S_n=10] &= 1/2\\ \lim_{n\rightarrow\infty} P[S_n=s] &= 0 \quad \forall s \notin \{0, 10\} \end{align} so $$ \boxed{\lim_{n\rightarrow\infty} Var(S_n) = (0-5)^2(1/2) + (10-5)^2(1/2) = 25} $$


Details on variance

Squaring the equation $S_{n+1} = S_n + A_n$ gives $$S_{n+1}^2 = (S_n+A_n)^2 = S_n^2 + 2S_nA_n + A_n^2 $$ So $$E[S_{n+1}^2|S_n] = S_n^2 + 2S_nE[A_n|S_n] + E[A_n^2|S_n] = S_n^2 + 0 + (1/4)1_{\{S_n \notin\{0, 10\}\}}$$ where $1_{\{S_n \notin\{0, 10\}\}}$ is an indicator function that is 1 if $S_n \notin \{0,10\}$ and is 0 else. So $$E[S_{n+1}^2] = E[S_n^2] + (1/4)P[S_n \notin \{0,10\}]$$ Subtracting 25 from both sides gives $$ Var(S_{n+1}) = Var(S_n) + (1/4)P[S_n \notin \{0,10\}]$$ and $Var(S_0)=0$ so $$ \boxed{Var(S_n) = (1/4)\sum_{i=0}^{n-1} P[S_i \notin \{0,10\}] \quad \forall n\in \{1, 2, 3, ...\} } $$ Since $P[S_i \notin \{0,10\}] = 1$ for $i \in \{0, 1, 2, 3, ..., 9\}$ we have $$\boxed{Var(S_1)=1/4, Var(S_2)=2/4, Var(S_3) = 3/4, ..., Var(S_{10})= 10/4}$$ On the other hand: $$ Var(S_{11}) = 10/4 + (1/4)\underbrace{(1-2(1/2)^{10})}_{P[S_{10}\notin\{0,10\}]}$$ In general, the variance increases as $n\rightarrow\infty$ to approach a limiting value of $25$. It is possible to compute $P[S_i \notin \{0,10\}]$ for all $i$ (for example, by taking powers of a transition probability matrix), but this calculation is more involved.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .