Conditional expectation of standard random walk conditioned on its position at a given future time

Question

Suppose $\{X_i\}_{i=1}^{\infty}$ is i.i.d. with $P(X_i=1)=p$ and $P(X_i=-1)=1-p$. Let $Y_n=\sum\limits_{i=1}^{n} X_i$. We want to compute $E[Y_m|Y_n]$ for $m<n$.

Thus, we know the future and want to find an expectation in the past. Here is what I think:

It's clear that $$E[Y_m|Y_n=n]=\frac{m}{n}n=m$$ since if $Y_n=n$, $Y_m$ has to be $ m$, otherwise it will not get to $n$ at time $n$.

I guess when $p=\frac{1}{2}$, $$E[Y_m|Y_n]=\frac{m}{n}Y_n$$ though I'm not sure. I don't know whether the result will change when $p\neq \frac{1}{2}$, either. And I think the following is true (assuming $j\leq n$): $$ P(Y_m=i|Y_n=j)=\frac{P(Y_m=i,Y_n=j)}{P(Y_n=j)}=\frac{P(Y_m=i)P(Y_{n-m}=j-i)}{P(Y_n=j)} $$ Then $$E[Y_m|Y_n=j]=\sum_{i=j-(n-m)}^{j+(n-m)} iP(Y_m=i|Y_n=j) = \frac{1}{{P(Y_n=j)}} \sum_{i=j-(n-m)}^{j+(n-m)} [iP(Y_m=i)P(Y_{n-m}=j-i)]$$ but it is still so complicated to me.

Finally, I also thought about using mathematical induction or iteration, but couldn't make it work.

Answer 1

1. The situation might be easier to picture for the (nondecreasing) random walk $$W_n=\sum_{i=1}^nZ_i$$ where $(Z_i)_{i\geqslant1}$ is i.i.d. with $P(Z_i=1)=p$ and $P(Z_i=0)=1-p$. To wit, note that $W_n$ is the size of the random set $$I_n=\{i\in[n]\mid Z_i=1\}$$ with the notation $[n]=\{1,\ldots,n\}$. Furthermore, for every $J\subseteq[n]$ of size $k$, $$P(I_n=J)={n\choose k}p^k(1-p)^{n-k}$$ does not depend on $J$ except through its size $k$ hence:

Conditionally on $\{W_n=k\}$, the random set $I_n$ is uniformly distributed on the collection of subsets of $[n]$ of size $k$.

In particular, by exchangeability, $$P(i\in I_n\mid W_n=k)$$ does not depend on $i$ in $[n]$.

2. As a first consequence, the fact that $$\sum_{i=1}^nP(i\in I_n\mid W_n=k)=E(W_n\mid W_n=k)=k$$ implies that, for every $i$ in $[n]$, $$P(i\in I_n\mid W_n=k)=\frac{k}n$$ In turn, this identity implies that, for every $m$ in $[n]$, $$E(W_m\mid W_n=k)=\sum_{i=1}^mP(i\in I_n\mid W_n=k)=\frac{mk}n$$

3. To come back to your setting, note that the processes $(X_i)_{i\geqslant1}$ and $(2Z_i-1)_{i\geqslant1}$ are identically distributed hence the processes $(Y_n)_{n\geqslant1}$ and $(2W_n-n)_{n\geqslant1}$ are identically distributed. In particular, for every $k$ such that $|k|\leqslant n$ and $k+n$ is even, $$E(Y_m\mid Y_n=k)=2E(W_m\mid W_n=\tfrac12(k+n))-m=2\frac{m\tfrac12(k+n)}n-m$$ that is,

$$E(Y_m\mid Y_n=k)=\frac{mk}n$$

To conclude, your conjecture is confirmed and, indeed, the result does not depend on $p$ in $(0,1)$.