確率論の問題

方針. $S_{n+1}=S_n+{\xi }_{n+1}$ と書き、$S_n$ と ${\xi }_{n+1}$ の独立性を使って $E|S_{n+1}|$ を $S_n$ の値ごとに分解する。そのうえで、整数 $s$ についての初等的な等式 $\frac{|s+1|+|s-1|}{2}=|s|+1_{\{s=0\}}$ を使う。

ステップ 1（整数についての等式）. すべての整数 $s$ に対して
$$\frac{|s+1|+|s-1|}{2}=|s|+1_{\{s=0\}}(1)$$
が成り立つことを示す。場合分けする。
- $s\ge 1$ のとき: $s+1>0$, $s-1\ge 0$ なので左辺は $\frac{(s+1)+(s-1)}{2}=s=|s|$ であり、$1_{\{s=0\}}=0$ なので右辺も $|s|$ である。
- $s\le -1$ のとき: $s+1\le 0$, $s-1<0$ なので左辺は $\frac{-(s+1)-(s-1)}{2}=-s=|s|$ であり、右辺も $|s|$ である。
- $s=0$ のとき: 左辺は $\frac{1+1}{2}=1$、右辺は $0+1=1$ である。
以上で $(1)$ がすべての整数 $s$ で成り立つ。

ステップ 2（独立性による分解）. $n\ge 0$ を固定する。$S_n$ は ${\xi }_1,\dots ,{\xi }_n$ の関数であり（$n=0$ なら定数 $0$）、${\xi }_{n+1}$ は ${\xi }_1,\dots ,{\xi }_n$ と独立なので、$S_n$ と ${\xi }_{n+1}$ は独立である。また $S_n$ は有限集合 $V_n=\{-n,-n+2,\dots ,n\}$ に値をとる整数値確率変数である。

$S_{n+1}=S_n+{\xi }_{n+1}$ であり、$(S_n,{\xi }_{n+1})$ のとりうる値は有限個なので、
$$E[|S_{n+1}|]=\sum _{s\in V_n}\sum _{e\in \{1,-1\}}|s+e|P(S_n=s,{\xi }_{n+1}=e).$$
独立性より $P(S_n=s,{\xi }_{n+1}=e)=P(S_n=s)P({\xi }_{n+1}=e)=\frac{1}{2}P(S_n=s)$ なので
$$E[|S_{n+1}|]=\sum _{s\in V_n}P(S_n=s)\frac{|s+1|+|s-1|}{2}.(2)$$

ステップ 3（まとめ）. $(2)$ に $(1)$ を代入すると（$V_n$ の元は整数なので $(1)$ が使える）
$$E[|S_{n+1}|]=\sum _{s\in V_n}P(S_n=s)|s|+\sum _{s\in V_n}P(S_n=s)1_{\{s=0\}}=E[|S_n|]+P(S_n=0).$$
ここで第 2 項は、$0\in V_n$ なら $P(S_n=0)$、$0\notin V_n$（$n$ が奇数のとき）なら $0=P(S_n=0)$ であり、いずれにしても $P(S_n=0)$ に等しい。どの期待値も有限和なので有限であり、移項してよい。

結論. すべての整数 $n\ge 0$ に対して $E[|S_{n+1}|]-E[|S_n|]=P(S_n=0)$ が成り立つ。$■$