ランダムウォークの基礎（一次元，高校範囲）

$n$ 回のうち $k$ 回プラスに移動し，$n-k$ 回マイナスに移動したとすると，$n$ ステップ後の位置は $k-(n-k)=2k-n$

これが $x$ と等しくなるとき $k=\dfrac{n+x}{2}$

• $n+x$ が奇数のとき
  上記のような $k$ は存在しないので求める確率は $0$

• $n+x$ が偶数のとき
  $n$ 回の試行で $\dfrac{n+x}{2}$ 回プラスに移動する確率は，反復試行の確率の考え方より $\dfrac{1}{2^n}\cdot{}_n\mathrm{C}_{\frac{n+x}{2}}$

条件を満たす経路の数を数える。

• 最初にプラスに移動した場合
  「$(2n-1)$ ステップ目まで原点を通らない」かつ「$(2n-1)$ ステップ後にプラス1の位置にいる」ような移動方法の数はカタラン数 $c_{n-1}=\dfrac{1}{n}{}_{2n-2}\mathrm{C}_{n-1}$ である。→カタラン数の意味と漸化式

• 最初にマイナスに移動した場合
  対称性より同様に $c_{n-1}$ 通り。
  よって，求める確率は $\dfrac{2c_{n-1}}{2^{2n}}=\dfrac{{}_{2n-2}\mathrm{C}_{n-1}}{n2^{2n-1}}$