ランダムウォーク不等式(仮)

はじめに

　この記事は前の記事( k-ナッチ数列の四捨五入表示の確率論的導出 )を書くにあたって触れた漸化式と確率論から不等式を導く理論がふと一般化できるんじゃないかと思い立って書いてみたものになります。
　具体的には以下のように主張に拡張してみました。

　数列 ${a_{n}}_{n = 1}^{\infty}$ が漸化式
$a_{n} = \sum_{k = k_{0}}^{k_{1}} p_{k} a_{n + k} (k_{0} < 0, p_{k} \geq 0, \sum_{k = k_{0}}^{k_{1}} p_{k} = 1)$
および
$\underset{n \to \infty}{lim sup} | a_{n} | < + \infty$
を満たすとき
$\begin{aligned} K & = max {k_{1}, 0} - k_{0} \\ A & = max {| a_{1} |, | a_{2} |, \dots, | a_{K} |} \end{aligned}$
とおくと任意の $n$ に対し
$| a_{n} | \leq A$
が成り立つ。

　これはランダムウォークの議論から成り立つ不等式なのでとりあえず安直にランダムウォーク不等式とでも呼ぶことにしました。
　 $K$ の設定が少しややこしいですが本質的には負のべきを許した多項式 $\sum_{k = k_{0}}^{k_{1}} p_{k} x^{k} - 1$ の次数っぽいものと考えればいいと思います。また $K$ の取り方は以下のように少し強くすることができます。

　方程式
$\sum_{k = k_{0}}^{k_{1}} p_{k} x^{k} - 1 = 0$
の絶対値 $1$ 未満の解を $α_{1}, a_{2}, \dots, α_{l}$ 、そのそれぞれの重複度を $m_{1}, m_{2}, \dots, m_{l}$ 、そして絶対値 $1$ の解の個数(重複は含めない)を $m$ とおくとランダムウォーク不等式は
$K = m + m_{1} + m_{2} + \dots + m_{l}$
としても成り立つ。

ランダムウォーク問題

　今回考えるランダムウォークの問題設定は前の記事とほとんど同じです。

　ある人が $x$ 軸上の非負整数点 $x = n$ に立っており、この人は $p_{k}$ の確率で $x$ 軸正の方向に $k$ だけ進むという動作を区間 $[1 : K]$ に至るまで無限に繰り返す。
　そしてこの人が止まった点 $x = j (1 \leq j \leq K)$ に到達したとき得点 $e (j)$ を得るものとする。

　このときこの人が得る得点の期待値 $e_{n}$ 、つまりこの人が $x = j$ に止まる確率 $p_{n}^{(j)}$ について
$e_{n} = p_{n}^{(1)} e (1) + p_{n}^{(2)} e (2) + \dots + p_{n}^{(K)} e (K)$
と定められる値 $e_{n}$ が $a_{n}$ と同じ性質を満たすことを示します(ちなみに $k_{0} \geq 0$ においてこの人は負の方向に進まなくなるのでこの手法は使えません)。

　 $e_{n}$ は漸化式
$e_{n} = \sum_{k = k_{0}}^{k_{1}} p_{k} e_{n + k}$
を満たす。

　いま $x = n$ からスタートして一回目の動作で $p_{k}$ の確率で $x = n + k$ の位置に進み、そこから $x = j$ に至る確率はそれぞれ $p_{n + k}^{(j)}$ であることから漸化式
$p_{n}^{(j)} = \sum_{k = k_{0}}^{k_{1}} p_{k} p_{n + k}^{(j)}$
が成り立つので $e_{n}$ についても同じ漸化式が成り立つことになる。

　さてこの漸化式から方程式
$\sum_{k = k_{0}}^{k_{1}} p_{k} x^{k} - 1 = 0$
の解を $x = α_{1}, \dots, α_{l^{'}}$ 、そのそれぞれの重複度を $m_{1}, \dots, m_{l^{'}}$ とおくと $e_{n}$ の一般項は
$e_{n} = f_{1} (n) α_{1}^{n} + \dots + f_{l^{'}} (n) α_{l^{'}}^{n} (f_{k} (n) \in C [n], \deg f_{k} < m_{k})$
と表せることがわかる。
　このとき $e_{n}$ の取り方からいくつかの項を取り除けるできることを示そう。

　 $e_{n}$ の一般項は
$e_{n} = c_{1} ζ_{1}^{n} + \dots + c_{m} ζ_{m}^{n} + f_{1} (n) α_{1}^{n} + \dots + f_{l} (n) α_{l}^{n}$
のように表せる。ただし $ζ_{1}, \dots, ζ_{m}$ は絶対値 $1$ の解、 $α_{1}, \dots, α_{l}$ は絶対値 $1$ 未満の解とした。

　いま $p_{n}^{(j)}$ は確率なので $0 \leq p_{n}^{(j)} \leq 1$ を満たすことに注意すると $e_{n}$ は有界、特に $e_{n}$ は $n \to \infty$ において発散する項を持ってはならないことになる。そして

$| α | > 1$ において $| f (n) α^{n} | \to \infty$
$| α | = 1$ において $| n α^{n} | \to \infty, | α^{n} | \to 1$
$| α | < 1$ において $| f (n) α^{n} | \to 0$

が成り立つことに注意すると主張を得る。

不等式の導出

　いま $e_{n}$ と $a_{n}$ は同じ漸化式を満たし、また仮定より $a_{n}$ も有界であるので $a_{n}$ も補題3と同じ主張が成り立つことになる。特に $a_{n}, e_{n}$ の一般項の自由度は $ζ_{k}^{n}$ の係数と $f_{k} (n)$ の係数の計 $K = m + m_{1} + \dots + m_{l}$ 個であり、したがって $K$ 個の点 $j$ における値 $a_{j}, e_{j}$ から一般の点 $n$ における値 $a_{n}, e_{n}$ を決定することができる。
　いま $e_{n} = a_{n}$ としたい。そのためには
$e_{j} = a_{j} (1 \leq j \leq K)$
が成り立てばよく、また $p_{j}^{(j)} = 1$ つまり $e_{j} = e (j)$ であったことから $e (j) = a_{j}$ とすればよい。
　このとき
$A = max {| a_{1} |, | a_{2} |, \dots, | a_{K} |}$
とおくと
$\begin{aligned} | a_{n} | = | e_{n} | & = | \sum_{j = 1}^{K} p_{n}^{(j)} e (j) | \\ \leq \sum_{j = 1}^{K} p_{n}^{(j)} | a_{j} | \leq A \sum_{j = 1}^{K} p_{n}^{(j)} = A \end{aligned}$
が成り立つことがわかる。

　また上の議論は
$K \geq m + m_{1} + \dots + m_{l}$
であれば成り立つのでその値として方程式 $\sum_{k = k_{0}}^{k_{1}} p_{k} x^{k} - 1 = 0$ の重複度込みの解の個数として
$K = max {k_{1}, 0} - k_{0}$
を採用してもよい。