無理数時計の数理

　本記事は、何年も前に別の場所で書いた記事（現在は削除済）を note 用に修正したものである。このネタを何度も使いまわしており、最近は何もアウトプットしていない。また、このネタはお茶会や LT で話したことがありそこそこウケて個人的にお気に入りである [※1] 。これは大学院の研究室同期ととあるハッカソン [※2] に出て作ったものの解説である。参加したハッカソンの記事はこちら [※3] 。

　ハッカソンでのテーマは時間。成果物の名前は無理数時計。無理数 [※4] の小数点以下の桁の中から一番手前に存在する現在の時:分:秒の 6 桁を探し出して、時計として表示している。円周率 Π  や自然対数の底 e 、黄金比 φ 、 √2 、 ln2 に関して、 00:00:00 から 23:59:59 まで表示している [※5] 。

　直感的には非常に大きい桁数を調べることで時分秒すべての数字が存在しそうではあるが、どれだけの桁数を調べれば良いのか不明である。 Π に関して探すと、 2019 年には世界記録として 31 兆桁の計算結果が見つかる。これは数字だけが記載されたプレーンなテキストファイルでも 31TB となり、文字列検索するにしても圧倒的な大きさである。著者が最初に見つけたのは 4GB のテキストファイルであったが、こちらを対象にすると現実的な時間でプログラムが動作しない工学的な課題があった。そのため、ミニマムで理論上必要な小数点以下の桁数に関して見積もる必要があった。まずは期待値を計算し、雑にその 2 倍の長さのファイルで調査することにした。 [※6] 結果、現実的な時間で動作するようになった。

　手前味噌で恐縮だが、動作している成果物そのものと期待値を見積もる背景にある理論の両方が面白いと感じている。本稿では無理数時計の背景にある確率解析の部分を解説する。読者諸氏が当該分野に興味を持っていただけたら嬉しい限りである。

　まずは問題を定義しよう。

問題の定義

仮定
- 対象の無理数は正規数 [※7] と仮定する。（この命題は証明されていない）
- 各桁における数字は 0-9 であるが、各桁に 000000-999999 の数字が格納されていると仮定する。

問題
上記二つの仮定のもと時刻に相当する数字 000000〜235959 の 60*60*24 通りの数字が全て揃うのに必要な桁数の期待値を求める。

　円周率Πを例にとって説明をする。

3.141592653589793238462643383279...

　1 桁目の数字は 1 であるが、本問題においては 1 桁目の数字を 141592 とする。i 桁目の数字を ai と表記すれば、最初の 5 桁を整理すると以下の通りとなる。

a1 = 141592
a2 = 415926
a3 = 159265
a4 = 592653
a5 = 926535

　このとき、 ai の下 5 桁と a{i+1} の 1-6 桁の数字は等しいという制約が存在する。a1 と a2 を例にすると、太字で強調された部分の値が等しいことを意味している。

a1=141592
a2=415926

　今回の問題においては上記制約をなしと緩和して考える。つまり以下の例が発生しても問題ないとみなす。

ai = 134258
a{i+1} = 823475

　以上より、今回の問題は以下のように定義することができる。

各桁には 000000 から 999999 までの数字がランダムに格納されている。その中で時分秒に相当する数字がすべて揃うのに必要な桁数の期待値を求める。

　本問題は確率解析の問題であるクーポンコレクター問題に帰着させる。詳細な解法を説明する前にこちらを解説する。

クーポンコレクター問題

　クーポンコレクター問題は以下のような状況の問題である。

n 種類の異なるクーポンがあるとき、各種類のクーポンを 1 回以上引くまでに、何回クーポンを引けば良いか

　本問題を適用可能な現実の事象としては日本におけるビックリマンチョコレートの買い占めやソーシャルゲームにおけるコンプリートガチャなどがある。さまざまな一般化が可能な問題であるが、本稿においては最も基本的な問題の解説のみを行う。

　では、まずは問題を定義する。

n 種類の異なるクーポンが存在し、毎回の試行でこれらのクーポンを引き当てる確率はいずれも等しい。この際にすべてのクーポンを 1 枚以上引き当てるのに必要な試行回数の期待値を求める。

　解き方はシンプルである。すでに i(<n) 枚のクーポンを引き当てている際に、次のクーポンがまだ引き当てていないクーポンの確率 p(xi) を考える。 n 種類のクーポンが存在し、 (n-i) 種類のクーポンがまだ引き当てていない。そのため p(xi) = (n-i)/n となる。新規のクーポンを引き当てる期待値 E[xi] は 1 / p(xi) と等しい。また期待値の線形性より E[Σxi] = ΣE[xi] となる。整理すると以下のようになる。

　クーポンコレクター問題を一般化させた問題として、各クーポンの引き当てる確率が異なるケース、クーポンの引き当てる枚数が複数枚のケースなどがある。本稿ではこれらに関しては述べないが、バルセロナ自治大学数学科発行の電子ジャーナルに色々とまとまっているので、そちらを読んでいただけたらと思う。

解法

　本問題は以下のふたつの確率を考えることで期待値が求まる。

A. 一様分布に従い 000000 から 999999 の 10,000,000 通りの値が出るときに時分秒に相当する数字の並びが出る確率。
B. まだ、出ていない時分秒の数字の並びである確率。

　時分秒に相当する数字の並びの数 24*60*60 を n とし、全事象の数 10000000 を m とする。

　以上より、求める期待値は 11,400,000 程度である。

実測結果

　無理数時計で用いた代表的な無理数に関して測定したところ概ね期待値に近しい値であった。

おまけ

　今回調査した無理数では正規数だと仮定したが、無理数の中には正規数でないものも存在し、無理数時計の条件を満たさないものも存在する。例えば下記のような小数点以下の素数桁目の数字が1となる数も無理数である。

0.0110101000101000101...

　しかしこの数は定義より明らかに、 2-9 の数字が現れないため、無理数時計にならない。

脚注

※1　ふたつの記事で反応があった。
http://herumi.in.coocan.jp/diary/1807.html#1
https://negli0.github.io/posts/talk-at-tcfm-meetup/
自分の発表に対してフィードバックがあるのは嬉しい。実装では初歩的な過ちを犯しておりそこの指摘を受けており、学びの機会を得られてうれしい一方で少し恥ずかしい。

※2　ハックとマラソンを合わせた混成語のこと。たいてい最初になんらかのお題が出されて、所定の時間内にお題に基づく成果物を作り、最後に成果物に関するプレゼンテーションを行う。 Facebook の「いいね！」ボタンは、ハッカソンからアイデアが生まれたものとして知られている。

※3　オリジナル記事の SSL サーバ証明書が切れているようなので、 webarchive へのリンクとしているがご容赦願いたい。

※4　クヌース大先生のスタンフォード大学における 2019 年のクリスマスレクチャーも円周率 Π に関する内容だし、  Java の開発者であるジェームズ・ゴスリンはの好きな無理数は √2 として有名。無理数は我々を魅了して止まないのだ。

※5　詳細は記載しないが、分散も簡単に求まり、みんな大好きな Π がでてくる！　分散が分かったのでチェビシェフの不等式（詳細は割愛）を用いて封筒裏の計算をしたところ、期待値の 2 倍以内に収まっている確率は 0.5% 未満だった。そのため、大丈夫だろうと考えた。

※6　数字が一様に分布しており、数字の列が現れる頻度に偏りがないという性質のこと。この性質を満たしていると任意の数字がどこかには必ず存在する。『好きな整数を考えて』というお題を読者に出す。何桁であれその整数の並びは必ず正規数の中には現れる。面白いね。この内容を拡張して一般の記号がランダムに並んでいる事象に関する無限の猿定理という思考実験がある。