MITの研究者、高速でメモリ効率が高い乱数生成アルゴリズム「FLDR」を開発：重み付け乱数を効率良く生成

MITの研究者チームは、少なくとも特定のタスクについては、速度と精度、低いメモリ要件を最適な組み合わせで満たしながら乱数を生成するアルゴリズム「Fast Loaded Dice Roller」（FLDR）を開発した。

[＠IT]

　マサチューセッツ工科大学（MIT）の研究者チームは、2020年5月28日（米国時間）、乱数を生成する優れたアルゴリズム「Fast Loaded Dice Roller」（FLDR）を開発したと発表した。

　乱数を生成するときに求められる3種類の要件、すなわち速度と精度、メモリをあまり使わないことについて、現時点における最適な組み合わせで実行できるという。乱数生成はさまざまなシミュレーションで多用されているため、効率の良い手法に対するニーズは高い。

　FLDRを開発したのは、MITの大学院生フェラス・サード氏、リサーチサイエンティストのキャメロン・フリーア氏、マーティン・リナード教授、プリンシパルリサーチサイエンティストのビカシュ・マンシンカ氏。「AISTATS 2020 : The 23rd International Conference on Artificial Intelligence and Statistics」（AISTATS第23回人工知能と統計学に関する国際会議、2020年6月3〜5日に開催）で、FLDRに関するプレゼンテーションを行う予定だ。

　簡単に言えば、FLDRは、さいころの回転をシミュレートして整数の乱数を生成するコンピュータプログラムだ。さいころは任意の数の面を持ち、事前に重み付けすることで、特定の面が他の面よりも高い確率で出るようになる。

　重み付けされたさいころ（原文では「loaded dice」とあり、「いかさまさいころ」という意味がある）は、乱数を生成できる。どの面が出るか前もって予想できないためだ。その一方でランダム性を、あらかじめ設定した確率分布を満たすように制約できる。例えば、重み付けされたさいころを使って、野球の試合結果をシミュレートできるかもしれない。

　FLDRでは、さいころは“完全に”重み付けされている。これは、指定された通りの確率を実現できることを意味する。4面のさいころを例に説明すると、「1」「2」「3」「4」の各目を25％ずつではなく、例えば23％、34％、17％、26％の確率で出るように設定できる。

　多数の面を持ち、重み付けされたさいころの回転をシミュレートするために、MITの研究チームはまず、ランダム性を生み出す簡単な源を利用しなければならなかった。それは、0または1をそれぞれ50％の確率で生成する、コイントスのコンピュータ化されたバージョンだった。乱数生成方法の効率は、各さいころの回転をシミュレートするために、こうしたランダム源を利用する必要がある回数（“コイントス”の回数）に依存する。こうした効率が、乱数生成方法の重要な設計基準となる。

既に知られている効率の良い手法には問題があった