これは難しくないし, 直感的に明らかだと思えば一瞬で解けてしまう.
ここではわざと丁寧な証明を試みる.
2つの戦略, 噂と電話とがあるが, その効果から, 一回電話をしたらもうそれ以上何をしてもしょうがないことがわかる. したがってありえる戦略としては, 噂を n 回連続で行ってから, 最後に一回電話をするかシないかである. ここで n はゼロ以上の自然数であって, 無限を許す. 特に, 電話をしない場合は, 噂をする回数が有限だと結局来ない可能性があるので, （加算）無限回実行しないといけないことになる
# Case 1: 無限に噂だけするパターン
(噂) -> (噂) -> ... -> (噂) -> ...
# Case 2: 有限回噂して最後に電話パターン
(噂) -> (噂) -> ... -> (噂) -> (電話)
# Case 2': 特に噂の回数がゼロ回の場合
(電話)
Case 2 は電話を n 回する場合であって, Case 2' はこれの n=0 の場合だけを取り出したもの.
さてそれぞれについて求められる期待値を計算する.
Case 1
今まだ太郎君が来てない時点で噂だけで来るまでの期待値を \alpha とすると,
\alpha = \frac{1}{p} \times 1 + \left( 1 - \frac{1}{p} \right) \times (1 + \alpha)
という立式が出来る.
これは 「成功した場合は1分後、失敗した場合は1分とさらに
\alpha 分後」 掛かることを言っている. この方程式を解くことで
\alpha = p が得られる. まあわざわざ立式するほどのものじゃないけど.
Case 2' (n=0)
これは決定的で q 分後である.
Case 2
今から n 回噂をするつもりというときの期待値を \alpha_n とする.
特に \alpha_0 = q である.
そして \alpha_n については次のように立式できる.
\begin{aligned}
& \alpha_n = \frac{1}{p} \times 1 + \left( 1 - \frac{1}{p} \right) \times (1 + \alpha_{n-1}) \\
\iff & \alpha_n = 1 + \left( 1 - \frac{1}{p} \right) \alpha_{n-1} \\
\end{aligned}
さて, 今の目的は期待値 \alpha で最小のものを探すことだった.
実を言えば \alpha_n は n について単調増加であるかはまた単調減少である.
このことを P(n) : \alpha_n < \alpha_{n-1} という仮説を立てて検討することにする.
\begin{aligned}
P(n)
& \iff 1 + \left( 1 - \frac{1}{p} \right) \alpha_{n-1} < \alpha_{n-1} \\
& \iff 1 + < \frac{1}{p} \alpha_{n-1} \\
& \iff p < \alpha_{n-1} \\
\end{aligned}
もし \alpha_0 = q が p<q のとき, P(0) は成り立ち, 帰納的に P(n) がいつも成り立つことがわかる. したがって \alpha_n は単調減少するし, その極限値が p であることは既に見た.
逆に p \geq q のときは p \geq \alpha_n が成り立つことが言えて \lnot P(n) \iff \alpha_n \geq \alpha_{n-1} が従う.
以上より答えは \min\{p,q\} になる.
証明が冗長過ぎた気がする.
もっとかんたんに言えそう.
直感的なことを言えば, 最初有限回だけ噂をして, そこから電話をすることが得なのなら, 初めから電話するほうが得.
要は2つの戦略を混ぜることはどちらか一方を使うことの中間になるから, それが最小になることはないというのを言えば良かった.
Discussion