$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!
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.