ツイートあみだ

Twitter であみだくじをする「ツイートあみだ」の方法を書きます。つまり、あみだくじドットコムのようなことを、専用のシステムなしで、Twitter だけでします。ツイッターではなくても、発言履歴が記録されて発言の後に発言内容を書き換えることが出来ないシステムであれば、なんでも構いません。

ツイッターで2人対戦

あみだくじの前に、2人対戦の話から始めます。じゃんけんやコイントス、丁半のように、偶然性のみに依存する勝率50%の2人ゲームを、ツイッターのツイートのみでできるか、という話が@s_hskz さんのツイートをきっかけとして盛り上がりました。素数の積を利用する方法は、素数判定されにくいような数字を使うことでズルができるかどうかが不明、という疑問が残りました。そこで、このようなルールを考えました。

Aさんが最初の文字が1か2の文字列を考えて、それに何らかのあらかじめ定めたハッシュ関数をかけたものをツイート。Bさんは最初の文字が1か2かをツイート。Aさんが元の文字列をツイート。文字列の長さとハッシュアルゴリズムが解読の難しさを決めます。

このルールを、もう少しきちんと書きます。秘密の整数をn、秘密の文字列をS、ハッシュ関数をHとします。n+Sを整数nの10進数表記の文字列とSの連結であるとします。たとえば、n=1, S="abc" の時に（引用符は文字列をあらわす）、n+S="1abc" となります。Aさんは P=H(n+S) とnの条件式（上の場合では「n=1またはn=2」という条件）、Hのアルゴリズムをツイートして、Bさんがnに関する条件式 C(n) をツイートします（上の場合では「n=1」あるいは「n=2」）。その後、Aさんがn+Sをツイートします。Bさんは、P=H(n+S)となることを確認します。C(n)が真であればBさんの勝ち、偽であればAさんの勝ちです。なお、nの桁数があらかじめ決まってない時には、Sの最初の文字は数字以外であることとします。また、文字コードを気にしなくて済むように、文字列はASCII文字のみを使うこととしておきます。

それでは、2人対戦のシミュレートをします。

• Aさん「@B ツイート対戦。n=1 or 2. SHA256 base 64. Ro4ywhmeToWKsbzre3agp2PT2GTPhD5dqTw9B3sXp90」
• Bさん「@A n=2」
• Aさん「@B 1uYj9B4cowaDJ+d/vrbLjLiNKtyYFEPLMf7JnWV3+d」
• Bさん「@A ハッシュを確認。負けました。」

このゲームが公平であるためには、2つの条件が必要です。1つ目は、AさんがH(n+S) = H(n'+S'), n≠n' となるような n,S,n',S' を見つけることができない、ということです。これは、ハッシュ関数が衝突困難性を持っているということです。2つ目は、BさんがPからn+Sの値を計算できない、ということです。これは、ハッシュ関数の原像計算困難性です。すなわち、H関数のアルゴリズムと、Sの文字列の長さ（より厳密には、Sをどのように選んだかというエントロピー）が、現時点の一般的な計算機の能力では総当たり攻撃と衝突攻撃に対して安全であるとされているレベルにあることが必要です。このブログ記事を執筆している時点では、たとえばSを英数字記号まじりで30文字以上（180 bit 以上）、アルゴリズムをSHA-256としておけば、安全だろうと思います。文字数を短くするために、base 64 を加えてもいいでしょう。SHA-256のハッシュは、SHA generatorのようなサイトを使えば、簡単に計算出来ます。

nの条件を「n=0,2,5 のいずれか」とすれば、n=0 （グー）、n=2 (チョキ）、n=5 (パー）のじゃんけんができます。Aさんが選んだ秘密の数字 n と、Bさんがツイートした数字 m から、(n+m) mod 6 + 1 を計算すれば、Bさんがダイスを振ることができます。

ツイートあみだ

それでは、次にこの方法を応用してツイッターであみだくじをすることを考えます。ここまでの議論で、自然数 n を仕込めるようになったので、その自然数を初期値とした既定アルゴリズムの疑似乱数列を発生させることで、あみだくじと同じことをすることができます。ここで、あみだくじは、あみだの上に左から順番に 1,2,3,...,N の「くじ番号」が並んで、あみだの下に、左から順番に 1,2,3,...,N の「抽選結果」が振られていると考えると、くじ番号と抽選結果を対応づけるくじ引きだと考える事ができます。

N人のくじをすることを考えます。このような流れとなります。

• くじの主催者が、くじの開始とくじの対象者等の条件、抽選結果の意味（抽選結果3以下は当選、等）を宣言する。くじの数Nは、あらかじめ決めて宣言する場合と、あらかじめ決めない場合がある。
• 主催者は、乱数の初期値となる整数nと、秘密の文字列Sを決めて、ハッシュ関数のアルゴリズム、P=H(n+S)の値、疑似乱数列の生成アルゴリズムをツイートする。ここで、疑似乱数列の周期はNよりも大きいとする。
• くじの参加者が、くじを引く。Nがあらかじめ決まっている場合、N人の参加者が1人ずつ1〜Nの数字（くじ番号）を重複しないように選ぶ。主催者がくじに参加する場合は、主催者は最後に余った数字とする（主催者はあらかじめ結果を知っているため）。Nがあらかじめ決まっていない場合は、参加者はくじへの参加をツイートして、主催者が1,2,3,...とくじ番号を順番に振る。以上で、N人の参加者がそれぞれ1〜Nの「くじ番号」と対応づけられる。
• 主催者は n+S をツイートする。参加者はP=H(n+S)が成立することを確認可能である。
• nを乱数の初期値 R(0) として、あらかじめ宣言された疑似乱数列生成アルゴリズムによって、乱数列R(1),R(2),...R(N)を生成する。R(1)〜R(N)を昇順にソートしたときのR(k)の順位をA(k)とする。たとえば、N=3, R(1)=4, R(2)=2, R(3)=5の時、A(1)=2, A(2)=3, A(3)=1 である。主催差は、その計算結果をツイートする。参加者は、nと擬似乱数生成アルゴリズムが分かっているため、その計算結果が正しいことを確認可能である。
• くじ番号 k の人は、抽選結果 A(k) を引いたこととなる。

疑似乱数列のアルゴリズムの例として、線形合同法は漸化式 R(n+1) = (a R(n)+b) mod M であり、この記事を参考に、a=1664525, b=1, M=2^32=4294967296 として、R(n+1) = (1664525 R(n)+1) mod 2^32 とするのが一例です。 ここで、乱数の初期値 R(0) は M/a よりも大きくする方が良いので（あまり小さいと、A(1)=1となりやすくなってしまう）、この例では5桁以上の数字としておくと良いでしょう。

それでは、実行例です。

• Aさん「@A @B @C @D @E ツイートあみだ https://researchmap.jp/joeuzo28q-1933868/ で掃除当番を決めます。くじの参加者はメンションした5人、1番を引いた人が掃除当番です。」
• Aさん「@A @B @C @D @E ハッシュは SHA-256 base 64 で E/FMSPmF92sZmkr3cJePcFGwOXTA23te9eNAI8LUarI 乱数列は R(n+1) = (1664525 R(n)+1) mod 2^32 です。」
• Aさん「@A @B @C @D @E それでは、1〜5の数字を重複しないように選んで下さい。」
• Bさん「@A @B @C @D @E 3」
• Cさん「@A @B @C @D @E 1」
• Dさん「@A @B @C @D @E 5」
• Eさん「@A @B @C @D @E 2」
• Aさん「くじ番号は @A 4 @B 3 @C 1 @D 5 @E 2 です。13242dGvoXFI/LKmqzZhuIzm2fyqFlj48kAXqbJNImG5l がハッシュの元で、R(0) = 13242 です。」
• Aさんは疑似乱数列を計算する。R(1)=(1664525 * 13242 + 1) mod 2^32 = 566803571, R(2) = 427975640, R(3)=4286521849, R(4)=4065259430, R(5)=682905455 と計算出来る。昇順にソートすると、R(2) < R(1) < R(5) < R(4) < R(3) となり、A(1)=2, A(2)=1, A(3)=5, A(4)=4, A(5)=3となる。この計算の Excel ファイルをダウンロード。必要に応じて、計算過程をツイート。
• Aさん「@A @B @C @D @E あみだの結果は、A(1)=2, A(2)=1, A(3)=5, A(4)=4, A(5)=3 となりました。A(2)=1なので、くじ番号2番の @E さんが掃除当番です。」
• Eさん「@A @B @C @D @E 計算が正しいことを確認しました。掃除当番了解です。」

この方法では、主催者がくじの結果をあらかじめ知ることができるので、参加者の一部にそれを教えてしまう、という不正をされることが考えられます。それを防ぐためには、2人以上が秘密の整数を用意して、その合計値を乱数の初期値とします。たとえば、AさんがH(n(1)+S(1)), BさんがH(n(2)+S(2)) をツイートして、R(0) = n(1)+n(2) とします。あるいは、くじ番号が選ばれた順番に数字を並べて、上記の例では31524という5桁の数字を作り、それを n に足したものを初期値にする、という方法も考えられます。あらかじめ、その方法を宣言しておく必要があります。

おわりに

この話は、暗号理論ではビットコミットメントという話になります。電子マネーや電子投票、電子くじなどに発展します。この方法は、複雑な計算をすることなく、ツイートのみでなるべく手軽にできるようにと考えたものです。このブログ記事の著者は暗号理論の研究者ではありませんので、議論の正確さはあやしいものと思って下さい。おかしなところをみつけたら、コメントを頂けると有り難いです。

このブログ記事へのコメントはこのツイートへの返信でどうぞ。Researchmap のアカウントを持っている方は、ログインして直接コメントを書くこともできます。

数年前に書いた文書ですが、要望によりアップします。

2つの封筒があり、それぞれにお金が入ってます。片方の封筒に入っている金額が、もう片方の封筒に入っている金額の2倍となっていることが分かっています。あなたは、最初にどちらか片方の封筒を選び、中身を見る事ができます。その後、改めてどちらの封筒を選ぶか決めることができます。二度目に選んだ封筒の中身をもらうことができます。

1. 最初の封筒に1万円入っていました。この時、封筒を交換する方が得か、交換しない方が得か、あるいはどちらでも同じか？最初に選んだ封筒を封筒Aとすると、ランダムに封筒を選んだことから、封筒Aが金額の小さい封筒である確率は1/2、金額の大きい封筒である確率は1/2です。すると、もう片方の封筒Bに入っている金額は、1/2の確率で2万円、1/2の確率で5000円となります。したがって、封筒Bに入っている金額の期待値は 1/2*20000+1/2*5000=12500 より、12500円となります。封筒Aを封筒Bに交換する事で、期待値が2500円増えますから、交換する方が得です。
2. (1)の議論は、最初の封筒に入っている金額に無関係に成り立ちます。封筒Aの金額をx円(ただしxは偶数)とすると、封筒Bに2x円入っている確率は1/2、封筒Bにx/2円入っている確率は1/2なので、封筒Bに入っている金額の期待値は 1/2*2x + 1/2*(x/2) = 1.25x 円となり、封筒Aの金額x円よりも 0.25x円ほど期待値が高くなります。したがって、封筒を交換する方が得になります。封筒Aの金額が奇数であれば、必ず封筒Bの方が金額が高く、これもまた封筒を交換する方が得をしますから、結局、封筒Aの中身がいくらであっても、必ず封筒Bに交換する方が得をします。ということは、封筒Aの中身を見るまでもなく、封筒Bに交換する方が得をする、ということになります。

封筒Aを手に取った時点で、封筒Bに交換する方が得をするために、封筒Bを取りますが、ここで封筒を交換しても良いと言われると、今度は同じ議論で封筒Aに交換する方が得をします。このように繰り返すと、封筒を無限に交換し続けることになります。

以上の議論に、どこかおかしいところはあったでしょうか？というパラドックスです。

ゲームのルールに関する補足

封筒を開けた後に「封筒を変えてもいいよ」と言われる、というバージョンをよく見かけますが、その場合には、自分が大きい金額の封筒を取った場合にのみ「封筒を変えてもいいよ」と言われる、小さい金額の封筒を取ったらそのように言われなかった、という可能性があります。そのような可能性を考えて「変えてもいいよと言われたからには、封筒を変えない方がいい」という回答が成立します。封筒を開ける前から、封筒の交換が許される事をルールとして設定しておくことで、そのような可能性について考える必要はなくなり、純粋にパラドックスの部分を議論することができます。

期待値計算はこれでいいのか？

この問題に対して、期待値計算に対する信頼性の議論がよくなされます。

1. たとえば、10万分の1の確率で1兆円が当たるくじがあるとします。このくじの期待値は1000万円です。これをあなたは990万円で買うでしょうか。大金持ちであれば買うでしょうが、そうでなければなかなか買わない(買えない)と思います。一方、宝くじは期待値が購入金額よりも小さいにも関わらず、計算上の期待値以上の期待を込めて買う人もいるということです。このように、人は期待値以上の価値を認めることも、期待値以下の価値しか認めないこともあります。それは、確率の大きさ、金額の大きさ、その金額の必要性等の様々な条件によります。

   この問題で、1万円の封筒を開けて1万円をもらうことが確定したときに、1/2の確率でさらに1万円をもらうか5000円を失うかのかけをするかどうか、という判断をする時に、1万円という大金を手にしたことがないという子供と、貯金が1千万円ある大人とでは、判断が異なるかもしれません。このように、期待値から計算される価値が必ずしもその人にとっての価値と等しくならない場合がある、ということは一つの論点としておさえておいて良いと思います。

2. (1)の議論とはまた別に、そもそもこの期待値計算はおかしいんじゃないの？という議論がされることもあります。では、こう考えたらどうでしょうか。封筒を開けて1万円得た時点で、残りの封筒には2万円入っている確率と5000円が入っている確率が等しくなっている。そこで、その1万円を払って、コインを投げて、表が出たら2万円をもらい、裏が出たら5000円をもらう、という賭けをするかどうか。こういう条件だったら、1万円を出して期待値12500円の賭けをするから得だ、だからその賭けをしよう、という期待値計算は問題ないように思えます。だとすると、封筒問題はそれとはどう違うのでしょうか？
3. では、残りの封筒に2万円入っている確率が1/2であるとは限らないのではないか？という議論がされることもあります。これは、次の論点であるベイズ理論に基づいた考え方です。問題が複雑なのは、確率が1/2でなければ、いったいいくつなのか？それが確定できないところです。

ベイズ理論による説明

ベイズ推定の理論によって、封筒Aを開ける前には封筒Aの方が大きい確率は1/2だけど、封筒Aを開けて金額が分かることで、封筒Aの方が大きい確率が条件付き確率として1/2から変化する場合があり、どんな金額でも必ず1/2となるような事前確率の分布はあり得ない、という説明がなされます。

この説明は非常に説得力がありますが、Wikipedia には

This is still an open problem among the subjectivists as no consensus has been reached yet.

と書かれており、学者の間でも完全な合意が出来たわけではなさそうで、複雑な問題をはらんでいます。

より詳しい説明は、また後日…。

さいころによる説明

封筒に入れる可能性のある金額をしぼって、問題を単純化します。さいころの各面に 100, 200, 400, 800, 1600, 3200 と書いて、振って出た金額とその目の２倍を封筒に入れます。この時に、片方の封筒を開けて

1. 封筒の中身が100円ならば、封筒を換えて200円になる。
2. 封筒の中身が6400円ならば、封筒を換えない。
3. (1) (2) 以外であれば、換えることで期待値が1.25倍になる。

封筒を換えない方が得なのは(2)の一通りだけですが、(2)で封筒を換えることで期待値がぐんと(3200円も)下がります。

封筒を換えない場合、換える場合の期待値を正確に計算すると、それぞれ18900円と等しくなり、封筒を換えても換えなくても同じになります。

このように、封筒に入れる可能性のある金額とその確率を明確に定義づけると、多くの場合は矛盾なく説明ができます。「多くの場合は」としたのは、次のバリエーションBが例外として考えられるためです。

バリエーションB: 確率分布が与えられた場合

2つの封筒問題は、事前確率の分布を定めないために生じたパラドックスである、という説明がよくされますが、事前確率の分布を定めてもパラドックスが生じる場合があります (Linzer, 1994)。

バリエーションBとして記述しました。

バリエーションC

オリジナル問題では、封筒を選ぶ側は封筒を交換してもしなくても、必ずお金をもらうことができる（得をする）というルールですが、損をする可能性があるようにルールを設定したら、どうなるでしょうか。

バリエーションCを作ってみました。

バリエーションD: 連続関数の場合

封筒の中身が自然数のみではなく、連続的に正の実数の値を取りうる、とすると、自然数の金額のみが許される場合と比べて、期待値の計算が若干変わります。

詳しい説明は、気が向いたら…。

色々なバリエーション

特に分類はしませんが、色々なバリエーションについて考えてみると面白いです。

1. 「片方の封筒がもう片方の封筒の10倍の金額が入っている」場合
2. 「片方の封筒がもう片方の封筒よりも1000円多く入っている」場合
3. 「３つの封筒に、x円、2x円、4x円入っている」場合

2つの封筒問題の歴史

1953年にベルギーの数学科 Maurice Kraitchik が提案した以下の問題が、2つの封筒問題のルーツではないかとされています。

2人の同じ程度に裕福な人が、財布の中身を比べるゲームをした。このゲームのルールは、以下の通りである。財布の中身が少ない方が、多い方の中身を全額もらう。中身が同額の場合は、なにも起きない。一人の男は「私の財布の中身をA円としよう。私が負けた時には、A円を失う。私が勝つ確率を0.5とすると、私が勝った時にはA円よりも多くの金額をもらい、合計は2A円よりも大きくなる。ということは、このゲームは私にとって得だ。」相手もまったく同じように考えた。しかし、実際には2人の条件はまったく同じであり対称であるため、ゲームは公平である。2人の考え方は、どこがおかしかったか？

Martin Gardner が、1982年にAha! Gotchaという本にてこの財布ゲームを紹介しました。そして、Barry Nalebuff が1989年に2つの封筒問題形式にて紹介し、それ以降、2つの封筒形式の問題が有名なパラドックスとして広まっています。

ネクタイのパラドックスは、オリジナルの財布ゲームに近いと言えます。

終わりに

肝心なところはすべて「後日記述する」ということにしてしまいしたが、いきなり全部書いてしまっても面白くないかな、という気持ちもあります。また、数学的に厳密に、かつ分かりやすく記述しようとすると、かなり大変そうです。少しずつ、説明を書き足していく予定です。

リンク

• Two envelopes problem - Wikipedia : 詳しい解説が書かれています。このページは、主としてこのWikipediaページおよびそのリンク先の参考ページを情報源として作成しました。
• 統計に関する教材 : 青山学院大学教授美添泰人氏のページ。確率に関するパラドックス（その１）(PDF) に、2つの封筒のパラドックスが紹介されています。

1年間のサバティカル（東洋大学の交換研究員派遣制度）による、フランスのストラスブール大学での研究生活ももうすぐ終わり。あっという間の1年間だった。良い研究仲間に恵まれ、とても充実した研究生活を送ることができた。帰国の準備を進めていると、夢の世界から現実の世界へと引き戻される感覚になる。

メインの研究である不飽和水分シミュレーションについては、投稿論文がアクセプトされるまでもうしばらくこちらの共著者たちとメールで研究を続けることになりそう。あとは、8月の農業農村工学会で発表をする予定。

放射性セシウムに関する話題については、昨年の11月に日仏会館で講演をして、それなりに反響はあった。福島の問題は、フランスでもかなり関心が高い。