公式解説で行間があると指摘されている部分について補足します．

\(\{0,1,\ldots,M\}\) を \(0\) を出発してランダムウォークする（端点からは確率 1 で内側へ，他の点からは左右 ¹⁄₂ ずつ）ときに，\(0\) を出発して \(M\) に到達するまでの移動回数の期待値を求めます．

• 有向辺 \(i\to (i+1)\) を通る回数の期待値を \(a_i\)
• 有向辺 \((i+1)\to i\) を通る回数の期待値を \(b_i\)

とします．各点に入る辺・出る辺のつり合いを考えれば，

• \(a_0=b_0+1\)
• \(1\leq i\leq M-1\) に対して \(a_i+b_{i-1}=a_{i-1}+b_{i}\)
• \(a_{M-1}=1,b_{M-1}=0\)

となります．また，始点を固定すると有向辺を使う回数期待値は出る辺によらない（これはその点に訪れるたびに等確率で辺を選ぶため）ので，\(a_i=b_{i-1}\) という条件も成り立ちます．

あとは \(i\) が大きい方から決めていくと，

• \(a_i = M-i\)
• \(b_i = M-1-i\)

と決まって，これらの総和 \(M^2\) が移動回数の期待値となります．