2

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

34
0
$$\newcommand{a}[0]{\alpha} \newcommand{b}[0]{\beta} \newcommand{dis}[0]{\displaystyle} \newcommand{z}[0]{\zeta} $$

はじめに

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

数列$\{a_n\}_{n=1}^\infty$が漸化式
$\dis a_n=\sum^{k_1}_{k=k_0}p_ka_{n+k}\quad(k_0<0,\;p_k\geq0,\;\sum^{k_1}_{k=k_0}p_k=1)$
および
$\dis\limsup_{n\to\infty}|a_n|<+\infty$
を満たすとき、$\dis K=\left\{\begin{array}{cl}-k_0&(k_1\leq0)\\k_1-k_0&(k_1>0)\end{array}\right.$および$A=\max\{|a_1|,|a_2|,\ldots,|a_{K}|\}$とおくと任意の$n$
$|a_n|\leq A$
が成り立つ。

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

方程式$\sum^{k_1}_{k=k_0}p_kx^k-1=0$の絶対値$1$未満の解を$\a_1,a_2,\ldots,\a_l$そのそれぞれの重複度を$m_1,m_2,\ldots,m_l$、そして絶対値$1$の解の個数を$m$とおくとランダムウォーク不等式は
$K=m+m_1+m_2+\cdots+m_l$
としても成り立つ。

ランダムウォーク問題

今回考えるランダムウォークの問題は 前の記事 とほとんど同じです。
 ある人が$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$においてこの人は負の方向に進まなくなるのでこの手法は使えないです。)

漸化式$e_n=\sum^{k_1}_{k=k_0}p_ke_{n+k}$が成り立つ。

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

さてこの漸化式から方程式$\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$の一般項は$\z_1^n,\ldots,\z_m^n$の線形結合と$\a_1,\ldots,\a_l$の項からなる。
ここで$\z_1,\ldots,\z_m$は絶対値$1$の解、$\a_1,\ldots,\a_l$は絶対値$1$未満の解とした。

いま$p_n^{(j)}$は確率、つまり$0\leq p_n^{(j)}\leq1$であったことに注意すると$e_n$は有界であり、$e_n$は発散する項を持ってはならないことになる。そして
$|\a|>1$において$|f(n)\a^n|\to\infty\;(as\;n\to\infty)$
$|\a|=1$において$|n\a^n|\to\infty\;(as\;n\to\infty)$$|\a^n|\to1\;(as\;n\to\infty)$
$|\a|<1$において$|f(n)\a^n|\to0\;(as\;n\to\infty)$
であることに注意すると主張を得る。

不等式の導出

いま$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.$
を採用してもよい。

投稿日:2021111

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

子葉
子葉
788
149356
主に複素解析、代数学、数論を学んでおります。 私の経験上、その証明が簡単に探しても見つからない、英語の文献を漁らないと載ってない、なんて定理の解説を主にやっていきます。 同じ経験をしている人の助けになれば。最近は自分用のノートになっている節があります。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中