tkenichi の日記

毒舌皮肉系恥さらし日記

クーポンコレクター問題

Math Probability

f:id:tkenichi:20120821102635j:plain

クーポンコレクター問題とは、n種類のクーポンがランダムに入っている商品について、全部そろえるにはどれくらい買えばよいか、という問題である。キャラクターグッズのおまけをそろえたりする場合を考えればわかりやすいだろう。

n種類のクーポンがすべて同じ確率 p = \frac{1}{n} であらわれるとする。よくある解法では、k個そろっている状態からk+1個そろっている状態へ遷移する確率が 1-kp = 1 - \frac{k}{n} であることに着目する。k 個から k+1 個へ遷移するためには、平均 \frac{n}{n-k} 回かかる。よって、0個の状態からn個の状態に遷移するにはこれらを全部足して

\sum_{k=0}^{n-1} \frac{n}{n-k}

である。

さて、この問題をちょっと拡張して考えてみた。n種類のクーポンがそれぞれ異なる確率で現れる場合はどうなるだろうか？その確率を p_1, p_2, \cdots, p_n とする。クーポンが現れる順番で分岐していくので、その枝ごとに確率を求めてみる。まず、 1, 2, \cdots, n の順番の場合を考える。k 個そろっている状態から k+1 個そろっている状態へ遷移する確率は p_{k+1} + \cdots + p_n であり、k 個そろっている状態にとどまっている確率は p_{1}+\cdots+p_{k} である。k 個から k+1 個へ n 回で遷移する確率は

(p_1 + \cdots + p_k)^{n-1}(p_{k+1} + \cdots + p_n)

であるから、その平均回数は

\frac{1}{p_{k+1} + \cdots + p_n}

である。ここでは k+1 番目にどの枝に分岐するかは問わないことに注意する。 1, 2, \cdots, n の順に遷移する枝の確率は

p(1,2,..,n) := \frac{p_1}{p_1 + \cdots + p_{n}} \times \frac{p_2}{p_2 + \cdots + p_n} \times \cdots \times \frac{p_{n-1}}{p_{n-1} + p_n} \times \frac{p_n}{p_n}

である。従って、すべてそろえるための平均回数は

\sum p(1,2,..,n) \sum_{k=1}^n ( \frac{1}{p_{k} + \cdots + p_n} )

である。最初の和はすべての枝についての和をあらわす。すなわち、1からnまでのクーポン番号の並び替えである。和の中身は1,2,3,...,n の順に現れた場合を記述している。

例として、n=3ですべて 1/3 のときと、(1/2,1/4,1/4) の場合で計算してみよう（前者の計算は検算のため）。
前者の場合は、すべての枝について和の中身は同じで、枝の本数は6本あるので

6 \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1} \times ( \frac{3}{3} + \frac{3}{2} + \frac{3}{1} ) = \frac{11}{2}

となる。後者の場合は (1/2,1/4,1/4) の順で現れる場合の枝の本数は2本

2 \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{1} \times ( 1 + 2 + 4 ) = \frac{7}{2}

(1/4,1/2,1/4) の順で現れる場合の枝の本数は2本

2 \times \frac{1}{4} \times \frac{2}{3} \times \frac{1}{1} \times ( 1 + \frac{4}{3} + 4 ) = \frac{19}{9}

(1/4,1/4,1/2) の順で現れる場合の枝の本数は2本

2 \times \frac{1}{4} \times \frac{1}{3} \times \frac{1}{1} \times ( 1 + \frac{4}{3} + 2 ) = \frac{13}{18}

となるので、平均値はこれらを足して \frac{57}{9} となる。

また面白い練習問題として、クーポンが3種類で (2/3, 1/6, 1/6) の確率のときと、4種類ですべて 1/4 の確率のときでは、前者のほうがそろえる平均の回数は大きくなる。

非対称の起源

Book

f:id:tkenichi:20120731211942j:plain

非対称の起源―偶然か、必然か (ブルーバックス)

非対称の起源―偶然か、必然か (ブルーバックス)

サイエンスの本で面白いのは２種類あると思う。ひとつは難しいとわかっているテーマ（素粒子とか遺伝子とか）について、新たな知見を与えることで、そのテーマをさらに深く掘り下げていくもの。もうひとつは、別々のテーマのものが思わぬつながりを持っていることを気づかせて、知的領域を広げてくれるもの。後者のタイプのものが好きな人にはこの本はとても楽しめると思う。

対称性がある法則は美しいと考えられている。一方で、右利き左利き、右脳左脳、アミノ酸の光学異性体、素粒子物理学における対称性の破れ、といった非対称な現象も数多く見られる。非対称な事例を数多く集めて、網羅的に解説するとともに、一見無関係な事柄の間の関連を見出すことによる面白さがこの本の魅力である。

興味深い仮説が２つ述べられていたので紹介しよう。

ひとつ目は、弱い力のパリティが保存されないことから来る非対称性から、Ｌ型アミノ酸の優位性が説明できるではないかということ。Ｌ型アミノ酸の優位性が地球上の進化の過程で偶然に起こったものではないことは、宇宙から飛来した隕石に含まれるアミノ酸についてもＬ型が優位であるという分析がなされていることからも推測されている。ただし、宇宙全体でＬ型アミノ酸が存在するところは局所的で、太陽系がその場所に含まれているだけだという説もある。この場合は中性子星が発する円偏光された放射線がその原因ではないかと考えられている。

ふたつ目は利き手に関する遺伝的モデルである。Ｃ遺伝子とＤ遺伝子があるとして、ＣＣ型の人は右利き、左利きになる人は５０％ずつ、ＤＣ型の人は、右利き７５％、左利き２５％、ＤＤ型の人は右利き１００％になる。このモデルで一卵性双生児の１０～２０％が右利きと左利き一人ずつからなること、両親の一人が右利きでもう一人が左利きのときに子供が左利きになる割合が、両親が二人とも右利きのとき、二人とも左利きのときの割合のほぼ中間になることをうまく説明できるのだそうだ。

Newton-Raphson 法の収束の速さ

Math

Newton-Raphson法は収束する場合は速いが、収束しない場合もある。どんな場合に収束しないのか、また収束の速さはどれくらいのものかを調べてみることにする。
実験として、
x^3+ax+b = 0
を x=0 を初期値として Newton=Raphson 法で求めるときの収束回数を調べて a,b ともに -4.0 から 4.0 までを可視化した。

f:id:tkenichi:20120826234705p:plain

収束した領域を赤色（収束回数で濃淡）、振動した領域を青色、発散した領域を黒色とした。収束回数が余り変化しないところと、わずかな違いで大きく変化しているところがある。振動する領域は a = 0 の負の領域の近傍にも存在している。

問題：

  1. 振動している領域を特徴付けると？
  2. 収束回数が大きく変化しているところのふるまいは？
  3. Newton 法の修正アルゴリズムでの振動領域は小さくなるか？

それをお金で買いますか　市場主義の限界

Book

f:id:tkenichi:20120728110141j:plain

 

それをお金で買いますか――市場主義の限界

それをお金で買いますか――市場主義の限界

 

お盆の時期に、前から気になっていた本を読むことにした。マイケル・サンデルの「それをお金で買いますか」。白熱教室の印象から、読者へ哲学的な問いかけをしていくようなものを想像していたけれど、もっと切れ味鋭く、経済学に対する強烈な問題提起であった。金融工学が華やかなりし頃には、何でも市場で取引できて証券化できるような気にさせられたけど、リーマンショック以降は市場の限界が叫ばれるようになった。これを単なる流行や、景気の波と同じように考えずに、もっと本質的な倫理や道徳と関わって考えたのがこの「それをお金で買いますか」だ。

 

お金で買えるものかどうかの議論の対象となっているのは、行列に割り込む権利（ファストトラック）、行列に並ぶ商売、成績の良い子に払うインセンティブ、カーボンオフセット、売血、デスプール（人の死を対象にした賭け）、ネーミングライツ、など。こういうものを取引することのうしろめたさを経済学はうまく説明することができない。曰く、売る人と買う人の双方の効用が高くなるのならば、それは善だ。サンデルは道徳、名誉や尊厳を市場で売買するのは腐敗であるといい、インセンティブは人に良い行いをさせるために最も効果的な方法ではないという。また、腎臓や血液を市場で売買できるようにすると、結果として貧しい人たちを食い物にするという公正さの面からの問題も指摘している。

 

税金や景気の研究だけでなく、人間の行動まで予測できるといったり、今まで売買できないと思われていたものまで市場で売買する方法を与えたりといった、経済学の傲慢さに対する反論でもあろう。一方で経済学の立場からすると、道徳の影響がまだモデルにきちんと反映されていないからだ、ということなのかもしれない。市場に限界はある、それには同意しても、限界がどこかについては、諸説あるだろう。その限界は超えてはならない一線なのか、それとも克服すべき限界なのか、それても超えたくても超えられない究極の限界なのか。。。

 

白熱教室と同じく、この本にも答えはない。自分で考えなければならないが、考えるための貴重な道しるべになる。 

見えざる宇宙のかたち

Book

f:id:tkenichi:20120623133943j:plain

見えざる宇宙のかたち――ひも理論に秘められた次元の幾何学

見えざる宇宙のかたち――ひも理論に秘められた次元の幾何学

大栗先生の「重力とは何か」と同じく、第一線の研究者が自分の研究を一般向けに解説した本だが、こちらはほとんど手加減なしという感じで、大学学部レベルの数学と物理の知識がないと用語レベルでついていけないかもしれない。その代わりに、ひも理論をこれから勉強しようという人にとっては、理論の歴史的な背景とサーベイ的な解説が読めるという点で、これ以上のものはないのではないだろうか。ひも理論を構成するピースが誰の功績なのかということも几帳面に書いてあるので、論文を探す際の手引きとしても役に立ちそう。

内容はカラビ＝ヤウ多様体を中心に、その生い立ち、ひも理論への貢献、物理学と数学とが絡み合いながら発展していく様子、現在のこの分野で残されている問題など。カラビ＝ヤウ多様体とは、ひも理論で考えられている１０次元の宇宙と４次元の時空の差の余剰次元に現れると考えられている図形のこと*1。分野的にはこの本では幾何解析と呼ばれている分野に属する。幾何解析の功績として筆者は、リッチフローを使ってペレルマンが解決したポアンカレ予想、ドナルドソン、フリードマン、ウィッテンらによる４次元トポロジーの研究、そしてカラビ＝ヤウ多様体を挙げている。

本書の後半はミラー対称性、一般相対論とブラックホール、素粒子物理、真空崩壊などについて、カラビ＝ヤウ多様体との関わりの観点から解説している。一般的な啓蒙書の解説と比べると難しいし、一度読んだぐらいではなかなかわからない。教科書や論文の副読本のような位置づけで読むのがいいと思う。

*1:ただし数学的に厳密な定義は、専門書を見てください

余次元１のRayleigh商

Math

f:id:tkenichi:20120623133719j:plain

階数1の行列で摂動したときの固有値の変化についてはすでに述べたので、今度は余次元1の射影の場合を考える。摂動の場合は行列の足し算であり、射影によって行列は射影行列の相似変換になるので、同じような議論ができるわけではない。ほとんど初歩的な計算ですぐわかる結果を列挙することにとどめる。

補題1

R を余次元1の射影演算子とする。 R = 1 -ww^{T} とかける。このとき w は R が与える余次元1の部分空間の直交補空間の基底である。 R は、余次元1の直交フレーム Q を用いて R = QQ^{T} と書ける。

補題2

対称行列 X を余次元1の部分空間に制限した線形写像は、その直交フレーム Q を用いて Q^{T}XQ とあらわせる。このとき、 \beta = w^{T} X w とすると、

\mbox{trace}(X) = \mbox{trace}(Q^{T}XQ) + \beta

が成り立つ。

補題3

射影演算子 R を用いて R^{T}XR を考えると、 R^{T}XR の固有値は Q^{T}XQ の固有値と 0 であり、 w が 0 の固有ベクトルになる。 v が w と直交している X の固有ベクトルならば、 R^{T}XR の固有ベクトルでもある。


次元を1小さくすると、trace が \beta だけ小さくなるので、それぞれの固有値がどれだけ小さくなるのかを \beta と直交補空間のベクトル w で評価できればうれしいのだが。。。