P (X_{n + 1} = j ∣ X_{n} = i, X_{n - 1}, \dots, X_{0}) π_{j} = p_{ij} = i \sum π_{i} p_{ij}

マルコフ連鎖

Markov chain

プーシキンの 2 万字を、母音と子音に分けて鉛筆で数えた。

次の一歩が今の状態だけで決まる偶然の列。長く続けると、各状態にいる割合は決まった値に落ち着く。言葉の統計、検索の順位、物理の計算の土台。

年代: 1906年
人物: アンドレイ・マルコフ、パーヴェル・ネクラーソフ、アレクサンドル・チュプロフ、アンドレイ・コルモゴロフ、クロード・シャノン

数学言語学情報科学物理学

逸話

オネーギンの 2 万字

1913 年 1 月 23 日、サンクトペテルブルクの帝国科学アカデミーの物理数学部で、56 歳の数学者アンドレイ・マルコフが講演をした。材料は、アレクサンドル・プーシキンの韻文小説『エヴゲーニイ・オネーギン』である。数学者が詩を持ち出したのは、味わうためではない。文字を数えるためだった。

マルコフは、第 1 章の全部と第 2 章の 16 連から 2 万個の文字を取り出した。句読点と空白を捨て、それだけでは発音されない硬音記号 ъ と軟音記号 ь も除いた。残った文字を 1 本の長い列にし、1 文字ずつ母音か子音かに分けた。

列は 100 字ずつ、縦 10 行・横 10 列の升目に書き写された。升目は 200 枚になる。書き出しの「мой дядя самых честных правил」(わたしの伯父は、このうえなく実直な人で)から始まる最初の 100 字には、母音が 42 個あった。次の 100 字には 46 個。200 枚の母音の数は 37 個から 49 個のあいだに散らばり、平均は 43.19 個だった。

全体では、母音が 8,638 個、子音が 11,362 個あった。マルコフはさらに、母音のすぐ後に母音が来る並びを数え、1,104 か所を得た。母音の後に母音が来る割合は $1104/8638 \approx 0.128$ である。母音の後に子音が来る並びは、引き算で $8638 - 1104 = 7534$ か所と分かる。ここから、子音の後に母音が来る割合は約 0.663 と求まる。前の文字が母音なら、次が母音になるのは 8 回に 1 回。子音なら 3 回に 2 回。すぐ前の 1 文字で、次の文字の出かたが 5 倍以上も違う。

もし文字が前と無関係に並ぶなら、母音が 2 つ続く並びは約 3,731 か所あるはずだと、アメリカの科学ライター、ブライアン・ヘイズは計算している。実際の 1,104 か所は、その 3 分の 1 にも届かない。言葉の文字は、すぐ前の文字に引きずられて並んでいる。

計算機の無い時代である。マルコフはこれを鉛筆と紙だけでやり遂げた。のちには作家セルゲイ・アクサーコフの作品からも 10 万字を数えている。

本来は応用に冷淡な人だった。統計学者アレクサンドル・チュプロフへの手紙には、自分が関心を持つのは純粋な解析の問題だけで、確率論が応用できるかどうかには無関心だ、と書いている。そのマルコフが、詩を数えた。

この年は、ヤコブ・ベルヌーイの『推測術』が 1713 年に大数の法則を世に出してから 200 年にあたる。皇帝ニコライ 2 世がロマノフ家 300 年の祝賀を呼びかけた年に、マルコフは別の記念日を選び、ベルヌーイの 200 年を祝う集まりを準備した。同じ年に出た教科書『確率計算』の第 3 版は、オネーギンの数え上げを「依存する試行の良い例」として本の最後に置いている。

この講演の論文は、長くロシアの外では読まれなかった。言語学者モリス・ハレが 1955 年に英訳したが出版はされず、誰でも読める英訳が出たのは 2006 年である。

起源

独立でなくてもよい

硬貨を何度も投げると、表の出る割合は 1/2 に近づく。これが大数の法則である。1713 年のベルヌーイから 1867 年のパフヌティ・チェビシェフまで、証明はどれも、1 回 1 回の結果が互いに独立であることを前提にしていた。

マルコフは 1856 年にリャザンで生まれ、ペテルブルク大学でチェビシェフに学び、1905 年に大学を退いたあとも家で研究を続けた。

論争の相手は、モスクワ大学のパーヴェル・ネクラーソフ(1853〜1924)である。神学校で学んだあと数学に進んだ人で、1898 年ごろからは統計を、帝政と正教会の権威を支える道具として使うようになっていた。1902 年の著作でネクラーソフは、大数の法則は確率変数が 2 つずつ互いに独立なときに「完全な力」を持つ、と書いた。統計学者ユージン・セネタは、文脈から見て、2 つずつの独立が必要だと言っているのはほぼ疑いない、と読んでいる。

ネクラーソフはこの考えを、自由意志をめぐる議論に持ち込んだ。ヘイズの要約では、筋はこうである。犯罪の統計のような社会の数字は大数の法則に従う。大数の法則は独立な出来事にしか成り立たない。だから一人ひとりの行いは互いに独立で、自由な意志によるものだ。

無神論者のマルコフは、政治でも宗教でもネクラーソフと対立していた。けれども攻めたのは数学の誤りだった。1910 年 11 月 6 日、チュプロフへの手紙にこう書いている。「ネクラーソフのただ一つの功績は、多くの人も持っていると思われる彼の誤解、すなわち独立は大数の法則の必要条件だという考えを、はっきり示したことだ。この事情に促されて、私は一連の論文で、大数の法則もラプラスの公式も従属する変数に当てはまることを説明した」。

1906 年、マルコフは友人アレクサンドル・ヴァシリエフが編集していたカザン大学物理数学会の紀要に、論文「大数の法則の、互いに依存する量への拡張」を寄せた(刷り上がったのは 1907 年)。考えたのは、「 $x_{k}$ が分かれば、 $x_{k + 1}$ はそれより前の $x_{1}, \dots, x_{k - 1}$ と独立になる」ようにつながった変数の列である。マルコフはこれを単純な連鎖と呼んだ。次の一歩は今の状態だけで決まり、そこまでの道のりは関係しない。

最初は状態が 0 と 1 の 2 つだけの場合を扱い、続いて、移る確率がすべて正の有限個の状態の連鎖に広げた。どちらでも、長く続けた平均は一定の値に近づき、大数の法則が成り立つ。論文の最後の 1 文はこうである。「こうして、量の独立は、大数の法則が成り立つための必要条件ではない」。ネクラーソフの名前は出てこない。ヘイズによれば、この一連の結果に押されて、ネクラーソフは大数の法則から自由意志が導かれるという主張から退いた。

1908 年、マルコフは移る確率に 0 が混じる連鎖にも結果を広げ、中心極限定理も連鎖で成り立つことを示していく。「マルコフ連鎖」という名前は、1926 年のセルゲイ・ベルンシュテインの論文で初めて使われたとされる。1931 年にはアンドレイ・コルモゴロフが、時間が連続に流れる場合も含む一般の理論を立てた。1948 年、クロード・シャノンは英語の文字の並びをマルコフ過程として扱い、2 文字や 3 文字の並びの頻度をまねた「英語の近似」を作ってみせた(シャノンの情報エントロピー)。

証明

母音を V、子音を C とする 2 つの状態の連鎖で、母音の割合が一定の値に落ち着くことを示す。マルコフにならって、母音の後に母音が来る確率を $p_{1}$ 、子音の後に母音が来る確率を $p_{0}$ とし、 $n$ 文字目が母音である確率を $x_{n}$ と書く。

$n + 1$ 文字目が母音になるのは、「 $n$ 文字目が母音で、次も母音」か「 $n$ 文字目が子音で、次が母音」のどちらかである。
$x_{n + 1} = p_{1} x_{n} + p_{0} (1 - x_{n})$
整理すると、1 次の漸化式になる。
$x_{n + 1} = p_{0} + (p_{1} - p_{0}) x_{n}$
変わらない値 $π$ を探す。 $x_{n + 1} = x_{n} = π$ と置いて解くと
$π = \frac{p _{0}}{1 - p _{1} + p _{0}}$
$δ = p_{1} - p_{0}$ と書き、2 の式から $π = p_{0} + δ π$ を引く。
$x_{n + 1} - π = δ (x_{n} - π)$
これを $n$ 回くり返す。
$x_{n} - π = δ^{n} (x_{0} - π)$
マルコフの仮定どおり $0 < p_{1} < 1$ 、 $0 < p_{0} < 1$ なら $∣ δ ∣ < 1$ で、 $δ^{n} \to 0$ となる。どこから始めても
$n \to \infty lim x_{n} = π$

次に、実際に数えた割合も $π$ に近づくこと(大数の法則)を示す。簡単のため、はじめから $x_{0} = π$ とする。 $k$ 文字目が母音なら 1、子音なら 0 をとる量を $Y_{k}$ 、母音の個数を $S_{n} = Y_{1} + \dots + Y_{n}$ とする。

5 で $x_{0} = 1$ (母音から始める)と置くと、 $m$ 文字先が母音である確率は $π + δ^{m} (1 - π)$ である。よって $m$ 文字離れた 2 つの文字の共分散は
$Cov (Y_{k}, Y_{k + m}) = π (π + δ^{m} (1 - π)) - π^{2} = π (1 - π) δ^{m}$
$S_{n}$ の分散は、各項の分散 $π (1 - π)$ の和に、すべての組の共分散の 2 倍を足したものである。 $∣ δ ∣^{m}$ の和を等比級数で抑えると
$Var (S_{n}) \leq n π (1 - π) \frac{1 + ∣ δ ∣}{1 - ∣ δ ∣}$
チェビシェフの不等式から、どんな $ε > 0$ についても、 $n \to \infty$ で右辺は 0 に近づく。
$P (\frac{S _{n}}{n} - π \geq ε) \leq \frac{Var ( S _{n} )}{n ^{2} ε ^{2}} \leq \frac{π ( 1 - π )}{n ε ^{2}} \cdot \frac{1 + ∣ δ ∣}{1 - ∣ δ ∣}$

独立は 1 度も使っていない。使ったのは、離れた文字どうしの関係が $δ^{m}$ の速さで薄れることだけである。8 をもう少し細かく計算すると、 $n$ が大きいとき $Var (S_{n}) / n$ は $π (1 - π) \frac{1 + δ}{1 - δ}$ に近づく。独立なら係数は 1 である。母音と子音が交互に並びやすい( $δ < 0$ )ほど、ばらつきは小さくなる。マルコフが 1913 年に確かめたのは、この係数だった(応用)。

状態が $N$ 個あっても筋は同じである。移る確率 $p_{ij}$ がすべて正なら、 $π_{j} = \sum_{i} π_{i} p_{ij}$ を満たす分布 $π$ がただ 1 つあり、どこから始めても $n$ 歩後の分布はそこへ近づく。マルコフは 1906 年の論文で、出発の状態ごとに $n$ 歩後の期待値を求め、その最大と最小の差が 1 より小さい数の累乗の速さで縮むことを示した。

応用

オネーギンを連鎖で見る。 マルコフの数 $p_{1} = 0.128$ 、 $p_{0} = 0.663$ を 3 の式に入れると、 $π = 0.663/1.535 \approx 0.432$ になる。数えた母音の割合 $8638/20000 = 0.4319$ と合う。これは偶然ではない。長い列の中で「母音から子音へ」移る回数と「子音から母音へ」移る回数は、多くても 1 回しか違わない。その釣り合い $π (1 - p_{1}) = (1 - π) p_{0}$ を解いたものが、3 の式だからである。

いま母音を読んだとすると、次が母音である確率は 0.128、2 文字先は 0.595、3 文字先は 0.345、4 文字先は 0.478 と、上下に揺れながら 0.432 に寄っていく(図示)。ずれは 1 文字ごとに $∣ δ ∣ = 0.535$ 倍に縮み、5 文字先では 0.025 より小さくなる。5 文字離れると、前の文字の影響はほとんど残らない。

ばらつきが小さい。 100 字ごとの母音の数を考える。文字が独立なら、その分散は $100 \times 0.432 \times 0.568 \approx 24.5$ (標準偏差約 5.0)のはずである。マルコフが 200 枚の升目から出した値は 5.11(標準偏差約 2.3)で、比は 0.208、およそ 5 分の 1 だった。単純な連鎖とみなすと、比の理論値は証明の $\frac{1 + δ}{1 - δ} = \frac{0.465}{1.535} \approx 0.30$ で、分散にして約 7.4 になる。独立の場合の 1 よりずっと実際に近い。マルコフはさらに、次の文字が前の 2 文字で決まる「複雑な連鎖」を考えた。母音が 3 つ続く並び 115 か所、子音が 3 つ続く並び 505 か所を数えて理論値 0.195 を出し、これ以上の一致はほとんど望めない、と書いた。

ウェブページの順位。 1998 年、ラリー・ペイジとセルゲイ・ブリンは、検索エンジン Google の試作を発表した論文で、ページの重要さ PageRank を、リンクをでたらめにたどり続ける「ランダムサーファー」がそのページにいる確率として定めた。ページを状態とするマルコフ連鎖の定常分布である。確率 $d$ でいまのページのリンクの 1 つを選び、確率 $1 - d$ で全 $N$ ページから選び直す。論文は $d = 0.85$ を使った。 $C (T)$ はページ $T$ から出ているリンクの数である(論文の式は $1 - d$ を $N$ で割らない形で書かれている)。

P R (A) = \frac{1 - d}{N} + d T \to A \sum \frac{P R ( T )}{C ( T )}

A から B と C へ、B から C へ、C から A へリンクがある 3 ページなら、解は $P R (A) \approx 0.388$ 、 $P R (B) \approx 0.215$ 、 $P R (C) \approx 0.397$ になる。リンクを 2 本もらう C がいちばん高く、C のただ 1 本のリンクを丸ごともらう A が続く。

図示

母音と子音の 2 つの状態と、マルコフが『エヴゲーニイ・オネーギン』の 2 万字から求めた移る確率。矢印の太さは確率の大きさを表す。

『エヴゲーニイ・オネーギン』の最初の 100 字を、マルコフにならって 10 行 10 列の升目に並べたもの。網をかけた升が母音で、ѣ は旧い綴りの母音字。右の数は行ごとの母音の数で、й を母音に数えると、マルコフが書いた 42 個になる。

母音から始めた場合(実線)と子音から始めた場合(破線)の、n 文字先が母音である確率。上下に揺れながら、どちらも 0.432 に近づく。

升目の行を左から右へ読むと、元の文の順になる。マルコフは列ごとにも母音を数え、1 列目と 6 列目のように 2 列ずつを 5 枚の升目から集めて、別の 100 字の組を作った。こちらの組は、文の中で隣り合う文字を 1 つも含まない。そのばらつきの比は 1.18 で、独立な場合の 1 に近かった。隣り合う文字どうしの結びつきが、ばらつきを小さくしていたことになる。

シミュレーション

つまみで、母音のあとに母音が来る確率 $p_{1}$ と、子音のあとに母音が来る確率 $p_{0}$ を変えられる。「1 つの点」では、点が 2 つの部屋を 1 歩ずつ行き来し、母音の部屋にいた割合(実線)が定常分布 $π = p_{0} / (1 - p_{1} + p_{0})$ (破線)に近づいていく。「200 個の点」では、同じ部屋を出た点の群れが 1 歩ごとに分かれ、母音の部屋にいる割合が、証明の 5 の式(点線)のとおり揺れながら $π$ に落ち着く。「オネーギンの値」を押すと、マルコフが数えた 0.128 と 0.663 に戻る。

広がる学問

数学確率論の中心の対象である。移る確率がすべて正なら定常分布がただ 1 つに決まることは、行列の固有値についてのペロン(1907 年)とフロベニウス(1912 年)の定理と表裏の関係にある。マルコフの 1908 年の論文は、フロベニウスが負でない行列について完全に証明する 4 年前に、その主な部分を示していた。時間と空間を連続にすると、ブラウン運動のようなマルコフ過程になる。
言語学 オネーギンの分析は、言葉を統計で扱った最も早い仕事の 1 つである。シャノンは同じ考えで英語の文字や単語の並びをまねた。前の数語から次の語の確率を見積もる n グラムのモデルは、音声認識や機械翻訳で長く使われた。
情報科学 PageRank は、ウェブ全体を 1 つのマルコフ連鎖とみなす。見えない状態の連鎖から観測が出てくると考える隠れマルコフモデルは、音声認識や遺伝子の配列の解析に使われてきた。
物理学 1953 年、ニコラス・メトロポリスらはロスアラモスの計算機 MANIAC で、粒子の配置を少しずつ動かすマルコフ連鎖を、定常分布がボルツマン分布になるように作り、多数の粒子が集まった系の性質を計算した。このマルコフ連鎖モンテカルロ法は、のちに統計学のベイズ推定の計算にも広がった。

参考文献

A. A. Markov, "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga", Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, 15 (1906), 135-156.
A. A. Markov, "Primer statisticheskogo issledovaniya nad tekstom «Evgeniya Onegina», illyustriruyuschij svyaz' ispytanij v cep'", Izvestiya Imperatorskoj Akademii Nauk, VI seriya, 7(3) (1913), 153-162.(英訳 "An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains", Science in Context 19(4) (2006), 591-600)
G. P. Basharin, A. N. Langville, V. A. Naumov, "The Life and Work of A. A. Markov", Linear Algebra and its Applications 386 (2004), 3-26.
E. Seneta, "A Tricentenary History of the Law of Large Numbers", Bernoulli 19(4) (2013), 1088-1121.
B. Hayes, "First Links in the Markov Chain", American Scientist 101(2) (2013), 92. doi:10.1511/2013.101.92
S. Brin, L. Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine", Computer Networks and ISDN Systems 30 (1998), 107-117.
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller, "Equation of State Calculations by Fast Computing Machines", Journal of Chemical Physics 21 (1953), 1087-1092.