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

はじめに

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

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

ランダムウォーク問題

今回考えるランダムウォークの問題は 前の記事 とほとんど同じです。
　ある人が$x$軸上の非負整数点$x=n$に立っています。この人は$k_0\leq k\leq k_1$に対して$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)+\cdots+p_n^{(K)}e(K)$
と定められる値$e_n$が$a_n$と同じ性質を満たすことを示します。
(ちなみに$k_0\geq0$においてこの人は負の方向に進まなくなるのでこの手法は使えないです。)

さてこの漸化式から方程式$\sum^{k_1}_{k=k_0}p_kx^{k}-1=0$の解を$x=\a_1,\ldots,\a_{l'}$、そのそれぞれの重複度を$m_1,\ldots,m_{l'}$とおくと$e_n$の一般項は
$e_n=f_1(n)\a_1^n+\cdots+f_{l'}(n)\a_{l'}^n\quad(f_k(n)\in\mathbb{C}[n],\deg f_k< m_k)$
と表されることになる。このとき$e_n$の取り方からいくつかの項を削除できることを示そう。

不等式の導出

いま$e_n$と$a_n$は同じ漸化式を満たし、また仮定より$a_n$も有界であるので$a_n$も補題3と同じ主張が成り立つことになる。
また$a_n,e_n$の一般項を決定するには$\z_k^n$の係数と$f_k(n)$の係数の計$m+m_1+\cdots+m_l$個の未知数がわかればよいので
$e_n=a_n\quad(1\leq n\leq m+m_1+\cdots+m_l)$
であれば常に$e_n=a_n$が成り立つことになる。

ところで$p_j^{(j)}=1$であったので$e_j=e(j)$つまり$K=m+m_1+\cdots+m_l$とおくと$e(j)=a_j$とすればよい。よって$A=\max\{|a_1|,|a_2|,\ldots,|a_{K}|\}$について
$\dis|a_n|=|e_n|\leq\sum^K_{j=1}p_j|a_j|\leq A\sum^K_{j=1}p_j=A$
が成り立つことになる。

また上の議論は$K\geq m+m_1+\cdots+m_l$であれば成り立つのでその値として方程式$\sum^{k_1}_{k=k_0}p_kx^k-1=0$の重複度込みの解の個数として
$\dis K=\left\{\begin{array}{cl}-k_0&(k_1\leq0)\\k_1-k_0&(k_1>0)\end{array}\right.$
を採用してもよい。