ガチャ、オートマトン、オイラー積分 - Analytic Combinatoricsが面白い

Analytic Combinatoricsがめちゃくちゃ面白い。場合の数という離散的なものを数えるのに、連続的世界から生まれた解析学の知見を用いる分野だ。階乗をガンマ関数で表示するだとかいうレベルではなく、マクローリン展開の係数を調べることで場合の数を知るようなことをしている。

オートマトン

ハマった発端は「オートマトン理論再考」（新屋, 2017 *1 ）というサーベイ論文。有限状態オートマトンを定めると、そのグラフの形から直接「 $a_i=$ 出力文字列のうち $i$ 文字のもの」の $a_i$ 係数とする母関数が構成でき、それをマクローリン展開すると、 $i$ 文字となる出力の場合の数が直ちにわかるという内容を紹介していた。この結果は文脈自由言語にも拡張でき、生成規則から母関数が機械的に計算でき、その展開係数が $i$ 文字の場合の数になっているという。場合の数を数えるのになんとマクローリン展開！一体どういうことなのか。

例えば、[1]中では「正しく対応する括弧の文字列」の集合で構成されるDyck言語

$\displaystyle \xrightarrow{R} : S = \varepsilon \mid (S)S$

を取り上げていた。この規則は、例えば

$\displaystyle \varepsilon,\ ( ) ,\ ( ( ) ) ,\ ( ) ( ) ,\ ( ( ( ) ) ) ,\ ( ( ) ( ) ) ,\ ( ( ) ) ( ) ,\ ( ) ( ( ) ) ,\ ( ) ( ) ( ) ,\ \cdots$

のような文字列を生成する（ $\varepsilon$ は空文字列。また、生成規則中の括弧は文字を表すことに注意）。

さて、上記を見ると、Dyck言語では2文字の場合は1通り、4文字の場合は2通り、6文字の場合は5通り存在する。では、一般の文字数では何通りあるのか？普通、この問に答えるには、漸化式や場合分けなどが沢山必要だろうというイメージがあった。しかし、なんと文脈自由言語の生成規則を機械的に母関数化する操作 $\Xi$ を用いて、

$\displaystyle \Xi (\xrightarrow{R}): S = 1 + zSzS$

となり、母関数 $S$ に関する方程式

${\displaystyle z^{2} S - S + 1 = 0, \, \, i.e. \, \, S = \frac{1 \pm \sqrt{1-4z^{2}}}{2z^{2}} }$

がわかり、さらにそれをマクローリン展開すると

$\displaystyle S = \sum_{i=0}^\infty C_{i}z^{2i}$

と、カタラン数 *2 $C_{i}$ で書けることから、Dyck言語のうち $2i$ 文字の場合は $C_{i}$ 通りであることがわかるのである。

これを初めて見た時の感想は「あ・・・ありのまま今起こったことを話すぜ・・・！！」だった。あの場合の数の細かい操作が、全て解析的操作に押し込められていた。離散的なものを解析するのに、解析学の知見を使う系の物が好きな上に、複雑な対象が代数的に、かつ機械的に処理できるようなものが昔からかなり好きなのだけど、これはもう驚きの連続で見ているだけで幸せになれた。

一番感動したのは、Kleene Starが母関数の無限等比級数を取る操作に等しいことだ。 $a^{*}$ という正規表現にマッチする文字列において、 $i$ 文字のものは常に1通りだ。したがって、 $a^{*}$ の母関数は

$\displaystyle \Xi[a^*] = 1 + 1 \cdot z + 1 \cdot z^{2} + \cdots = \frac 1 {1-z}$

となることがわかる。

しかし、これだけでは終わらない。なんとこれが一般の場合に拡張できるのである！ $(a|ba)^{*}$ という正規表現があったとき（ここではDyck言語における括弧とは意味が異なり、括弧は文字としてカウントしていないことに注意）、なんと

$\displaystyle \Xi[(a|ba)^{*}] = \frac{1}{1 - \Xi[(a|ba)]} = \frac{1}{1 - (z+z^{2})}$

のようになるのだ。このマクローリン展開の一般項は、なんとフィボナッチ数列になることが、[1]の中で触れられている。つまり、正規表現 $(a|ba)^*$ にマッチする文字のうち、 $i$ 文字のものは $i$ 番目のフィボナッチ数通りあるのだ。

また、[1]中では他にも正規言語 $\iff$ 母関数が有理関数、文脈自由言語 $\iff$ 母関数が代数関数となることから、言語の母関数の極が無限にあればそれは文脈自由言語や正規言語ではないことがわかるなどの結果が紹介されていた。これは、正規表現でマッチしうる場合の数の性質と、文脈自由言語の性質が、解析学的には有理関数と代数関数の差として表現できるという、もうこれ哲学じゃん！！という内容だった。他にも、まだ読めていないがいわゆる無限の猿定理のフォーマルな証明などを紹介している。

ガチャの数

続いて見かけたのはアイテムコンプに必要なガチャの回数の期待値を厳密に計算する方法 (sxarp, 2017, ブログ記事)。ここではCoupon Collector's Problem を一般化し、異なる確率で得られるクーポンを集めるまでの回数の期待値を、マルコフ連鎖を用いて計算している。

この問題のモデルは重み付き有限状態オートマトンで書けるので、母関数法を用いてもっと簡単に解けないかと論文を探していたら、Math Overflowの質問から Flajolet, et al., 1992 *3 を見つけた。そこには正規言語の話など見慣れた話題が載っていた。この論文の定理4.1が、問題の期待値を求める式を与えている。

更に、この定理の元となる定理3.1を見ると、どうもKlamkin and Newman, 1967 *4 の Extensions of the Birthday Surprise という論文が出典らしい。

この論文では、所望の期待値を求めるために、なんと道具がガンマ関数の定義式であるオイラー積分にまで発展しているのだ！！

$\displaystyle \Gamma(x) = \int_0^\infty t^{z-1}e^{-t}dt$

これが、階乗を連続的に扱うためにガンマ関数で表示する、とかいう生半可な使い方ではないのだ。これをどう使うかというと、ある母関数を考えるのに、それに $\frac{t^{N}}{N!}$ をかけた補助的な関数を考え、色々いじったあとに、 $\frac{t^{N}}{N!}$ を消去するのに $e^{-t}$ 倍してオイラー積分を行うのだ。「え、ここでそれするの！？」と、久々に感動した。最初多項式の話をしていたと思ったら、みるみるうちに話が解析的になっていき、最後にはガンマ関数が出てきて度肝を抜かれた。

この感動は是非元論文を読んで体験していただきたい。4ページで、アイデアもわかりやすいので、非常に読みやすい。

Analytic Combinatoricsスライド

もっとKlamkin and Newmanのような結果を読みたい！この分野は、どうもAnalytic Combinatoricsという名前がついているらしい。そこで、Analytic Combinatoricsで検索すると、Robert Sedgewick のFrom Analysis of Algorithms to Analytic Combinatorics - a journey with Philippe Flajolet *5 という発表スライドを見つけた。スライドを見ると "This talk is dedicated to the memory of Philippe Flajolet" とあり、更に "Philippe Flajolet 1948-2011" とあった。どこかで見覚えのある名前だなと思ったら、なんと [3] の著者だった！！一気に親しみを覚えると同時に少し寂しくなってしまった。どんな方だったのだろうか。

このスライドでは、PSET, MSETなどの生成規則に関する演算と、その母関数表示上での演算の対応規則が書かれており、 $N$ ノードある二分木の数え上げなどが行われていた。Kleene Starが $1/(1-z)$ と等価、を更に推し進めたような規則が沢山書いてあるのだ。

中でも心を打たれたのが、 "If you can specify it, you can analyze it" という格言だった。これは、正に「オートマトン理論再考」[1]を読んだ時の感動の源泉そのものだった。オートマトンのグラフ構造や文脈自由言語の生成規則からほぼ直接的に母関数を構成でき、更にその展開係数そのものが場合の数だという、この直接的な関係。機械的・機能的美しさと神秘を兼ね備えた感動をそのまま言い表していて、スライドの著者にとても同意した。

更に、このスライドでは Donald Knuth の The Art of Computer Programming など、Knuth に関して重点的に触れていたり、世界初の機械式コンピュータ "Difference Engine" をデザインした「コンピュータの父」Charles Babbageの言葉を引用していた：

"As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise - By what course of calculation can these results be arrived at by the machine in the shortest time?" - Charles Babbage, as quoted by R. Sedgewick [4]

なぜKnuthやBabbageのこの言葉を引用していたかというと、スライドによるとAnalytic Combinatoricsによる数え上げによってアルゴリズムの計算クラスを証明したりするらしい。このような美しい理論に実用的な使い道があるとますます嬉しくなる。

Analytic Combinatorics本

そして更に検索していると、Flajolet and Sedgewickの本 Analytic Combinatoricsを発見した。こちらは、826ページにも亘るにもかかわらずオンラインで無料で全ページ公開されている。

p.2 によると、このようなAnalytic Combinatoricsの流れは、1881年にDésiré André というフランスの数学者が、隣接する位の数字の大小が毎度交代する整数の場合の数が、 $\tan x$ のマクローリン展開の係数になっていることを発見したことから始まったという。

更にこの本のp.35では、凸多角形の三角形分割の場合の数がカタラン数で与えられることの直感的説明を紹介している。Dyck言語もカタラン数で与えられるため、三角形分割もDyck言語と同じような規則が存在するはずであると思ってこの本を読む前までしばらく悩んでいたのだが、このような複雑な構造をここまで直感的に説明できるものなのかと思った。

どんどん読み進めていくと、そもそもこの分野を調べるきっかけとなったオートマトンの話などが載っており、目が幸せになりつつ、現在この本を読み進めている途中である。

Babbageから現代まで

先程出てきたBabbageが設計したDifference EngineのレプリカはMountain ViewのComputer History Museumに展示 *6 されている。Charles Babbageは、Wikipediaによると1791-1871年を生きており、Analytic Combinatoricsの幕開けである1881年は彼の没後となる。彼のDifference Engineは、実はBabbageの生前は実装することができず、2002年に初めて実装されたとある。（つまり、Difference Engineはバグが無かったことが、100年以上越しに示されたことになる！）以前博物館を訪れた際そのDifference Engineのレプリカの一つを見たが、改めて、そんな「コンピュータの父」の「アルゴリズムを最小時間で実行することが興味の対象となるだろう」という予想、そしてDifference Engineの黎明期的雰囲気から、Analytic Combinatoricsという大変美しい理論によってアルゴリズムの計算量が測られる現代までの、風が吹くような勢いの変遷を見て、計算機科学に待ち受けるまだ見ぬ面白さにますます大きな期待を僕は寄せている。

*1:https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja/

*2:https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0

*3:Flajolet, et al. (1992), Birthday paradox,coupon collectors,caching algorithms and self-organizing search.

*4:http://www.sciencedirect.com/science/article/pii/S0021980067800759

*5:https://www.cs.princeton.edu/~rs/talks/AofA2AC.pdf

*6:http://www.computerhistory.org/babbage/