公約数、素数、そしてバーゼル問題

Jul 17, 2012

2人が同時に好きな自然数を叫びます。
A：「10」
B：「132」
この2つの数字はどちらも2で割り切れます。難しい言葉で言うと「この2つの数字の公約数は2」ということです（小学校で習うんだったかな）。

ではもう一度
A：「37」
B：「111」
この2つの場合はどうでしょう。すぐに分かりますがこの2つの数字には公約数はありません。難しい言葉でいうと「この2つの数字は互いに素」ということです。

ではここで問題「任意に2つの数字が互いに素である確率は？」

ちょっと実験してみようにもこれはなかなか難しいです。
というのも、任意の自然数ですから、10とか250とかはもちろん
20482093840734198720491209341412987461298402971029347019823740194
や
93410974246817469817648164815451276453725653666635467341618253600027
みたいのでもいいですし、、、というか、こういう数字も公平に出てこないと実験になりません。

さあ数字を言え！といってこんな数字を挙げられる人はいないでしょう。 じゃあコンピューターで、といっても無限にある自然数をすべて公平に挙げるのは無理でしょう。

しかし人間の知性に限界はありません。この問題を理論的に解きましょう。

例えば、8と16の公約数は2、4、8となりますが、互いに素かどうかを見るには素数の公約数だけみればいいということに注目します。 この例なら4で割れるかどうかを調べはしません。素数2で割れるかを見るだけです。
15と105なら素数3で割れます。 8と105なら素数2、素数3、素数5、素数7…と素数を順に調べてどの素数も共通の公約数になっていない、つまり互いに素だと分かります。

任意の自然数Nが素数pで割れる確率は、{1}/{p}であるというのは分かりますか？
例えば、素数3で割れる数というのは3\;,6,\;9,\;12,\;\cdotsとなります。つまり全自然数の3つに1つが素数3で割れる自然数だということになります。 パッと選んだ自然数が3で割れるかは3つに1つ、つまり確率1/3となります。

同様に素数5で割れる確率は1/5、素数13で割れる確率は1/13、、、素数pで割れる確率は1/pとなります。

従って自然数N_1とN_2がどちらも素数pで割れる確率は1/p^2となります。

ということは自然数N_1とN_2が素数pを公約数に持たない確率は1-1/p^2となります。

自然数N_1とN_2が互いに素ということはあらゆる素数が公約数でないということなので、その確率は

P=\prod_{i=1}^{\infty}\left(1-\frac{1}{p_i^2}\right)

です。なんとも複雑そうな式ですが、この値は幾らになるでしょうか？

結論だけ言うと、

P=\prod_{i=1}^{\infty}\left(1-\frac{1}{p_i^2}\right)=\frac{6}{\pi^2}=0.607927\cdots

です。なんとこんなところに円周率が出てきます！

\frac{\pi^2}{6}という部分は「バーゼル問題」という数学の歴史的難問（解決に100年！）に端を発し、数学の最大の未解決問題とされる「リーマン予想」にも関わるネタで、 とてもここでは書ききれません。

火星に猫はいるか？

Feb 09, 2012

火星に生物はいるだろうか？生物のいる確率はどのくらいだろうか？順を追って求めてみよう。

まずは火星に人間がいる確率をP_\text{human}としよう。例えば…P_\text{human}=0.0000001\%くらいかな。

よし、次に火星に犬がいる確率をP_\text{dog}としよう。なんとなく犬は人間よりいそうなんで、P_\text{dog}=0.000001\%とでもしてみるか。

どんどん続けよう。次に火星にアメンボがいる確率をP_\text{water strider}としよう。これはきっと人間なんかよりずーっといる確率が高いだろう。よしP_\text{water strider}=0.001\%だ。

ここで中間報告。では、火星に人間も犬もアメンボもいない確率はいくつになるだろうか。それは、”（人間がいない）かつ（犬がいない）かつ（アメンボがいない）”確率となるので、次式で与えられる。

P_\text{no life}=(1-P_\text{human})(1-P_\text{dog})(1-P_\text{water strider}) =99.9999999\%\times 99.999999\%\times 99.999\%=99.9989989\%

なるほど…しかし、まだ他にも調査すべき生物はたくさんある！象がいる確率、マントヒヒがいる確率、ムカデがいる確率、カピバラがいる確率…どれもきっと確率は0ではないだろう。

ある生物がいる確率をP_{i}とする。iは生物の種別を表していている。ものの本によると生物は1億種という説もある。それらが火星にいる確率が平均して0.000001\%とすると、火星にまったく生物がいない確率は、

P_\text{no life}=\Pi_{i=1}^{100000000}(1-P_{i})=(99.999999\%)^{100000000}\sim 37\%

となる。ちょっと待てよ、、、ということは、火星に何か生物がいる確率は、

1-P_\text{no life}\sim 63\%

これは驚いた！火星にはきっと何かいるぞ！

上記の推論はどこがおかしいか分かりますが？

男の子？女の子？

Dec 20, 2011

「二人の子供問題」という有名な確率のトピックです。

昼休み。食事も終えて、職場の仲間とまったりとコーヒーを飲んでいます。誰ともなしに家族の話題になりました。

独りモノのあなたな職場の仲間Aさんにこんな質問をしました。

  • 質問1：子供は何人いますか？
  • 回答1：二人です

では、ここで問題

  • 問1：Aさんの子供が、二人とも男の子の確率は？

あなたはAさんに更に質問をぶつけました。

  • 質問2：では、男の子はいますか？
  • 回答2：はい

なるほど。では、ここで問題

  • 問2：Aさんの子供が、二人とも男の子の確率は？

もう一人Bさんが隣に座っています。Bさんは今日はたまたま子供を連れてきています。男の子です。

あなたはBさんにも質問をしました。

  • 質問3：子供は何人いますか？
  • 回答3：二人です

ふーむ、、、ここで問題

  • 問3：Bさんの子供が、二人とも男の子の確率は？

問2と問3の違いが分かりますか？AさんもBさんも二人子供がいて、少なくとも一人は男の子であることが分かっています。

ちなみに解答は（男の子が生まれる確率と女の子が生まれる確率は等しいとしましょう）

  • 解1：1/4
  • 解2：1/3
  • 解3：1/2

です。

メルセンヌ素数

Dec 20, 2011

確率のネタではないですが、小話をひとつ

NtRandでは”Mersenne-Twister”と呼ばれる一様乱数生成アルゴリズムが採用されています。 このアルゴリズムで生成される乱数は2^{19937}-1、実に6002桁という途方もない長い周期をもっています。

さて、この数は”メルセンヌ素数”と呼ばれる一群の数字のうちの一つで、これが”Mersenne-Twister”の語源になっています。

メルセンヌ素数とは、素数のうちで2^{n}-1という形で書けるもののことです。 つまりMarsenne-Twisterの周期はn=19937のメルセンヌ素数です。 2001年5月現在、メルセンヌ素数は47個見つかっています。n=19937のメルセンヌ素数は24番目のものです。

1644年、マラン・メルセンヌさんが n=2,3,5,7,13,17,19,67,127,257がメルセンヌ素数であると主張しました。 残念なことに彼はn=61,89,107を見逃していました。

更に残念なことに、、、

1903年、アメリカで行われた数学会でフランク・ネルソン・コールなる人物が発表のため登壇しました。タイトルは「大きな数の素因数分解」。

彼はまず黒板に2^{67}を書き下しました。

2^{67}=147,573,952,589,676,412,928

そこから1を引き、そして次に

193,707,721\times761,838,257,287

の計算を行いました。その結果は、、、147,573,952,589,676,412,927! その間彼は一言も口をきかず、静かに席に戻りました。その後会場は万雷の拍手が沸いたそうです。

メルセンヌさんの主張から250年以上経って、2^{67}-1が素数でないことが分かったのです。

今ではn=127も素数ではないことが分かっています。

サンクトペテルブルグのパラドックス

May 25, 2010

某国、華やかなカジノの街。
ルーレット、スロットマシーン、カード…有象無象どもが一攫千金を目論んで目を血走らせて必死にもがいている。
さて今日はどのゲームでひと稼ぎしようか…ふと片隅にあるゲームに目がとまる。

「サイコロを転がして出た目が1なら1円、2なら2円…出た目と同じ額を賞金として進呈！」

なんとも幼稚なギャンブルだが、まぁいいや。ちょっとやってみるか。 参加費用は4円か。サイコロなんだから5か6を出せばもうかるじゃないか、チョロイチョロイ。
…1時間後…
すっかりスッカラカンになった彼は道端でボロ雑巾のようになっていた。

もちろん、確率を熟知したあなたはこのゲームには参加しないはずですね。 そう、期待値の問題です。このゲームの賞金の期待値 E は、
E=1\times \frac{1}{6}+2\times \frac{1}{6}+3\times \frac{1}{6}+4\times \frac{1}{6}+5\times \frac{1}{6}+6\times \frac{1}{6}=3.5
です。賞金は 3.5円しか期待できないのに参加費が4円。長い目でみるとどんどんと負けが込んでいくのです（ちなみに1枚300円の宝くじの期待値は大体142円だそうです）。

リベンジだとばかりに再びカジノにやってきた彼。今度は確率の勉強もしっかりしてきた。 うーん、どのゲームも期待値を計算するとマイナスのものばかりか（当たり前。ギャンブルは胴元が儲かるようになっている）…なまじ確率の勉強をしたのでどのゲームも割に合わないと感じてしまうなぁ。 ふと片隅にあるゲームに目がとまる。
「コイントスゲーム！外れなし！表が出たら賞金は倍！！ただし裏が出たらゲームオーバー」
つまり、
  • 1回目で裏が出たら賞金1円
  • 2回目で裏が出たら賞金2円
  • 3回目で裏が出たら賞金4円
  • 4回目で裏が出たら賞金8円
  • （以下賞金は倍々）
なるほど面白そうだ。おっといけない、軽々に飛びついては痛い目に逢う。まずは期待値を計算してみよう。
各パターンの確率は、
  • 裏：1/2
  • 表裏：(1/2)^2
  • 表表裏：(1/2)^3
  • 表表表裏：(1/2)^4
  • 表表表表裏：(1/2)^5
  • （あとは分かるでしょう）
となるので、期待値は
E=1\times\frac{1}{2}+2\times\left(\frac{1}{2}\right)^2+4\times\left(\frac{1}{2}\right)^3+8\times\left(\frac{1}{2}\right)^4+\cdots=\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\cdots=+\infty
こりゃ凄い、何と期待値は無限大だ！幾らでも儲かるってことか！！で、参加費はいくらだって？1億円か。安い安い！！よ～し、やるぞ！！！…はたして彼の運命やいかに…

どうです？あなたはこのゲームに参加しますか？参加費100円でもやらないのではないでしょうか？（ちなみに100円以上の賞金を手にするには、7回連続して表を出す必要があります）。

でも確かに期待値は無限大…腑に落ちませんね。これが「サンクトペテルブルグのパラドックス」です。

石器時代からあるモンテカルロシミュレーション

May 24, 2010

モンテカルロシミュレーションの第1歩として、100パーセントどの教科書にも載っている例題があります。
どの教科書にも載っていて、このサイトに無いのも悔しいので載せておきます。

一様乱数から円周率を求めよう

1辺が1の正方形を用意します。そこに4分の1円を描いておきます。この正方形内に一様に点を打っていき、（円内の点の数）/（全点の数）を計算すると、 これは（4分の1円面積）/（正方形の面積）に近づいていきます。
（4分の1円面積）/（正方形の面積）はすなわち \pi/4 なので、（円内の点の数）×4 /（全点の数）は円周率 \pi に近づいていきます。
 

コンカツの数学

May 19, 2010

モテモテで我が世の春を謳歌していたあなたは、いよいよ真剣に結婚を考えることにしました。しかし焦って貧乏くじを引きたくない！できるだけいい条件の人と結婚したい！
あなたは勝負はこの1年と決めて、ある結婚相談所に登録することにしました。そこはかなり値段が張るだけはあって「今後1年で100人のお相手の紹介を保証」とのこと。ただし…
  • (1) 前もって相手のプロフィールなどは見せられない（条件などは会うまで分からない）
  • (2) 1度に1人しか会えない
  • (3) 交際を断った場合に次の人を紹介する
  • (4) 一度断った相手とは二度と会えない（キープは不可）
  • (5) こちらが OK すれば相手は必ず応じる。そしてゴールイン！
という条件付きです。
この人だ！と思ってももしかしたら次にもっといい人が現れるかも…でもそうこうしているうちに1番の人を見逃してしまっているかも…これは綿密なる戦略が必要だ！

そこであなたは先ず勇気を出して最初の何人かを見逃して（観察して）、その後「これまでに見逃した人より高条件の人」が現れたら問答無用でその人をゲットする、という戦略を採用することにしました。

この戦略だと、見逃す人数が少なすぎると、高条件の人を見逃す確率は減るけども低条件の人を選んでしまう確率も増える。見逃す人が多すぎると、最高条件の人を見逃してしまうかもしれない…では何人を見逃すことで最高の相手をゲットする確率が一番高くなるでしょうか？

結論を先に言うと、最初の37人を見逃すのが最良の戦略で、その場合最高の相手をゲットする確率は約37.1%となります。

ここから先は数学の話

N 人の見合い相手（今の例では N=100）のうち、見逃す人数を s\;(0\leq s&lt N) とする。
本当の No.1 の相手が j\;(j=1,2,\cdots,N) 番目にいる場合で、しかもその人を選ぶ確率を P_{j} と書くとしよう。
P_{j}を考えてみよう。これは

（j 番目に最高の相手がいる確率）×（そこに達する確率）

と定義される。
前者の確率は 1/N となる（完全にデタラメなので一様分布）。
後者の確率は、運命の j 番目の相手に至るまでに出会う（j-1）人のうちの最高の人が、最初の s 人に含まれていればいいというのは分かるだろうか？ もし（j-1）人のうちの最高の人が最初の s 人に含まれていなければその人に出会った時点で婚活は終了し、運命の人には出会えないことになるからである。 逆にこの人が最初の s 人に含まれていれば、観察期間が終了して運命の j 番目の相手に出会うまでは見逃した人より高条件の人には出会わないことになる。 というわけで、後者の確率は s/(j-1) である。結局 P_{j} は、
P_{j}=\frac{1}{N}\times\frac{s}{j-1}\;(j=s+1,\;s+2,\;\cdots\;N)
となる（j が 1 から s までの場合は最高の人を見逃してしまった！ということで出逢う確率は 0）。
最高の相手に出会う確率は P_{j} の和、つまり
P=\sum_{j=s+1}^{N}P_{j}=\frac{s}{N}\sum_{j=s+1}^{N}\frac{1}{j-1}
となる。あとはこれを最大にする s を見つければよいことになる！

ちなみにこの 37% という何ともキレの悪い数字は一体何かというと、
\frac{1}{\text{e}}=0.367879\cdots
です。何とこんなところに自然対数の底 \text{e}=2.71828\cdots が！！
 

黄金のフラフープ

May 18, 2010

この一様乱数（連続）を利用したゲームは
http://beetama.blog14.fc2.com/blog-date-200807.html
に掲載されていたものを参考にしました。ペコリ。

ルール

1箇所に赤い丸印（基準点）がつけてあるリングがあります。リングの任意の2箇所にボタンを使って切り込みを入れます。その結果リングは2つに分割されますが、そのうち赤い丸印がない方があなたの取り分、もう一方が闇のオーナーの取り分となります。

  • あなたの取り分が大きい場合：あなたの勝利。闇のオーナーとの取り分の差額が手に入る。
  • あなたの取り分が小さい場合：あなたの負け。闇のオーナーとの取り分の差額を支払う。
要するに基準点、切り込み1、切り込み2の3点を円周上にランダムに配置しているだけなのです。その位置は一様分布（連続）に従っていて、範囲は 0\sim 360[度]になっているというわけ。 3点をデタラメにばら撒いているだけなので、どっちに基準点が入るかは5分5分のような気がする。ならば勝敗は5分5分なんでしょうか？

[スタート]ボタンをクリックするとリングが回転します。その後、同じボタン（[最初の切り込み]となっている）をクリックすると赤い三角形の箇所に切り込みが入り、更に同じボタン（[次の切り込み]となっている）をクリックすると2箇所目に切り込みが入ってリングは停止します。 あなたの取り分が緑色で示されます。あなたは見事勝利することができるでしょうか？勝率や成績を調べてみてくださいね（果たして5分5分？）。