有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

本格数学クイズ (確率論)

 確率に関する問題でも, 組合せ論的な意味合いが強い問題は「本格数学クイズ (組合せ論)」のページに掲載しています.

条件付き確率

クイズ《モンティ・ホール問題》

 $3$ つのドア A, B, C のうち, いずれかのドアの向こうに賞品が無作為に隠されている. 挑戦者はドアを $1$ つだけ開けて, 賞品があれば, それをもらうことができる. 挑戦者がドアを選んでからドアを開けるまでの間に, 司会者は残った $2$ つのドアのうち, はずれのドアを $1$ つ無作為に開ける. このとき, 挑戦者は開けるドアを変更することができる. ドアを変更するとき, しないときのどちらが賞品を得る確率が高いか.
(有名問題)
$2023/08/11$$2023/08/11$

答え

 ドアを変更するとき.

解説

 ドア A, B, C の向こうに賞品があるという事象をそれぞれ $A,$ $B,$ $C$ とおく. さらに, 挑戦者が A を選んだとき, 司会者が C を開けるという事象を $E$ とおく. 司会者が C を開けたとき, A が当たりである条件付き確率 $P_E(A),$ B が当たりである条件付き確率 $P_E(B)$ の大小を比較すればよい.
(1)
まず, $P(E)$ を求める. 賞品は無作為に隠されているから, \[ P(A) = P(B) = P(C) = \frac{1}{3}\] である.
  • A が当たりのとき司会者は C の他に B も開けることができるから, $P_A(E) = \dfrac{1}{2}$ であり, \[ P(A\cap E) = P(A)P_A(E) = \frac{1}{3}\cdot\dfrac{1}{2} = \frac{1}{6} \quad \cdots [1]\] である.
  • B が当たりのとき司会者は C を開けるしかないから, $P_B(E) = 1$ であり, \[ P(B\cap E) = P(B)P_B(E) = \frac{1}{3}\cdot 1 = \frac{1}{3} \quad \cdots [2]\] である.
  • C が当たりのとき司会者は C を開けることはないから, $P_C(E) = 0$ であり, \[ P(C\cap E) = P(C)P_C(E) = \frac{1}{3}\cdot 0 = 0\] である.
よって, \[\begin{aligned} P(E) &= P(A\cap E)+P(B\cap E)+P(C\cap E) \\ &= \frac{1}{6}+\frac{1}{3}+0 = \frac{1}{2} \end{aligned}\] である.
(2)
次に, $P_E(A),$ $P_E(B)$ の各値を求めて比較する.
  • $[1]$ から, \[ P_E(A) = \frac{P(A\cap E)}{P(E)} = \frac{1}{6}\div\frac{1}{2} = \frac{1}{3}\] である.
  • $[2]$ から, \[ P_E(B) = \frac{P(B\cap E)}{P(E)} = \frac{1}{3}\div\frac{1}{2} = \frac{2}{3}\] である.
$P_E(A) < P_E(B)$ であるから, ドアを変更するときの方が賞品を得る確率が高い.

参考

  • 本問は, アメリカのテレビ番組 “Let's make a deal” の中で行われたゲームに由来をもち, その司会者の名に因んで「モンティ・ホール問題」 (Monty Hall problem) と呼ばれる.
  • 全事象が互いに排反な事象 $A_1,$ $\cdots,$ $A_n$ に分けられるとき,「全確率の定理」(theorem of total probability) \[\begin{aligned} P(E) &= P(A_1\cap E)+\cdots +P(A_n\cap E) \\ &= P(A_1)P_{A_1}(E)+\cdots +P(A_n)P_{A_n}(E) \end{aligned}\] が成り立つ.
  • (2) で導いた等式 \[ P_E(A) = \dfrac{P(A)P_A(E)}{P(E)}\] は, 「ベイズの定理」(Bayes' theorem) として知られている.
  • 「モンティ・ホール問題」によく似た「$3$ 囚人の問題」「ベルトランの箱の問題」も有名である.

クイズ《ポリアの壺》

 最初, 壺の中に色 $1$ の玉が $a_1$ 個, $\cdots,$ 色 $r$ の玉が $a_r$ 個だけ入っている. 壺の中から無作為に玉を $1$ 個取り出して, その玉と同じ色の玉を $c$ 個だけ壺の中に入れ, 取り出した玉も戻すという試行を繰り返す. $n$ 回目に色 $i$ $(1 \leqq i \leqq r)$ の玉を取り出す確率はいくらか.
(有名問題)
$2024/02/09$$2024/02/09$

答え

 $\dfrac{a_i}{a_1+\cdots +a_r}.$

解説

 $n$ 回目に色 $i$ $(1 \leqq i \leqq r)$ の玉を取り出す確率を $p_n$ とおく. \[ p_n = \frac{a_i}{a_1+\cdots +a_r} \quad \cdots [*]\] であることを数学的帰納法で示す.
(i)
$n = 1$ のとき. 明らかに $[*]$ が成り立つ.
(ii)
$n = k$ ($k$: 正の整数) のとき $[*]$ が成り立つとする. また, $k$ 回目の試行を行う直前の壺の中にある色 $i$ の玉の個数を $x,$ その他の色の玉の個数を $y$ とおく. $k$ 回目に取り出す玉の色で場合に分けて考えると, \[\begin{aligned} p_{k+1} &= p_k\cdot\frac{x+c}{x+y+c}+(1-p_k)\cdot\frac{x}{x+y+c} \\ &= \frac{x}{x+y}\cdot\frac{x+c}{x+y+c}+\frac{y}{x+y}\cdot\frac{x}{x+y+c} \\ &= \frac{x(x+y+c)}{(x+y)(x+y+c)} = \frac{x}{x+y} \\ &= p_k = \frac{a_i}{a_1+\cdots +a_r} \end{aligned}\] が得られる. よって, $n = k+1$ のとき $[*]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $p_n = \dfrac{a_i}{a_1+\cdots +a_r}$ が成り立つ.

参考

  • 確率変数が時間的に変化するような確率のモデルは「確率過程」(stochastic process) と呼ばれる.
  • 本問は「ポリアの壺問題」(Polya's urn problem) として有名である.

期待値

クイズ《じゃんけんの勝者の人数》

 $1$ 回だけじゃんけんをするとき, 勝者の人数が最も多くなると見込まれるのは, 何人でじゃんけんをするときか.
(オリジナル)
$2023/06/02$$2023/06/09$

答え

 $4$ 人.

解説

 $n$ を $2$ 以上の整数とする. $n$ 人で $1$ 回だけじゃんけんをするとき, 勝者の人数を $X_n$ とおく. 求めるべきは, $X_n$ の期待値 $E(X_n)$ を最大にする $n$ の値である.
(1)
まず, 勝者が $k$ 人 $(1 \leqq k \leqq n-1)$ である確率 $P(X_n = k)$ を求める. $n$ 人のじゃんけんで, 全員の手の出し方は $3^n$ 通りある. 勝者が $k$ 人 $(1 \leqq k \leqq n-1)$ であるとき, 勝者と敗者を分ける方法が ${}_n\mathrm C_k$ 通りあり, そのおのおのに対して勝者と敗者の手の組合せが ${}_3\mathrm C_2$ 通りあるから, $X_n = k$ となる確率は \[ P(X_n = k) = \frac{{}_n\mathrm C_k\cdot {}_3\mathrm C_2}{3^n} = \frac{{}_n\mathrm C_k}{3^{n-1}} \quad \cdots [1]\] である.
(2)
次に, $X_n$ の期待値 $E(X_n)$ を求める. $X_n$ は $0$ 以上 $n-1$ 以下の整数の値をとるから, $[1]$ により, $X_n$ の期待値は \[\begin{aligned} E(X_n) &= \sum_{k = 0}^{n-1}kP(X_n = k) \\ &= \sum_{k = 1}^{n-1}kP(X_n = k) \quad (\because 0\cdot P(X_n = 0) = 0) \\ &= \sum_{k = 1}^{n-1}k\cdot\frac{{}_n\mathrm C_k}{3^{n-1}} \quad (\because [1]) \\ &= \sum_{k = 1}^{n-1}n\cdot\frac{{}_{n-1}\mathrm C_{k-1}}{3^{n-1}} \quad (\because k\,{}_n\mathrm C_k = n\,{}_{n-1}\mathrm C_{k-1}) \\ &= \frac{n}{3^{n-1}}\sum_{k = 1}^{n-1}{}_{n-1}\mathrm C_{k-1} \\ &= \frac{n}{3^{n-1}}\{ (1+1)^{n-1}-{}_{n-1}\mathrm C_{n-1}\} \\ &= \frac{n(2^{n-1}-1)}{3^{n-1}} \end{aligned}\] である. 最後から $2$ つめの等号では二項定理を使った.
(3)
最後に, $E(X_n)$ を最大にする $n$ の値を求める. \[\begin{aligned} \frac{E(X_{n+1})}{E(X_n)} &= \frac{(n+1)(2^n-1)}{3^n}\cdot\frac{3^{n-1}}{n(2^{n-1}-1)} \\ &= \frac{(2n+2)(2^n-1)}{3n(2^n-2)} \end{aligned}\] であるから, $n \geqq 3$ のとき \[\begin{aligned} &E(X_n) > E(X_{n+1}) \iff \frac{E(X_{n+1})}{E(X_n)} < 1 \\ &\iff \frac{(2n+2)(2^n-1)}{3n(2^n-2)} < 1 \\ &\iff (2n+2)(2^n-1) < 3n(2^n-2) \\ &\iff 4n-2 < (n-2)2^n \\ &\iff \frac{4n-2}{n-2} < 2^n \iff 4+\frac{6}{n-2} < 2^n \\ &\iff n \geqq 4 \quad \left(\because 4+\frac{6}{n-2} \leqq 10\right) \end{aligned}\] が成り立つ. また, \[ E(X_2) = \frac{2}{3}, \quad E(X_3) = 1, \quad E(X_4) = \frac{28}{27}\] である. よって, \[ E(X_2) < E(X_3) < E(X_4) > E(X_5) > E(X_6) > \cdots\] であるから, $E(X_n)$ は $n = 4$ のとき最大値 $\dfrac{28}{27}$ をとる.

参考

  • $n$ が小さいときの $E(X_n)$ の近似値は, 次の表の通りである.
    $n$$2$$3$$4$$5$
    $E(X_n)$$0.666\cdots$$1$$1.037\cdots$$0.925\cdots$
    $6$$7$$8$$9$$10$
    $0.765\cdots$$0.604\cdots$$0.464\cdots$$0.349\cdots$$0.259\cdots$
  • 極限値 $\lim\limits_{n \to \infty}E(X_n)$ については, こちらを参照されたい.

クイズ《夫婦円卓問題》

 $n$ 組 $(n \geqq 2)$ の夫婦 $2n$ 人が, 男女交互に, それ以外は無作為に円卓の周りに座るとき, 隣どうしに座ると見込まれる夫婦は何組か.
(有名問題)
$2023/06/09$$2023/06/09$

答え

 $2$ 組.

解説

 隣どうしに座る夫婦の総数を $X$ とおく. 求めるべきは, $X$ の期待値 $E(X)$ である.
 席に $1$ から $2n$ までの番号をつけて, 各番号 $k$ $(1 \leqq k \leqq 2n)$ に対して, 番号 $k$ の席に座る人とその右隣に座る人が夫婦であるとき $X_k = 1,$ そうでないとき $X_k = 0$ と定める. $n \geqq 2$ に注意すると, 隣どうしに座る夫婦の総数 $X$ は右隣に伴侶が座る人の総数に等しいから, \[ X = X_1+\cdots +X_{2n} \quad \cdots [1]\] が成り立つ.
(1)
まず, $X_k$ の期待値 $E(X_k)$ $(1 \leqq k \leqq 2n)$ を求める. 番号 $k$ の席に座る人とその右隣に座る人が夫婦である確率は $\dfrac{1}{n},$ そうでない確率は $\dfrac{n-1}{n}$ であるから, \[ E(X_k) = 0\cdot\frac{n-1}{n}+1\cdot\frac{1}{n} = \frac{1}{n} \quad \cdots [2]\] である.
(2)
次に, $X$ の期待値 $E(X)$ を求める. $[1],$ $[2]$ により, \[\begin{aligned} E(X) &= E(X_1+\cdots +X_{2n}) = E(X_1)+\cdots +E(X_{2n}) \\ &= 2n\cdot\frac{1}{n} = 2 \end{aligned}\] である.

クイズ《さいころですべての目を出すまでにかかる回数》

 $n$ 面のさいころがある. すべての目を出すには, 平均的に何回さいころをふればよいと見込まれるか (ヒント: 正の整数全体を値域とする確率変数 $W$ の期待値は \[ E(W) = \sum_{m = 1}^\infty m\,P(W = m)\] で定義される).
(有名問題)
$2024/01/17$$2024/01/17$

答え

 $n\displaystyle\sum_{k = 1}^n\frac{1}{k}$ 回.

解説

 事象 $A_1,$ $\cdots,$ $A_n$ のいずれかが等確率で起こる試行の反復試行において, $A_1,$ $\cdots,$ $A_n$ がすべて $1$ 回以上起こるまでに要する試行回数 $X$ の期待値 $E(X)$ を求めればよい. $A_1,$ $\cdots,$ $A_n$ のうち $k$ 個 $(0 \leqq k \leqq n-1)$ が起こった状態から別の事象が起こるまでに要する試行回数を $X_k$ とおくと, \[ X = \sum_{k = 0}^{n-1}X_k\] となる. 期待値の線形性により \[ E(X) = \sum_{k = 0}^{n-1}E(X_k) = \sum_{k = 0}^{n-1}\frac{n}{n-k} = n\sum_{k = 1}^n\frac{1}{k}\] であるから, $E(X_k)$ の値を求める. $X_k = m$ ($m$: 正の整数) となるのは, $m-1$ 回はすでに起こった $k$ 個の事象以外は起こらず, その次に残り $n-k$ 個のうち $1$ つの事象が起こる場合であるから, \[ P(X_k = m) = \left(\dfrac{k}{n}\right) ^{m-1}\dfrac{n-k}{n}\] である. よって, \[\begin{aligned} E(X_k) &= \sum_{m = 1}^\infty m\,P(X_k = m) = \sum_{m = 1}^\infty m\left(\frac{k}{n}\right) ^{m-1}\frac{n-k}{n} \\ &= \frac{n-k}{n}\left( 1-\dfrac{k}{n}\right) ^{-2} = \frac{n-k}{n}\left(\dfrac{n-k}{n}\right) ^{-2} \\ &= \frac{n}{n-k} \end{aligned}\] である. ここで第 $3$ の等号では, $r = \dfrac{k}{n}$ に対して \[\sum_{m = 1}^\infty mr^{m-1} = \frac{1}{(1-r)^2}\] が成り立つことを使った ($r = 0$ のときは自明, $0 < r < 1$ のときの証明はこちらを参照). ゆえに, 求める期待値は \[ E(X) = \sum_{k = 0}^{n-1}\frac{n}{n-k} = n\sum_{k = 1}^n\dfrac{1}{k}\] である.

参考

  • $n$ 種類のアイテムのうち $1$ 種類がランダムに封入されたカプセル・トイで全種類のアイテムを集めるにも, 平均的にこの回数繰り返せばよいと見込まれる.
  • この種の問題はしばしば「クーポン・コレクターの問題」(coupon collector's problem) または「食玩問題」と呼ばれる.
  • 無限級数 $\displaystyle\lim_{n \to \infty}\left(\sum_{k = 1}^n\frac{1}{k}-\log n\right)$ は収束し, その和 $\gamma = 0.57721\cdots$ を「オイラーの定数」(Euler's constant) と呼ぶ. \[\lim_{n \to \infty}n\sum_{k = 1}^n\frac{1}{k}\!-\!\lim_{n \to \infty}n(\log n\!+\!\gamma ) \!=\! \lim_{n \to \infty}\left(\sum_{k = 1}^n\frac{1}{k}\!-\!\log n\!-\!\gamma\right) \!=\! 0\] であるから, $n$ が十分に大きいとき, $E(X)$ は近似的に $n(\log n+\gamma )$ に等しいと言える.
  • $n$ が小さいときの $E(X)$ の値は, 次の表の通りである.
    $n$$1$$2$$3$$4$
    $E(X)$$1$$3$$\dfrac{11}{2}$
    $= 5.5$
    $\dfrac{25}{3}$
    $= 8.33\cdots$
    $n$$5$$6$$7$$8$
    $E(X)$$\dfrac{137}{12}$
    $= 11.41\cdots$
    $\dfrac{147}{10}$
    $= 14.7$
    $\dfrac{363}{20}$
    $= 18.15$
    $\dfrac{761}{35}$
    $= 21.74\cdots$
    $n$$9$$10$$11$$12$
    $E(X)$$\dfrac{7129}{280}$
    $= 25.46\cdots$
    $\dfrac{7381}{252}$
    $= 29.28\cdots$
    $\dfrac{83711}{2520}$
    $= 33.21\cdots$
    $\dfrac{86021}{2310}$
    $= 37.23\cdots$