とつげき東北

 古典的な信仰。

 暗号学的擬似乱数に「偏り」があり、当該偏りが計算量的に予測可能ならば、インターネット等における金融取引その他現代的な各種情報通信領域の基盤技術がたやすく崩壊することになるが、人々はやすやすとコンピュータの出力する各種の乱数の「偏り」を看破してみせる。現象ではなくて認識の方に偏りがあるのでは、と疑うこともなく。
「コンピュータは与えられた計算しかできない」と言われるが、計算機は、その程度の知識しか持たぬ者よりもしばしば優秀に機能するだけでなく、彼の想像をもはるかに超えて機能するものだ。

  • 2007-05-15 (火) 23:29:49
    彼らが想像したこともない程の天才がシステムから理論まで作っているのだから、彼らを超えて機能するのも、彼らが理解できないのも当然かもしれませんね。
     
  • 亡国 2007-05-15 (火) 23:56:50
    >瓦
    「彼らが想像したこともない程の天才」を認めたがらないことが
    もっともわかりやすい理由では。

    っていうか、トップ項目に追従してどうする。
     

  • masa 2007-05-19 (土) 09:10:07
    >暗号学的擬似乱数に「偏り」があり
    なんだかなあ。まるで、古典的擬似乱数(予測可能、再現性ありの擬似乱数の意味でつかっています。)
    については、偏りがあると読むこともできるではないか。
    乱数の検定プログラムを使って検定すれば、
    古典的方法(たとえば混合合同法)などはアウトかもしれない。
    でも、
    >人々はやすやすとコンピュータの出力する各種の乱数の「偏り」を看破
    とうのは、人間レベルでは無理でしょ?
    (混合合同法あたりなら、ノイマンやヴィルトといったかたなら人間レベルでもひょっとすると...
    でも、メルセンヌ−ツイスタなら、いくら何でも人間業では無理(乱数の種がバレないとして。))
    と思うが。

    ついで。
    >>ハードウェア乱数生成ルーチンhdrand.c (別コンテンツ)
    >>動作速度は遅い(1000ビット/1秒)が、「真の乱数」は普通は1000ビットもあればかなり充分だろう。
    これって、モンテカルロシミュレーションの場合、必要な乱数が1000ビットどころか、
    1000kビットでもまるで足りないがな。
    (麻雀の洗牌1回でさえ、1000ビットでは無理っぽい。(私の計算では最小で約2000ビット。))

    結論として、
    モンテカルロシミュレーションのような場合、
    動作速度が遅い(1000ビット/1秒)のはルーチンとして致命傷であり、
    メルセンヌ−ツイスタなどの「乱数の種発生」としてなら使えるけど、
    乱数そのものの発生ルーチンとしては使えない。

 

  • 六分儀 2007-05-19 (土) 10:27:09
    >>人々はやすやすとコンピュータの出力する各種の乱数の「偏り」を看破
    >とうのは、人間レベルでは無理でしょ?

    乱数を看破したつもりになっている愚者を揶揄した文だと思われ。
    東風荘のプログラムに偏りを発見できる人は結構多いですからね。
    そのことをいってるんでしょう。
     

  • とつげき東北 2007-05-19 (土) 12:41:46
    >masa

    暗号学における擬似乱数は、「計算量的に、出力値が真の乱数と区別不可能な乱数」と定義されているので予測は不可能。
    メルセンヌツイスターは線形漸化式で出力値を決定するから予測可能。
    また、単純な線形合同法などを使っていても、混ぜる等のアルゴリズム非公開でそれなりのエントロピーを入れておけば――たとえば複数の系列の乱数を組み合わせて用いたり、サーバ側でネットワークのトラフィックを利用して適宜シャッフルするなどすれば――、ゲーム等において実用的に予測不可能なものは作れる。

    「真の乱数」をそのままモンテカルロシミュレーションに使うやつがいるか(笑) だいたいシミュレーションに「真の乱数」を使う意味は何だ(笑) 低速なだけでなく、再現性なしという致命的な欠陥があるぞ。
    暗号的利用が必要な場合、当然たとえばメルセンヌツイスターの種に用いる。
    一方向関数が存在すれば暗号論的擬似乱数が存在する(逆も成り立つ)ので、暗号的に利用する場合は、メルセンヌツイスターの出力値(実装レベルで言えば、さらに初期ランダム値でパディングしたもの)をSHA−512等の一方向性関数に放り込むか、さらに証明可能安全性を保ちたければBlum−Blum−Shubなどを使う(速度が遅いが)。

    いずれにせよ種となる「真の乱数」が必要となる。
    HotBitsなど、放射性崩壊を観測して真の乱数を得る仕組みが実用化されているようだが、そんなものは一般家庭・企業に浸透していない。
    代替措置としてのhdrand.cの手法は極めて有益である(「真の乱数」が1000ビット程度あれば、充分すぎるほど安全な擬似乱数の種となる)。無理やり「モンテカルロシミュレーションにそのまま使う」という正体不明の前提を置いてまで攻撃すべきではない。

  • とつげき東北 2007-05-19 (土) 12:41:46
    どは! オペミスったよ…書き込みが消えた…気合が入ったときに、また書きます。

 

  • M 2007-05-20 (日) 01:37:06
    ぜ・・・絶好調だなw
     
  • とつげき東北 2007-05-20 (日) 06:50:18

    >masa

    どうも批判されているように見えるので反論しておく。

    >(麻雀の洗牌1回でさえ、1000ビットでは無理っぽい。(私の計算では最小で約2000ビット。))

    その計算は間違っていると思うが、どんな仮定を置いて、どんなアルゴリズムを利用し、どんな計算を?

    山牌の組み合わせが持つ情報量は、およそ772.56ビット(ただし、1種4枚を区別する場合。区別しなければ約617ビット)。
    ∵Σ(i=1〜136)(log2(i))≒772.56 (エクセル計算精度)
    ゆえに、机上は、773ビット(同じ牌を区別しない場合は約617ビット)あれば山牌の全てのパターンを表現できる。ただし計算量的に、773ビットのビット列を一意に山牌と1対1対応させることは不可能だろう(巨大なテーブルが必要となると思料される)。

    そこで、乱数を用いて洗牌を行い、山牌を作成することになる。真の乱数ビットを用いて山牌を作る際に、「無限にゼロに近い誤差さえない攪拌関数(完全な攪拌関数)」にしようとした場合、計算量に下限値は存在しない。
    配山の組み合わせ数が2のべき乗に一致しないため、773ビット分の真の乱数を得ても、少なくとも1通り以上、「捨てる」必要がある組み合わせが存在するためだ。捨てる可能性がある以上、再計算が必要になる可能性があり、その確率は何度繰り返しても0にならない。
    もし32ビットほど追加して805ビットとすれば、再計算の可能性は約43億分の1に低下させられる。割と充分小さい確率だと思うが、「計算量的安全性」を考えて128ビットに拡張したとしても、机上では配山を901ビットで表現できる。これがいわば「計算量的な意味での理論上の最小値」となる。

    ※ついてこれてない人(のうち、ある程度数学がわかる人)のために補足

    乱数ビットを用いて、1〜4のいずれかをランダムに選ぶことを考えると、00=1 01=2 10=3 11=4 とすれば、2回の乱数ビットによって必ず決定できる。
    ところが、1〜3のいずれかをランダムに選ぶ場合は困難である。
    1ビットでは足りないので、2ビット使う。
    00 01 10が1、2、3に対応するとして、11が出てしまったらどうするか。
    この場合、乱数のうち大半(等確率に出現していることがある下位ビットを除く)を「捨てる」他ない。結局、その種の「ハズレ値」が出てしまった瞬間、「それを1〜3のどれかに等確率で、どうにかして当てはめる」必要があるわけだが、当該行為は、最初から1〜3のどれかを選ぶ問題と等価であるからだ。
    出てしまった「ハズレ値」をやりくりしたところで、結局は1〜3に等確率で分布させなければならないことに変わりないから無駄である。
    それで、そのような「ハズレ」が確率的に起き得る限り、「何回計算すれば求まるか」の下限値は存在しないことになる。死ぬまで1〜3のどれにするか迷い続ける可能性はゼロではない

    ところで、通常、乱数を使ってランダム選択する場合には、「ハズレを捨てる」ことはしない。正確性を重視したり、ビット数をことさらに削ったりしなければならないという使命がない限り、最大値がある値になる自然数の中から1つの数字を選ぶランダム選択をしたければ、例えば32ビットくらいの大きさの乱数を得ておいて、最大値となる自然数で割って、余り+1を選択された数字と見なせば良い。
    2^32=4294967296通りの数字が得られるうち、1431655765個は2に対応、1431655765個は3に対応、それから1431655766個(他の2つの数字よりも1多い)は1に対応、という風にだ。4294967296分の1の確率で生ずるわずかな偏りは、まあ無視しようということである。
    麻雀などのランダム選択では、このような方法が取られていることが多いと推測される。
    】(きっと、本当に頭の良い人はもっとわかりやすく書く←)

    さて確認になるが、実際の牌山作成のロジックは、1〜136の箱に牌1〜136を並べておいて、
    ・1番目の箱を、1〜136の箱のどれかと交換する。
    ・2番目の箱を、2〜136の箱のどれかと交換する。
     ……
    ・135番目の箱を、135〜136の箱のどれかと交換する。
    というものが一般的だ。
    これは、
    「1〜136のどれかをランダムに選択」
    「1〜135のどれかをランダムに選択」
    ……
    「1〜2のどれかをランダムに選択」
    という作業と等価である。

    136までの自然数をランダムに選ぶには、現実的に何ビット必要か。
    最小値1、最大値が2^x+1〜2^(x+1)の間にある自然数から1つをランダムに取る場合、x+1ビットの乱数が最低限必要である。ただし、ギリギリのx+1ビットでは、最大2^x程度のハズレができる(たとえば1〜256の8ビットを利用して選択する場合、本来の最大値が129であれば、130〜256の127個がハズレになる)。
    ハズレた場合にやり直しを認めないなら(当該条件下でしか計算に必要なビット数の最小値は定まらない)、ハズレはそのまま牌の攪拌の偏りとなる。
    ハズレ率を減らすために1ビット増加させるたびに、ハズレが生ずる確率は平均的におおむね半減する。この冗長ビットをyビット(固定)取るとしよう。

    【計算過程】
    136〜129まで(8個)は、8ビットで表せるが、yビット追加して8+yビットとすれば、ハズレが生ずる確率が最大で1/(2^y)程度になる。
    128は7ビットで表せる。
    127〜65まで(63個)は7+yビットで表せる。
    64は6ビットで表せる。
    同様に考え、合計で、
    =833+128yビット
    となる。

    【計算結果】
    1回の抽出を行う際のハズレ率を最大1/2^yとするためのyと、その際に山を作るために必要な乱数のビット数との関係は、833+128yビットである。yに依存して必要な最小ビット数は変化する。

    【偏りをなくす方法による場合】
    しかし、ハズレによって牌山に(ごくわずかの)偏りが生じてしまうのは、どうにも許しがたいとしよう。
    そこで、ハズレた場合は再抽出を行うこととする。
    ビットを無駄にしないよう、ハズレが出てしまったら乱数のうち無駄な部分だけを破棄する方式を採用する。

    この方式で、yを固定して1〜136をランダムシャッフルするために平均的に必要なビット数は、「ハズレ」を引いた場合のやり直しを含め、概算で、
    y:0  1231
    y:1  1135
    y:2  1177
    y:3  1263
    y:4  1370
    y:5  1486
    y:6  1608
    y:7  1733
    y:8  1859
    程度となる。
    たとえばy=5とすれば1回の山牌作りで平均1回のやり直しで済み、速度低下等の実装上の問題はない。この際、必要なランダムビット数はおよそ1486ビットである。

    【応用】
    さらにアルゴリズムを洗練し、ハズレを引く確率が、ランダム選択したい自然数によって変動することを考慮し、常に動的にyの値を最適に変動させることで、平均乱数1100ビットまで低下させることに成功した。
    http://www.interq.or.jp/snake/totugeki/bitalgo.pdf
    1回の牌山を作成するために平均18.6回の「ハズレ」を引くが、実用上問題のある数字ではない。
    万一「死ぬほど不幸」に見舞われてずっとハズレを引き続けることを心配するなら、試行回数に適当なしきい値を設けて「偏りを許容」すれば問題は生じない。

    【結論】
    実装を考慮に入れた上での現実的な「完全に等確率での牌山攪拌」において、平均的に必要な乱数ビット数はかなり大きく見積もって1500もあれば充分である。

    以上から、「私の計算では最小で約2000ビット」というmasaの概算はまったく誤りである。どんな粗末なアルゴリズムで莫大なビットを浪費してしまったのか。そもそも、条件を与えなければ解のない問題に対して、条件なしで計算ができるのはどういうわけか。
    完全等確率な分布になる洗牌を選択するか、偏りの生じる洗牌を選択するかの別についても無自覚である。

 

  • 2007-05-22 (火) 03:01:31
    ↑の書き込み一回消えたとかゲーム中に停電並の絶望感だなw

 

  • 亡国 2007-05-24 (木) 22:09:13
    息を呑んでこの項目を開いたそのすじの皆様方、肩を落とさせて申し訳ない。笑って許してください。

 

  • masa 2007-05-25 (金) 02:55:45
    とつさん

    >「真の乱数」をそのままモンテカルロシミュレーションに使うやつがいるか(笑)

    いえね、こう書かれてはじめて気づいたんだけど、
    >>「真の乱数」は普通は1000ビットもあれば
    の部分、「真の」の2文字を無いものとして読んでました。引用した箇所なのに。あちゃー。議論終わってもうた。

    >>麻雀の洗牌1回の乱数は最小約2000ビット。
    >どんな仮定を置いて、どんなアルゴリズムを利用し、どんな計算を?
    これについては一度書いた以上答えておきます。
     1〜136の箱に牌1〜136を並べておいて、
     ・1番目の箱を、1〜136の箱のどれかと交換する。
     ・2番目の箱を、1〜136の箱のどれかと交換する。
     ・136番目の箱を、1〜136の箱のどれかと交換する。
     1〜136を表すには8ビット必要で、ハズレた場合再抽選とし、8ビットそっくりを再度引っ張る。
    8bit*136*(256/136)=2048≒2000bit。
    要するに、最小といっても、字句どおりの最小ではなく、
    ビットの節約に凝らない範囲での最小。
     

  • robert 2007-05-25 (金) 22:22:11
    >要するに、最小といっても、字句どおりの最小ではなく、
    >ビットの節約に凝らない範囲での最小。

    ここから名言を抜き出せ(各5点)
     

  • 我打麻将 2008-06-15 (日) 16:40:50
    こんな面白い記事があったのか!
     

コメントは以下の作業を終えてからお願い致します。





重要:ボタンを押すか、手動で「OK!」と入力してからでないと反映されません。
一度入力すればクッキーによって保存され、入力の手間は省けます。


トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-08-24 (火) 18:40:23 (2861d)