k-ナッチ数列の四捨五入表示の確率論的導出

はじめに

　前回の記事では apu_yokai 氏の記事に触発されk-ナッチ数列の四捨五入表示の確かさをその一般項の公式から直接考察し、その後apu_yokai氏による

フィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想(その4・証明完成)

の記事をもって完全解決に至りましたが、少し引っかかる点がありました。
　というのもapu_yokai氏が立てた予想がWikipediaに2008年付の出典付きで既に紹介されていたわけなのです。

私も初めその出典を見たとき書いてある内容が不十分に見えて、まーたWikipediaがいい加減な出典拾ってきたのかと半信半疑でしたが、今一度よくよく見てみると確かに四捨五入表示の導出になっていそうだということがわかってきたので私なりに言葉を付け足しつつその内容をまとめようと思います。
　ざっくりとその内容を説明するととあるランダムウォークの問題を考えそれに対する期待値 $e_{n}$ を考えます。するとその期待値 $e_{n}$ が漸化式 $e_{n + 1} = 2 e_{n} - e_{n - k}$ を満たすことがわかり、問題の条件を適当に設定することで $e_{n}$ がk-ナッチ数 $a_{n}$ と $α^{n} / f^{'} (α)$ との誤差とみなせることを示します。そして $e_{n}$ の確率的な解釈から $| e_{n} | < 1 / 2$ であることがわかり四捨五入表示問題の解決となります。

ランダムウォーク問題

問題設定

　最初に $x$ 軸上の非負整数点 $x = n$ に人が立っており、この人は $\frac{1}{2}$ の確率で $x$ 軸正の方向に $1$ 進み、 $\frac{1}{2}$ の確率で負の方向に $k$ 進むという動作を区間 $[0, k - 1]$ 内に至るまで無限に繰り返す。
　そしてその人が止まった点 $x = j (0 \leq j \leq k - 1)$ に応じてその人は得点 $e (j)$ を得るものとする。

　このときその人が得る得点の期待値 $e_{n}$ 、つまりその人が点 $x = j$ に止まる確率 $p_{n}^{(j)}$ について
$e_{n} = p_{n}^{(0)} e (0) + p_{n}^{(1)} e (1) + \dots + p_{n}^{(k - 1)} e (k - 1)$
と定められる値 $e_{n}$ が上述のような性質を満たすことを示します。

　漸化式 $e_{n + 1} = 2 e_{n} - e_{n - k}$ が成り立つ。

　各 $j$ に対して $p_{n + 1}^{(j)} = 2 p_{n}^{(j)} - p_{n - k}^{(j)}$ が成り立つことを言えばよい。
　いま $x = n$ からスタートして一回目の動作でそれぞれ $\frac{1}{2}$ の確率で $x = n + 1$ または $x = n - k$ の位置に進み、そこから $x = j$ に至る確率はそれぞれ $p_{n + 1}^{(j)}, p_{n - k}^{(j)}$ なので
$p_{n}^{(j)} = \frac{p_{n + 1}^{(j)} + p_{n - k}^{(j)}}{2}$
つまり $p_{n + 1}^{(j)} = 2 p_{n}^{(j)} - p_{n - k}^{(j)}$ を得る。

　さてこの漸化式から方程式
$\frac{x^{k + 1} - 2 x^{k} + 1}{x - 1} = 0$
の解を $β_{1}, β_{2}, \dots, β_{k}$ とおくと $e_{n}$ および $p_{n}^{(j)}$ の一般項は $1, β_{1}^{n}, β_{2}^{n}, \dots, β_{k}^{n}$ の線形結合で表されることがわかる。ここで $β_{k} = α$ を唯一の正の実数解とするとそれらの線形結合において $α^{n}$ の係数が $0$ であることを示そう。

　 $e_{n}$ の一般項は $1, β_{1}^{n}, β_{2}^{n}, \dots, β_{k - 1}^{n}$ の線形結合で表される。

　いま $| β_{i} | < 1 (1 \leq i < k)$ および $1 < α$ に注意すると、 $p_{n}^{(j)}$ における $α^{n}$ の係数が $0$ でないとすると $n \to \infty$ において $p_{n}^{(j)}$ は正か負の無限大に発散することになるが $p_{n}^{(j)}$ は確率なので $0 \leq p_{n}^{(j)} \leq 1$ であることに矛盾。よって $p_{n}^{(j)}$ ひいては $e_{n}$ における $α^{n}$ の係数は $0$ であり主張を得る。

四捨五入表示の導出

　いま得点 $e (j)$ の値については特に定めてなかったので、 $a_{n}$ をk-ナッチ数列、 $f (x)$ を $f (x) = \frac{x^{k + 1} - 2 x^{k} + 1}{x - 1}$
とし $e (j)$ を
$e_{n} = a_{n} - \frac{α^{n}}{f^{'} (α)} (n = 0, 1, 2, \dots, k - 1)$
となるように定めることにする。具体的には $p_{j}^{(j)} = 1$ より $e_{j} = e (j)$ なので
$e (j) = a_{j} - \frac{α^{j}}{f^{'} (α)}$
とすればよい。
　このとき $e_{n}$ の一般項を
$e_{n} = c_{0} + c_{1} β_{1}^{n} + c_{2} β_{2}^{n} + \dots + c_{k - 1} β_{k - 1}^{n}$
と表すと $c_{0}, c_{1}, \dots, c_{k - 1}$ についての $k$ 個の方程式
$e_{n} = a_{n} - \frac{α^{n}}{f^{'} (α)} = \sum_{j = 1}^{k - 1} \frac{β_{j}^{n}}{f^{'} (β_{j})} (n = 0, 1, 2, \dots, k - 1)$
から $c_{0} = 0, c_{j} = \frac{1}{f^{'} (β_{j})}$ つまり $k \leq n$ においても常に
$e_{n} = \sum_{j = 1}^{k - 1} \frac{β_{j}^{n}}{f^{'} (β_{j})} = a_{n} - \frac{α^{n}}{f^{'} (α)}$
が成り立つことがわかる。
　ところで前回の記事で示したように $0 \leq n < k$ において
$| e (n) | = | a_{n} - \frac{α^{n}}{f^{'} (α)} | < \frac{1}{2}$
が成り立つことがわかっているので $k \leq n$ においても
$| a_{n} - \frac{α^{n}}{f^{'} (α)} | = | e_{n} | \leq \sum_{j = 0}^{k - 1} p_{n}^{(j)} | e (j) | < \frac{1}{2} \sum_{j = 0}^{k - 1} p_{n}^{(j)} = \frac{1}{2}$
となることがわかる。