0
$\begingroup$

$X_1$, $X_2$, ... are i.i.d. random variables with distribution P($X_i$ = 1) = $\frac{2}{3}$, P($X_i$ = -1) = $\frac{1}{3}$. Let $$S_n = \sum_{i=1}^n X_i$$ For each integer k > 0, define $$T_k = min \left\{ n\geq 1: S_n = k \right\} $$ Then $E(T_k) = \frac{k}{2p-1} = 3k$

But I do not know how the result comes from. Can anyone give me any idea about how should I solve this problem? Thanks a lot!

$\endgroup$
0
$\begingroup$

You can use renewal theory to solve this problem. The idea is to compute $u(j)=E[T_k \mid S_0=j]$ for each $j=\dots,-1,0,1,\dots,k$. Then $u(0)$ is what you want to find and $u(k)=0$. Then you also have the recursion relation $u(j)=1+2/3 u(j+1)+1/3 u(j-1)$ for $j<k$.

At the moment you still have a problem, because this is a second order recurrence relation and you only have one boundary condition. The solution is to approximate $u$ along a sequence $u_n$ with the artificial boundary condition $u_n(-n)=0$. These $u_n$'s can be computed and then you can send $n \to \infty$ to obtain the desired result.

$\endgroup$
  • $\begingroup$ Thank you very much! Could you please explain how I can get the recursion relation? Is it because when the sum of Xi's is j, then it has a probability of 2/3 that the sum of Xi's becomes j+1, and the probability that the sum becomes j-1 is 1/3. So u(j) = 2/3[u(j+1) +1] + 1/3[u(j - 1)+1]? $\endgroup$ – YYFFSS Sep 12 at 3:04
  • $\begingroup$ @YYFFSS Yes, that is where it comes from. $\endgroup$ – Ian Sep 12 at 10:09
  • $\begingroup$ Hi Ian, sorry for bothering you again, could you please explain a little more about how to get the artificial boundary condition? what are Un's and why Un(-n)=0? Thank you sooo much! $\endgroup$ – YYFFSS Sep 13 at 4:53
  • $\begingroup$ @YYFFSS The point is that we can find the expected time to leave a bounded domain. You want the time to leave an unbounded domain (by hitting one endpoint). So you can take a bounded domain and move one endpoint to infinity and you will get the desired result. $\endgroup$ – Ian Sep 13 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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