Say you have a simple random walk starting at 0.
$$S_n=X_1+…+X_n,\quad S_0=0$$
where $\mathbb P(X_i=\pm 1)=\frac{1}{2}$.
From what I understand, which intuitively makes a lot of sense, the following is true:
$$\mathbb E(T_k) = k \mathbb E(T_1) $$
where $T_k$ and $T_1$ are the times where the walker reaches $k$ and $1$, i.e. $S_n=k$ and $S_n=1$, respectively.
I am trying to find a proof for the above equation or pinpoint the properties of the random walk that make it true. Is it just a combination of memorylessness and symmetry?
Thank you.
Also, a question about the terminology. Does $\mathbb E(T_k) = k \mathbb E(T_1)$ imply linearity of expectation? I put "linear" in quotes in the title as I was unsure if it is true. Please edit if necessary.
Best Answer
Consider increments s.t. $P(X_1=1)=p>1/2$. Then $E[X_1]=p-(1-p)=2p-1$ and $Y_n=S_n-n(2p-1)$ is a martingale. Define $\tau_k=\inf\{u:S_u=k\},\,k>0$. We get $$\underbrace{0}_{=Y_0}=E[Y_{\tau_k\wedge n}]=E[S_{\tau_k\wedge n}-(\tau_k\wedge n)(2p-1))\leq k-E[\tau_k\wedge n](2p-1)\stackrel{\textrm{MCT}}{\implies} E[\tau_k]\leq \frac{k}{2p-1}<\infty$$ where $\tau_k\wedge n=\min(\tau_k,n)$. We showed $E[\tau_k]<\infty$ and the increments of the martingale are bounded, so we can use OST and obtain $$0=E[k-\tau_k(2p-1)]\implies E[\tau_k]=\frac{k}{2p-1}\stackrel{p\to 1/2}{\to}\infty$$ So if $p=1/2$ we have $E[\tau_k]=\infty,\,\forall k>0$. So if $p=1/2$ the claim is true in the sense that $\infty=\infty$. However, if $p>1/2$ indeed we have $$E[\tau_k]=\frac{k}{2p-1}=kE[\tau_1]$$