アジマティクス

ここをこうするとおもしろい

【数学】三人寄れば文殊の知恵が得られることの証明

f:id:motcho:20190426070330p:plain

よく知られた定理として、以下のものがあります。

定理:3人寄れば文殊の知恵

古くから知られている定理ですが、日常的によく使う定理である割にはその証明をきちんと追ったことがある方は少ないのではないかと思います。以下ではこちらの定理の証明を解説します。

 

前提

まずは要請される前提を確認しておきます。

・3人の人間がいます。名前はまあ何でもいいですがバルタザール、メルキオール、カスパーだと長いのでA,B,Cとでもしておきましょう。

・彼らは目の前の問題に対して何らかの意思決定をします。「問題」とは例えば「明日は遊園地に行くことにしようか?」とか、「あの子に告白した方がいいだろうか?」とか、「被告人を有罪にすべきだろうか?」などのことです。

・3人はそれぞれ、ちゃんと自分で考えて意思決定をします。これはつまり「他の人の判断に影響を受けることなく」ということです。「Aがそう言うんなら俺は意見変えよう」とかそういうことはしません。彼らの判断には独立性がある、という言い方でもいいでしょう。

・3人それぞれの意思決定に対して、「正解」か「不正解」いずれかの結果が得られます。世の中の一般の問題には正解なんてないことがほとんどですが、そこはまあ、あることにします。

・彼らは一人ひとりが「正解率」というパラメーターを持っています。これが高ければ高いほどいつも正解を導けるわけで、卑近な言い方をするならこれを「頭のよさ」として捉えることもできるでしょう。これは人物ごとに決まっている値です。
例えば「Aさんの正解率は0.6」であるとした場合、Aさんはどんな問題でも常に60%の確率で正解するような人である、ということです。

・この「正解率」は、0.5から1までの間の値をとります。正解率をpと表すなら、0.5\lt p\lt 1ということ。
p\lt 1」は、「全知ではない」ということを表しています。どんな問題にも正解率100%の人は、全知の人です。それはもはや人ではありません。
また「0.5\lt p」は、「コイントスよりは賢い」ということを表しています。人間が問題に対して「ちゃんと考える」なら、さすがにコイントスで決めるよりも正しい結果が得られるだろう、くらいの意味です。

・3人の持つ正解率、すなわち頭のよさはすべて同じであるとします。誰かが突出して頭がいいということはなく、同レベルの3人が集まっていると。気の合う3人です。

これだけの前提をおいた上では、3人寄れば文殊の知恵が得られるよ、ということを言っているわけです。

定理を翻訳しておく

さて、もとの定理の成立年代は不明ですが、かなり古いと思われるため、現代的な数学の言い方ではありません。そこで、実際に証明を見ていく前にこちらの定理を現代的な言い方に翻訳しておきましょう。それはとりもなおさず、今回の問題設定を正確に把握することにもなります。

まず「3人寄る」ですが、これは彼らが「多数決で意見を決める」ことを意味します(ほんとか?)。「3人寄れば」は「3人それぞれの意見のうち過半数を獲得したものを、全員の意見として採用すれば」となります。

そして「文殊の知恵」とは高い正解率のことを表します(いいのか?)。総合すると、「3人寄れば文殊の知恵」という定理は

3人が"ちゃんと自分で考えて"問題に答えるとき、3人それぞれの意見のうち過半数を獲得したものを全員の意見とすれば、1人で答えるときよりも正解率は上がる。

と言い換えることができます。

具体的に考えてみる

ここから証明を見ていくわけですが、もう少し問いを具体的にしておきましょう。

われわれはまず何を知ることが必要でしょうか。それは「多数決で正解を選ぶ確率」、すなわち「過半数の人数が正解を選ぶ確率」です。これを3人のときと1人のときとで比べて、3人のときのほうが正解率が高くなっていれば証明終了、多数決すごいですね、というわけです。

まず表を使って考えます。3人が問題に答えた結果としてありうる正解/不正解の別は以下の8通りです。

f:id:motcho:20190425050818p:plain

この中で「3人全員が正解」または「3人のうち2人が正解」のいずれかが発生してさえいれば、多数決をとったときに正解できます。ケース1から4ですね。

そして今欲しいのは「過半数の人数が正解を選ぶ確率」でしたから、すなわち「『3人全員が正解(ケース1)』または『3人のうち2人が正解(ケース2、3、4)』のいずれかが発生」する確率を求めればよい、ということになります。

ではまず「3人全員が正解を選ぶ確率」はどれくらいでしょうか。これは「Aが正解」「Bが正解」「Cが正解」の3事象が同時に起こる確率、ということなので、単純に全てかけ合わせればよくてp^3となります。積の法則ですね。pが0.6だとしたら0.216。21.6%です。

では「3人のうち2人が正解を選ぶ確率」は? これは例えば「Aが正解」「Bが正解」「Cが不正解」などのような3事象が同時に起こる確率なので、正解を選ぶ確率pを2回、不正解を選ぶ確率\left(1-p\right)を1回かけ合わせればよいことがわかります。式で言うとp^2\left(1-p\right)pが0.6だとしたら0.144、14.4%です。

そして、この2つの状況の「いずれか」が起こっている確率を求めたいので、これらの確率を足し合わせます。「いずれか」なので足せばいいんですね。和の法則です。

ただし、ここで単純に0.216と0.144を足してはいけません。表を見れば分かる通り、「3人中2人正解」が、誰が正解するかによって3種類あるのですね。これも「いずれか」なので、0.144を3回足さねばなりません。

これらのことを総合してpを使って表現すると、「p^3+3p^2\left(1-p\right)」となります。これがすなわち、「3人のときに過半数が正解を選ぶ確率」です。pが0.6だとしたら、0.648となります。

1人のときに0.6だったのが0.648ですから、3人のときのほうが正解率は高くなっています。1人のとき0.7なら3人で0.784。0.8なら0.896。0.9なら0.972。このようにいくつか具体的な数で試してみた結果では、3人のほうが常に正解率が高くなるように思えます。グラフにして見てみるとどうでしょう。

f:id:motcho:20190425052534p:plain

横軸が一人ひとりの正解率p、縦軸が全体での(多数決を経たときの)正解率です。赤が1人のときを表し、青が3人のときを表します。

1人のときはまっすぐナナメのグラフになっています。1人だと、1人の正解率が全体の正解率と同じになるのでこれは当然ですね。

そしてこのグラフを見ると、0.5\lt p\lt 1のすべての範囲で、青(3人のとき)のほうが大きくなっていることが一目瞭然ですね。

しかし「一目瞭然だから」では証明になっていないません。実際これを示すには、少しの計算が必要です。

実際の証明

示したいことは「青のほうが赤より大きい」なので、青から赤を引いて、それが「常に正」ならば示せたと言えるでしょう。

式で書くなら以下のように表せます。これが証明すべき式です。

\color{blue}{p^3+3p^2\left(1-p\right)}-\color{red}{p} \gt 0  (ただし0.5\lt p \lt 1)

左辺を因数分解した形に式変形すると、こうなります。

p\left(2p-1\right)\left(1-p\right) \gt 0

さて、ここに現れているすべての因数において、pに0.5から1までの数を入れてみても常に正であることはすぐに分かります。そして、正の数をどれだけかけても正の数のままなので、全体としても常に正であることがわかります。

ここまでで、「0.5\lt p \lt 1の範囲では、青のほうが常に大きい」ことが言えました。これは結局、「3人のほうが常に正解率が高い」ということなので、示したかった事実そのものです。

かくして、「3人が"ちゃんと自分で考えて"問題に答えるとき、3人それぞれの意見のうち過半数を獲得したものを全員の意見とすれば、1人で答えるときよりも正解率は上がる」もとい、「3人寄れば文殊の知恵」が証明されました。

陪審定理

この話は一般化できます。すなわち、「n人よれば文殊の知恵」が証明できます。これまでずっと3を算用数字で書いてきたのはそういう理由でした。3人で多数決とったら1人のときより正解率が上がる、というのは、まぁそりゃそうだろうなって感じです。では、nを増やすとどれくらい文殊の知恵に近づけるのでしょうか?

例えば5人の場合で考えてみましょう。5人の場合で過半数が正解する状況と、その確率は以下です。

5人全員正解 → p^5

5人中4人正解 → p^4\left(1-p\right)

5人中3人正解 → p^3\left(1-p\right)^2

3人のときと同じく、人数分の正解率と人数分の不正解率をかけ合わせている形です。

そして、「5人中4人」のありうる組み合わせは、5人から4人を選ぶ個数_5\mathrm{C}_4で5通り、「5人中3人」のありうる組み合わせは5人から3人を選ぶ個数_5\mathrm{C}_3で10通りあるので、それらをすべて足し合わせると以下のような式になります。

p^5+5p^4\left(1-p\right)+10p^3\left(1-p\right)^2

0.6をpに代入してみると0.68256となり、3人のときの0.648よりも大きくなっていることが確認できます。

同じように考えると、7人の場合は以下のようになるでしょう。

p^7+7p^6\left(1-p\right)+21p^5\left(1-p\right)^2+35p^4\left(1-p\right)^3

0.6だと0.710208。どんどん大きくなってきてますね。

奇数人に限ってやっているのは、偶数人だと正解と不正解とが「同票」になって多数決ができないことが発生しうるからです。とはいえ、人数を増やせば増やすほどピッタリ同票になる確率は下がっていくので、あまり本質的なことではありません(人数が十分多ければ偶数人で考えても別にいい)。

より一般的にしましょう。3人のときでも5人のときでもn人のときでも、やっていることは同じです。

①「n人全員が正解の確率」「n-1人が正解で1人が不正解の確率」「n-2人が正解で2人が不正解の確率」……とどんどん求めていく。

②それぞれが「何通りあるか」を求め、その分定数倍する。

③それらすべてを足し合わせる。

ということで、一般的な式で書くと以下のようになるでしょう。

\displaystyle\sum_{k=0}^{\frac{n-1}{2}} {}_n\mathrm{C}_k p^{n-k}\left(1-p\right)^k

n(人数)を大きくしていったときの、この式が描くグラフの変化の様子を見てみると以下のようになっています。

f:id:motcho:20190425054442g:plain

人数が増えれば増えるほど、多数決で正解を選ぶ確率は100%に収束する、ということが見てとれますね。

まさにこの事実、すなわち「(上記の前提のもとで)人数が増えれば増えるほど、多数決で正解を選ぶ確率は100%に収束する」という事実は「陪審定理」と呼ばれており、1785年にフランスの数学者コンドルセによって示されました。

数学の分野としてはざっくり「社会選択理論」とか「意思決定論」とか呼ばれる分野のお話です。

系として

ここまで、古来から伝わる定理「3人寄れば文殊の知恵」を証明するお話でしたが、最後に少し発想の転換をしてみます。いままでは、個々人の正解率に「0.5\lt p\lt 1」という前提が置かれていましたが、今度はこの前提を「0 \lt p\lt 0.5」としてみたらどうなるでしょうか?

これはつまり全員の正解率がコイントスにも劣る、ということになるので、言うなればアホばっかりの世界です。

アホ……というかまあ愚者を3人集めて多数決を取ると、その正解率はどうなるでしょうか? グラフで見てみましょう。描かれているものは、範囲が違うだけでさっきと同じです。

f:id:motcho:20190425054839p:plain

横軸の0 \lt p\lt 0.5の範囲に注目してください。3人のとき(青色)の正解率が、常に1人のとき(赤色)より低くなっていることが見てとれます。

これは愚者が3人集まって多数決を取ると、1人で決めるよりも正解率が低い、ということにほかなりません。タチが悪いですね。

そして愚者の人数をどんどん増やしていくと、

f:id:motcho:20190425055201g:plain

どんどん正解率は下がってゆきます。

愚者は集めれば集めるほど、より愚かな集団になってゆくことがわかります。

ということで、定理「3人寄れば文殊の知恵」の系として、次の定理が導かれます。

定理:船頭多くして船山に登る

すべての船頭は愚かだ、と言っているわけではもちろんありません。念のため。船頭として「コイントスよりも正解率の低い」、いわゆる「愚かな」人たちをたくさん集めると、愚かな結果が得られてしまうよ、ということです。心に刻んでおきたい事実です。

今回紹介した2つのことわz定理は、よく逆のことを言っている定理として紹介されがちです。

かたや「人が多いといい結果が得られる」、かたや「人が多いと悪い結果が得られる」という意味をもつわけで、じゃあ一体その違いはなんなのかということになるんですが、つまり一人ひとりの正解率の違いであったと。

一人ひとりがコイントスよりも賢ければ、多数決を取るとより良い結果が出せる。

一人ひとりがコイントスよりも愚かならば、多数決を取るとより悪い結果になってしまう。

という違いでした。数学を使えばそのようなことまで分かってしまう、というわけだったんですね。

いや、まあ、ゆうて、今回の話はだいぶこじつけの感があるのであまり真に受けすぎないでほしい(そもそも「三人寄れば文殊の知恵」の辞書的な意味って「凡人でも三人集まればよい知恵が浮かぶ」だから微妙に違う)んですが、ともかく意思決定論ってのがあって、その中の定理の一つに陪審定理ってのがあって、それによって多数決が正当化されている(上掲の理想化された前提をおいた上では)、ということは事実ですので知っておいても損はないと思います。意思決定論には他にも面白い話題がたくさんありますので興味もった方はいろいろ調べてみるとよいでしょう。

謝辞

東京で「数学デー」という、数学好きが集まるイベント&コミュニティを運営しています。

今回のお話は、数学デーの参加者であり大手数学ブログ「tsujimotterのノートブック」の主宰でもあるtsujimotterさんから、数学デーで「こんな面白い話があるよ」といった感じできっかけを提供いただいた話を発展させたものです。

tsujimotter.hatenablog.com

この記事を書くにあたり、tsujimotterさんには多大なる協力をいただきました。この場を借りてお礼申し上げます。ありがとうございました。

それでは今回はこのへんで!