【ITニュース解説】A coin flip by any other name (2023)

コンピューターの世界で「乱数」という言葉を聞くと、まるでサイコロを振るように完全に予測不可能な数字がポンと出てくるイメージを持つかもしれない。しかし、実際には多くのケースで、そのイメージとは少し異なる「疑似乱数」が使われている。システムエンジニアを目指す上で、この乱数の仕組みと、それがどのように利用され、どのような限界を持つのかを理解することは非常に重要だ。

私たちが普段目にするゲームの敵の出現パターンや、シミュレーションでのランダムなイベントの発生など、多くの場面で使われるのが疑似乱数生成器（PRNG）によって作られる乱数だ。これは、名前の通り「疑似」の乱数であり、実は完全に予測可能で決定論的なアルゴリズムに基づいて生成される。乱数を生成するための初期値、いわゆる「シード値」を一度決めると、そこから生成される乱数の数列は常に同じになる。まるで、特定のレシピに従って作られた料理がいつも同じ味になるように、同じシード値からは常に同じ乱数の並びが再現されるのだ。これは、デバッグ時に同じ条件を再現したり、特定のシミュレーション結果を共有したりする際には非常に便利な特性だ。しかし、予測可能であるという性質は、セキュリティが求められる場面、例えば暗号鍵の生成や宝くじの抽選のような、本当に予測不可能なランダム性が必要な場面では致命的な欠点となる。もし攻撃者にシード値が知られてしまえば、次に生成される乱数をすべて予測できてしまうからだ。

そこで登場するのが「真の乱数生成器（TRNG）」という考え方だ。これはコンピューター内部の予測できない物理現象、例えばCPUの熱雑音や、マウスポインタの動き、キーボードの入力タイミングなど、人間にはコントロールできない自然なノイズを利用して乱数を生成する。これらの物理的な現象は、理論上は予測不可能であるため、生成される乱数も真にランダムで、高いセキュリティが要求される場面で利用される。しかし、物理現象を利用するため、疑似乱数生成に比べて時間がかかり、大量の乱数を高速に生成することには向かないという側面も持っている。

次に、コンピューターで特定の確率のイベントをシミュレートする方法を考えてみよう。例えば、成功する確率が30%のイベントを表現したい場合、多くのプログラミング言語に用意されている random() 関数を使うのが一般的だ。この関数は通常、0.0から1.0までの範囲で均一な疑似乱数を返す。もし、返された乱数が0.3未満であれば成功、そうでなければ失敗、と判定することで、確率30%のイベントをシミュレートできる。random() < 0.3 という単純な比較で済むため、非常に多くの場面で利用されている。

しかし、もう少し深く、「公平なコイントス」をコンピューター上でどのように表現するかを考えてみよう。単純に random() < 0.5 とすれば、表と裏がそれぞれ50%の確率で出るコイントスをシミュレートできる、と思うかもしれない。確かに、多くの用途ではこれで十分だ。だが、もし乱数生成器自体にわずかな偏りがあったらどうだろうか？例えば、0.5未満の値が出やすい乱数生成器であれば、表が出やすくなってしまう。このような微妙な偏りも許されない、真に公平なコイントスを実現するための興味深い方法がいくつか存在する。

その一つが、数学者ジョン・フォン・ノイマンが考案した「偏りのないコイントスを生成するアルゴリズム」だ。これは、たとえ偏ったコイントス（例えば、表が出る確率が60%、裏が40%のコイントス）を使っても、最終的に公平な結果（表50%、裏50%）を得る方法である。手順はこうだ。まず、その偏ったコイントスを2回投げる。

1. もし「表、裏」という順で出たら、これを「表」の結果とする。
2. もし「裏、表」という順で出たら、これを「裏」の結果とする。
3. もし「表、表」または「裏、裏」という順で出たら、これは無効とし、もう一度最初から2回コイントスを投げる。 なぜこれで公平になるかというと、たとえコイントスが偏っていても、「表、裏」というパターンが出る確率と「裏、表」というパターンが出る確率は同じになるからだ。例えば、表が出る確率を p、裏が出る確率を q（q = 1 - p）とすると、「表、裏」が出る確率は p * q で、「裏、表」が出る確率は q * p となり、これらは等しい。このようにして、個々のコイントスの持つ偏りを相殺し、真に公平なコイントスを生成できる。これは、乱数源の偏りがあっても、その出力を巧妙に処理することで公平性を確保できる、という非常に洗練された考え方だ。

もう一つの方法は、複数の独立した乱数源を利用する方法だ。例えば、完全に独立した2つの異なる乱数生成器AとBがあったとする。両方から同じビット数の乱数をそれぞれ生成し、それらを比較する。

1. もし乱数Aが乱数Bよりも大きければ、これを「表」の結果とする。
2. もし乱数Bが乱数Aよりも大きければ、これを「裏」の結果とする。
3. もし乱数Aと乱数Bが同じ値であれば、これは無効とし、もう一度乱数を生成し直す。 この方法でも、各乱数生成器がたとえわずかに偏っていたとしても、両者が独立している限り、どちらか一方が他方より大きいという結果になる確率は、ほとんどの場合で等しくなる。A > B と B > A の確率は、AとBが完全に独立していれば同じになるからだ。これもまた、乱数生成器自体の完璧さに頼るのではなく、その出力を相対的に比較することで公平性を担保するアプローチだ。

これらの例からわかるように、コンピューターにおける「乱数」は、その利用目的によって求められる品質が大きく異なる。システムエンジニアとしては、単に random() 関数を使うだけでなく、それがどのような特性を持つのか、そして本当に必要なランダム性や公平性が保証されているのかを常に意識する必要がある。セキュリティが求められるシステムでは真の乱数が必要不可欠だし、フォン・ノイマンのアルゴリズムのように、既存の乱数源の弱点を補うための工夫も重要になってくる。乱数の奥深さを理解することは、より堅牢で信頼性の高いシステムを設計・開発するための第一歩と言えるだろう。