直交多項式と超幾何関数(8)〜二項分布とKrawtchouk多項式(その1)〜

125

第八回目の今回からは
話がガラッと変わってしまう。

前回までにみたように、
2階常微分方程式を満たすような直交多項式は、
Jacobi、及びその極限であるLaguerre、Hermite、そしてBesselの4つに限られてしまう
という事実があった。
しかし、直交多項式はこれで全てなんていうことはない。
むしろ逆に、直交多項式になる三項間漸化式を満たしているものはどんなものでも直交多項式になる。

もう少し広いクラスの直交多項式はないのであろうか。

歴史的に見ると、2階ODE型の直交多項式の分類が終わる前から
それ以外の直交多項式はもちろん知られていた。
今回はそんな中の一つの例を挙げる。

離散直交多項式

そもそも今まで定義されていたものは、連続的な直交多項式と呼ばれるものに相当する。
すなわち関数同士の内積が、ある種の積分で定義されていた。
$\displaystyle \langle f(x), g(x)\rangle = \int_a^b f(x)g(x)w(x)dx$
となるような区間$[a, b]$とその上の重さ関数$w(x)$が知られていた。
しかし、よく考えたら
別に内積って積分である必要はない。

そもそも我々が内積と聞いて最も(現実的に)身近にあるものと言えば平面・空間ベクトルが挙げられるだろう。
その場合の内積は、積分ではなく、有限和であった。

区間$[a, b]$ではなく、有限個の点の上で定義された「離散的な」重さ関数$w(x)$を取ってくると
自然と内積は積分から有限和に変わることがわかる。

ということで、離散直交多項式を定義する。

離散直交多項式

$\mu$を$\mathbb{R}$上の離散測度とする。
すなわち、ある実数列$(s_n)_{n=1}^\infty$と非負実数列$(a_n)_{n=1}^\infty$に対し
\begin{align*} \mu=\sum_{n=1}^\infty s_n\delta_{a_n} \end{align*}
とディラックのデルタ関数の高々可算個の和で書けているものとする。
(超簡単に言うと、$x=s_n$のところで$\mu(x)=a_n$、それ以外で$\mu(x)=0$となる)
多項式列$\{P_n\}_{n=0}^\infty$が離散測度$\mu$に関する離散直交多項式(discrete orthogonal polynomial)であるとは、ある実数列$(\kappa_n)_{n=0}^\infty$が存在して、任意の$m, n\ge0$に対し以下の直交関係式
\begin{align*} \sum_{i=1}^\infty P_m(a_i)P_n(a_i)\mu(a_i) \left(=\sum_{i=1}^\infty s_iP_m(a_i)P_n(a_i)\right) =\kappa_n\delta_{mn} \end{align*}
を満たすこととする。

二項分布と直交多項式

確率$p$(ただし$0\le p\le 1$)で表が出るコインが$n$枚ある。
これらコイン$n$枚を同時に投げるとき、出る表の目の枚数を$X$とする。
この確率変数$X$がもたらす確率分布のことを二項分布と呼ぶ。

$0\le x\le n$とする。このとき$X=x$となる確率$p_n(x)$は
\begin{align*} p_n(x)=\binom{n}{x}p^x(1-p)^{n-x} \end{align*}
で与えられる。この確率の値が二項係数で与えられることから二項分布と名付けられている。

この二項分布を重さ関数とする直交多項式を考えてみたい。
すなわち関数$f(x)$と$g(x)$の内積を
\begin{align*} \langle f(x), g(x)\rangle = \sum_{x=0}^nf(x)g(x)p_n(x) \end{align*}
として定め、多項式の空間とこの内積に対してシュミットの直交化法を行うことを考える。

簡単な例：$n=3$のとき

このとき確率変数$X$の確率分布は次のようになる。

$x$	$p_3(x)$
$0$	$(1-p)^3$
$1$	$3p(1-p)^2$
$2$	$3p^2(1-p)$
$3$	$p^3$

ということで以下、二項分布から誘導される内積に関する$N$次元多項式での直交基底$P_N(X)$を確定する。

$N=0$のとき
$P_0(X)=1$ととりあえずできる。
(ここで$1$同士の内積が消えていないことに注意せよ：
$\mu(1)=(1-p)^3+3p(1-p)^2+3p^2(1-p)+p^3=1$が従う。)
$N=1$のとき
ここで$\mu(X)$を計算すると
$\mu(X)=0\cdot(1-p)^3+1\cdot 3p(1-p)^2+2\cdot 3p^2(1-p)+3\cdot p^3 = 3p$
となるので$\mu(X-3p)=0$となる。すなわち$P_1(X)=X-3p$
$N=2$のとき
同様に$\mu(X^2)$や$\mu(X^3)$を計算すると
$\mu(X^2) =0^2\cdot(1-p)^3+1^2\cdot 3p(1-p)^2+2^2\cdot 3p^2(1-p)+3^2\cdot p^3 = 6p^2+3p$
また$\mu(X^3)=6p^3+18p^2+3p$となる。
したがって、例えば$P_2(X)=X^2+aX+b$などと置き、$\mu(P_2(X))=0$と$\mu(P_1(X)P_2(X))=0$の式を考えると
$\mu(P_2(X))=0\Leftrightarrow 3pa + b = -6p^2-3p$
$\mu(P_1(X)P_2(X))=0 \Leftrightarrow (-3p^2+3p)a=12p^3-9p^2-3p$
以上を解くことで$P_2(X)=X^2-(4p+1)X+6p^2$を得る。
以下同様に計算すると
$P_3(X)=X^3-3(p+1)X^2+(6p^2+3p+2)X-6p^3$
$P_4(X)=X^4-6X^3+11X^2-6X$
となるが、$P_5(X)$より上の多項式は存在し得ない。ここで終わりである。

まとめると
\begin{align*} P_0(X)&=1 \\ P_1(X)&=X-3p \\ P_2(X)&=X^2-(4p+1)X+6p^2 \\ P_3(X)&=X^3-3(p+1)X^2+(6p^2+3p+2)X-6p^3 \\ P_4(X)&=X^4-6X^3+11X^2-6X \end{align*}
が基底となりそうな直交多項式である。（実は正しくないのですぐ後で訂正する）

$\underline{\text{Question}}$: $N\ge5$のとき何が起こっているのか？
これは簡単なことで、今の二項分布に関する内積は
\begin{align*} \mu(f(x))=f(0)(1-p)^3+f(1)3p(1-p)^2+f(2)3p^2(1-p)+f(3)p^3 \end{align*}
と$f(0)$から$f(3)$の4つの値で全て決まってしまう。
すなわちそれらを補間する3次以下の多項式で代表されてしまう。
(Lagrange補間多項式、記事(4)のガウス求積法のところを参照せよ)
・・・ではなぜ逆に$P_4(X)$が存在するのか？
よくよく見ると
$P_4(X)=X^4-6X^3+11X^2-6X=X(X-1)(X-2)(X-3)$
となっているので、$P_4(0)=P_4(1)=P_4(2)=P_4(3)=0$となっている。
あれ。多項式としてゼロで補間されるじゃん。

ということで、この$P_4(X)$は今後考えないことにする。意味がないし。

まとめると、$n=3$のときの二項分布に関する直交多項式列$\{P_N(X)\}$は
\begin{align*} P_0(X)&=1 \\ P_1(X)&=X-3p \\ P_2(X)&=X^2-(4p+1)X+6p^2 \\ P_3(X)&=X^3-3(p+1)X^2+(6p^2+3p+2)X-6p^3 \end{align*}
となっている。

Krawtchouk多項式

さて、$n=3$のときはいいんですけど、これ一般の$n$で考えましょうってときに
モーメント法はやっぱり現実的ではない。
Rodriguesの公式・・・は、ないわけではないんだけど、（遠い目）
いきなりそれを持ってくるのもやや天下り感。

ここは一般項を先に与えることとしよう。

二項分布$\displaystyle p_n(x)=\binom{n}{x}p^x(1-p)^{n-x}$に関し、$n$次以下の多項式の空間にシュミットの直交化法を行った多項式として、次に定義される クラウチューク(Krawtchouk)多項式 が取れる。

Krawtchouk polynomial

Krawtchouk多項式$\{k_N^{(n)}(X)\}_{0\le N\le n}$は次の$N$次多項式$k_N^{(n)}(X)$の列である。
\begin{align*} k_N^{(n)}(X):=\sum_{r=0}^N(-1)^{N-r}\binom{n-X}{N-r}\binom{X}{r}p^{N-r}(1-p)^r \end{align*}

一見わかりにくいが、二項係数部に変数$X$が入っていて、合計$(N-r)+r=N$回掛けられている$N$次多項式になっていることに注意する。また、最高次係数は$\frac{1}{N!}$である。(上の例とはズレがある)

$n=3$のときの確認

$n=3$のとき、$N=0, 1, 2, 3$として$k_N^{(n)}(X)$の値は
\begin{align*} k_0^{(3)}(X)&=1 \\ k_1^{(3)}(X)&=X-3p \\ k_2^{(3)}(X)&=\frac{1}{2}\{X^2-(4p+1)X+6p^2\} \\ k_3^{(3)}(X)&=\frac{1}{6}\{X^3-3(p+1)X^2+(6p^2+3p+2)X-6p^3\} \end{align*}
と確かに正規化を除いて上の実験結果と一致。

とりあえず今定めたKrawtchouk多項式$k_N^{(n)}(X)$が二項分布に関して直交していることを示す必要がある。

Krawtchouk多項式の直交性

上で定めた$\{k_N^{(n)}(X)\}_{0\le N\le n}$は、二項分布$\displaystyle p_n(x)=\binom{n}{x}p^x(1-p)^{n-x}$に関して直交する。
すなわち、$M< N$のとき$\displaystyle \sum_{X=0}^nk_M^{(n)}(X)k_N^{(n)}(X)p_n(X)=0$が成立する。
さらに二乗ノルムに関しては
\begin{align*} \sum_{X=0}^n\left\{k_N^{(n)}(X)\right\}^2p_n(X) =\binom{n}{N}p^N(1-p)^N \end{align*}
のように計算することができる。
(特に$0< p<1$においては二乗ノルムが正であるので正定値直交多項式である)

さてこれをどうやって示せばいいのか。
そもそもKrawtchouk多項式の時点で$\sum$が中に入っているし、、、とか考え始めると
地獄が待っている。

母関数という概念を用いる。
ただ、今Krawtchouk多項式$k_N^{(n)}(X)$の変数$NとX$のどちらを動かすか注意しなければならない。

Krawtchouk多項式の母関数

Krawtchouk多項式$k_N^{(n)}(X)$に対し、その母関数は($n$次多項式になる)
\begin{align*} \sum_{N=0}^nk_N^{(n)}(X)Y^N =\left\{1+(1-p)Y\right\}^X(1-pY)^{n-X} \end{align*}
ただし$X=0, 1, \cdots, n$を動く。
(左辺を$N$に関する無限和に変更することで、Xの冪級数としても一致する)

一般項の式とはうって変わり、綺麗になった。

$N$に関する和の範囲を形式的な無限和にすると
\begin{align*} \sum_{N=0}^{\infty}k_N^{(n)}(X)Y^N &= \sum_{N=0}^{\infty}\sum_{r=0}^N(-1)^{N-r}\binom{n-X}{N-r}\binom{X}{r}p^{N-r}(1-p)^rY^N \\ &= \sum_{r=0}^{\infty}(1-p)^r\binom{X}{r} \left\{\sum_{N=r}^{\infty}(-p)^{N-r}\binom{n-X}{N-r}Y^N\right\} \\ &= \sum_{r=0}^X\binom{X}{r}\left\{(1-p)Y\right\}^r \left\{\sum_{N=0}^{n-X}\binom{n-X}{N}(-pY)^N\right\} \quad (N \mapsto N+r, \,\, \text{和の範囲に注意}) \\ &= \left\{1+(1-p)Y\right\}^X(1-pY)^{n-X} \quad (\text{二項定理を2回使う}) \end{align*}
となり題意の式が従う。
また$n< N$のとき、Krawtchouk多項式$k_N^{(n)}(X)$は$0\le X\le n$で$0$を返す多項式になることに注意をするとわかる。(証明終わり)

実はこういうのは三項間漸化式との対応を見る方が綺麗かもしれないが。(盛大な前振り)
今まで母関数の話を一切してこなかったので、2階ODE型の直交多項式の母関数についてはまたの機会でまとめておきたい。

母関数を用いて直交性が示しやすいのは、二項分布が特徴的な冪の形をしているからである。

直交性/二乗モーメント

Krawtchouk多項式同士の内積を計算したいが、次のようにその内積に関する母関数を取る。
上同様に和の範囲を無限大まで拡張することで
\begin{align*} &\sum_{M, N=0}^{\infty} \left\{\sum_{X=0}^nk_M^{(n)}(X)k_N^{(n)}(X)p_n(X)\right\}Y_1^MY_2^N \\ &\quad= \sum_{X=0}^n\binom{n}{X}p^X(1-p)^{n-X} \left\{\sum_{M=0}^{\infty}k_M^{(n)}(X)Y_1^M\right\} \left\{\sum_{N=0}^{\infty}k_N^{(n)}(X)Y_2^N\right\} \\ &\quad= \sum_{X=0}^n\binom{n}{X}p^X(1-p)^{n-X} \left\{1+(1-p)Y_1\right\}^X(1-pY_1)^{n-X} \left\{1+(1-p)Y_2\right\}^X(1-pY_2)^{n-X} \quad (\text{母関数の値}) \\ &\quad= \sum_{X=0}^n\binom{n}{X} \Bigl[p\left\{1+(1-p)Y_1\right\}\left\{1+(1-p)Y_2\right\}\Bigr]^X \left\{(1-p)(1-pY_1)(1-pY_2)\right\}^{n-X} \\ &\quad= \Bigl(p\left\{1+(1-p)Y_1\right\}\left\{1+(1-p)Y_2\right\} +(1-p)(1-pY_1)(1-pY_2)\Bigr)^n \quad (\text{二項定理})\\ &\quad= (1+p(1-p)Y_1Y_2)^n \\ &\quad= \sum_{N=0}^n\binom{n}{N} p^N(1-p)^NY_1^NY_2^N \quad (\text{二項定理}) \\ &\quad= \sum_{M, N=0}^n\delta_{MN}\binom{n}{N} p^N(1-p)^NY_1^MY_2^N \end{align*}
以上より係数を比較することで
\begin{align*} \sum_{X=0}^nk_M^{(n)}(X)k_N^{(n)}(X)p_n(X) =\delta_{MN}\binom{n}{N}p^N(1-p)^N \end{align*}
となり、直交性及び二乗モーメントの値を確かめることができた。(証明終わり)

Krawtchouk多項式の性質

残りの性質である、三項間漸化式、差分方程式とRodriguesの公式、超幾何級数による表示、を与えたいと思う。
ただしあまりにも量が多いので、今回の記事では超幾何表示のみを与える。
（それ以外の性質については、次の記事で与えることにする）

Krawtchouk多項式の超幾何表示

Krawtchouk多項式$k_N^{(n)}(X)$は次のような(${}_2F_1$型の)超幾何関数における表示を持つ。
\begin{align*} k_N^{(n)}(X) &=(-1)^N\binom{n-X}{N}p^N \sum_{k\ge 0}\frac{(-N)_k(-X)_k}{k!(n-X-N+1)_k}\left(\frac{p-1}{p}\right)^k \\ &=(-1)^N\binom{n}{N}p^N \sum_{k\ge 0}\frac{(-N)_k(-X)_k}{k!(-n)_k}\left(\frac{1}{p}\right)^k \end{align*}

1式目は直接的に二項係数をバラしただけである。
それに対し2式目はかなり重要な使い勝手のいい式である。(変数$X$が1箇所にまとまった)

超幾何表示 1式目

一般項の中の二項係数を階乗にバラしていく、でもいいが、少し別の方法を取りたい。
$k_N^{(n)}(X)$の和の中のr番目の値を$a_r$とおく。すなわち
\begin{align*} a_r:=(-1)^{N-r}\binom{n-X}{N-r}\binom{X}{r}p^{N-r}(1-p)^r \end{align*}
このとき初項$a_0$と隣接項の比$a_{r+1}/a_r$を計算する。
\begin{align*} a_0&=(-1)^N\binom{n-X}{N}p^N \\ \frac{a_{r+1}}{a_r} &=\frac{\displaystyle(-1)^{N-r-1}\binom{n-X}{N-r-1}\binom{X}{r+1}p^{N-r-1}(1-p)^{r+1}} {\displaystyle(-1)^{N-r}\binom{n-X}{N-r}\binom{X}{r}p^{N-r}(1-p)^r} \\ &=-\frac{N-r}{n-X-N+r+1}\frac{X-r}{r+1}\frac{1-p}{p} \\ &=\frac{(-N+r)(-X+r)}{(n-X-N+1+r)(1+r)}\frac{p-1}{p} \end{align*}
これらの事実から、$k_N^{(n)}(X)=\sum a_r$の超幾何表示が
\begin{align*} k_N^{(n)}(X) =(-1)^N\binom{n-X}{N}p^N \sum_{k\ge 0}\frac{(-N)_k(-X)_k}{k!(n-X-N+1)_k}\left(\frac{p-1}{p}\right)^k \end{align*}
のように得られることがわかった。(証明終わり)

2式目を示すために、次の補題を用意する。
(1式目から2式目が直接示されるのかどうかは私は知らない)

$k\le n$なる非負整数$k, n$に対して次が成立する。
\begin{align*} \sum_{N=k}^n \binom{n}{N}\binom{N}{k}a^N =\binom{n}{k}a^k(1+a)^{n-k} \end{align*}

補題の証明

私はこれを｢委員長-委員の定理｣と教わったが、
\begin{align*} \binom{n}{N}\binom{N}{k} =\binom{n}{k}\binom{n-k}{N-k} \end{align*}
という二項係数の等式を用いる。
左辺は｢$n$人の中から$N$人の委員を選び、その委員$N$人の中から$k$人の委員長を選ぶ｣選び方の総数である。
一方、右辺は｢$n$人の中から先に$k$人の委員長を選び、残り$n-k$人の中から委員長以外の委員$N-k$人を選ぶ｣選び方の総数である。
このような対応付けにより上の等式は正しいとわかる。

実はこんなことを言わなくとも、二項係数を階乗に直すことで
\begin{align*} \binom{n}{N}\binom{N}{k} &=\frac{n!}{N!(n-N)!}\frac{N!}{k!(N-k)!} =\frac{n!}{k!(N-k)!(n-N)!} \\ \binom{n}{k}\binom{n-k}{N-k} &=\frac{n!}{k!(n-k!)}\frac{(n-k)!}{(N-k)!\{(n-k)-(N-k)\}!} =\frac{n!}{k!(N-k)!(n-N)!} \end{align*}
となり明らかに一致しているのだが。

補題は今示した等式を用いて
\begin{align*} \sum_{N=k}^n \binom{n}{N}\binom{N}{k}a^N &=\sum_{N=k}^n \binom{n}{k}\binom{n-k}{N-k}a^N \quad (\text{今示した等式}) \\ &=\binom{n}{k} \sum_{N'=0}^{n-k}\binom{n-k}{N'}a^{N'+k} \quad (N=N'+k) \\ &=\binom{n}{k}a^k(1+a)^{n-k} \quad (\text{二項定理}) \end{align*}
のように示すことが出来る。(証明終わり)

超幾何表示 2式目

母関数を考えると
\begin{align*} \sum_{N=0}^{\infty}k_N^{(n)}(X)Y^N &= \sum_{N=0}^{\infty}(-1)^N\binom{n}{N}p^N \sum_{k\ge 0}\frac{(-N)_k(-X)_k}{k!(-n)_k}\left(\frac{1}{p}\right)^kY^N \\ &= \sum_{k\ge 0}\frac{(-X)_k}{p^k(-n)_k} \sum_{N=0}^{\infty}(-1)^N\binom{n}{N}p^N\frac{(-N)_k}{k!}Y^N \\ &= \sum_{k\ge 0}\frac{(-1)^k(-X)_k}{p^k(-n)_k} \sum_{N=k}^n \binom{n}{N}\binom{N}{k}(-pY)^N \\ &= \sum_{k\ge 0}\frac{(-1)^k(-X)_k}{p^k(-n)_k} \binom{n}{k}(-pY)^k(1-pY)^{n-k} \quad (\text{補題より}) \\ &=(1-pY)^n \sum_{k=0}^X\binom{X}{k} \left(\frac{Y}{1-pY}\right)^k \\ &=(1-pY)^n \left(1+\frac{Y}{1-pY}\right)^X \\ &=\left\{1+(1-p)Y\right\}^X(1-pY)^{n-X} \end{align*}
となり母関数が一致したので示された。(証明終わり)

Krawtchouk多項式として、超幾何関数の部分のみを取り出した
\begin{align*} {\widetilde{k}}_N^{(n)}(X) =\sum_{k\ge 0}\frac{(-N)_k(-X)_k}{k!(-n)_k}\left(\frac{1}{p}\right)^k \end{align*}
のように定めている文献が多数であろう。
以下では上の
\begin{align*} k_N^{(n)}(X) =(-1)^N\binom{n}{N}p^N \sum_{k\ge 0}\frac{(-N)_k(-X)_k}{k!(-n)_k}\left(\frac{1}{p}\right)^k \end{align*}
と共に、必要ならば両方載せておくこととする。
正規化の違いであるので、二項分布に関して直交するという事実は変わらない。

なお、${\widetilde{k}}_N^{(n)}(X)$の二乗モーメントは
\begin{align*} \sum_{X=0}^n\left\{{\widetilde{k}}_N^{(n)}(X)\right\}^2p_n(X) =\binom{n}{N}^{-1}p^{-N}(1-p)^N \end{align*}
である。また母関数は、二項係数を残した母関数
\begin{align*} \sum_{N=0}^n\binom{n}{N}{\widetilde{k}}_N^{(n)}(X)Y^N =\left\{1-\frac{1-p}{p}Y\right\}^X(1+Y)^{n-X} \end{align*}
として計算できる。(ほぼ$k_N^{(n)}(X)$の母関数に同じ)
(二項係数を掛けないと、${}_1F_1$型の合流型超幾何関数が出てきてしまい処理できない)

さて、この記事の最後に、
上で与えた超幾何表示から直ちにわかるdualityという性質について載せておく。

Krawtchouk多項式のduality

Krawtchouk多項式$k_N^{(n)}(X)$及び${\widetilde{k}}_N^{(n)}(X)$には次の"duality"と呼ばれる等式が成立している。
\begin{align*} {\widetilde{k}}_N^{(n)}(X) &={\widetilde{k}}_X^{(n)}(N) \\ k_N^{(n)}(X) &=(-1)^{N+X}\binom{n}{N}\binom{n}{X}^{-1}p^{N-X}k_X^{(n)}(N) \end{align*}

${\widetilde{k}}_N^{(n)}(X)$のdualityは、その超幾何表示
\begin{align*} {\widetilde{k}}_N^{(n)}(X) =\sum_{k\ge 0}\frac{(-N)_k(-X)_k}{k!(-n)_k}\left(\frac{1}{p}\right)^k \end{align*}
が$N$と$X$に関しての対称式であることから自明に従う。また$k_N^{(n)}(X)$についてはdualityを
\begin{align*} k_N^{(n)}(X) =(-1)^N\binom{n}{N}p^N{\widetilde{k}}_N^{(n)}(X) \end{align*}
の定義式に代入することで
\begin{align*} &{\widetilde{k}}_N^{(n)}(X) ={\widetilde{k}}_X^{(n)}(N) \\ &\Leftrightarrow (-1)^N\binom{n}{N}^{-1}p^{-N}k_N^{(n)}(X) =(-1)^X\binom{n}{X}^{-1}p^{-X}k_X^{(n)}(N) \\ &\Leftrightarrow k_N^{(n)}(X) =(-1)^{N+X}\binom{n}{N}\binom{n}{X}^{-1}p^{N-X}k_X^{(n)}(N) \end{align*}
となり従うことがわかる。（証明終わり）

dualityの観点からすると${\widetilde{k}}_N^{(n)}(X)$の方が定義に相応しい気もするが
$k_N^{(n)}(X)$の方が綺麗な性質を見せる場面もある。
・・・それについて書くのは次次回くらいになりそうな気がしてならない。