※この記事は同日投稿の "Birthday Envelope" を翻訳したものです。

NTTドコモ R&D Advent Calendar 2023 の6日目の記事です。

はじめに

こんにちは！私はカリフォルニアにあるNTTドコモの子会社，DOCOMO Innovations, Inc. の Senior Research Engineer としてモバイル通信ネットワークの最適化に携わってる David と申します。業務では，ランダム性がある中で最良の結果を選択をする手法である確率的最適化を使っています。もしジャンケンで勝つ戦略を知っているなら，それはそれは確率的最適化を実行していることになります。この記事では，確率的最適化と無線ネットワークに関連する，逆説的で面白い結果についてご紹介していきます。昨年の記事と同様に，数式はなるべく避けて直感的なわかりやすさを優先していきます。

封筒問題

以下に記述する問題は「封筒問題」として知られており，1987年には未解決問題とされていました (参照：Cover and Gopinath, "Open Problems in Communication and Computation")。より一般的なバリエーションである「二つの封筒問題」は有名な「モンティホール問題」 (ゲームショーで3つのドアのうち1つを選ぶ問題) の親戚です。

あなたと私は列車で長旅をしています。そこで時間をつぶすためにゲームをすることにしました。ここに2つの封筒があり，それぞれの中には数字が1つ書かれた紙が1枚ずつ入っています。その数字は私が書いたものです。私はそれぞれ異なる数字を選びました。あなたは大きい数字が入った方の封筒を選びたいとします。ただし，あなたはどちらかの封筒を選んで，紙に書かれた数字を見てから，その封筒をそのまま選んでもよいし，もう一方の封筒へ選び直すこともできます。最終的にあなたが選ばなかった封筒を私がもらいますので，せーので数字を見せあって勝負しましょう。大きい数字を選んだ人がそのラウンドの勝者です。その後，次のラウンドへ移ります。長旅なのでこのゲームを繰り返しプレイすることになります。

もしランダムに封筒を選ぶと，もう一方の封筒を見ても見なくても関係なく，あなたは平均して半数のラウンドで勝つでしょう。さて，あなたは平均して半数以上のラウンドで勝つための戦略を考えることができますか？

もし私が「あなたは半数以上のラウンドで勝つことができる」と言ったらどう思いますか？私を信じるかどうかにかかわらず，あなたはどのようにこのゲームをプレイしますか？

例えば封筒を開けて「-3.14」という数字を見て，それが小さい数字だと思い，もう一方の封筒を選ぶことにしたと想像してみてください。別のラウンドでは「42」という数字を見て，それがまだ小さいと思い，もう一方の封筒を選ぶかもしれません。「90,210」を見たら交換しますか？「1,234,567,890」ではどうですか？または「6.022 * 10²³」という数字だったら？この例の中のひとつくらいは「大きな数字だからその数字なら交換しない」と思ったでしょう。

書かれた数字のパターンを考えれば，あなたは交換しないと判断できる「十分に大きな」数字を正確に見つけることができます。その「十分に大きな数字」である閾値を $\alpha$ と定義し，あなたが最初に選ぶ封筒の数字を $\epsilon_1$ と定義し，もう一方の封筒の数字を $\epsilon_2$ と定義しましょう。これで，あなたの戦略を次のように定義することができます：

$\displaystyle \text{if}~\epsilon_1 \gt \alpha~\text{最初に選んだ封筒のまま; } \\ \text{if}~\epsilon_1 \lt\alpha~\text{もう一方の封筒に交換する}$

簡単ですね？あなたが $\alpha$ を決めておけば，平均して半数以上のラウンドで勝てるでしょう。さて，私を信じますか？

本当だろうか？

証明は比較的簡単ですが，難しい数式を抜きにして，Scaffolding という方法で理解を深めてみましょう。Scaffolding とは難しい問題を解く際に仮定や制限を加えて単純化してから問題を解く方法です。その後，いくつかの仮定を取り除き，再び解き方を考えます。このプロセスを繰り返すことで，元の難しい問題をより深く理解していくことができます。例えるなら，富士山 (標高3,776メートル) の登山の前に，まず小牧山 (標高85.9メートル) の登山から始め，徐々に高い山で練習を積んでいくことです*1。

この節では確率の基本的な知識を必要とします。数式を使わない解説は，次の節で説明いたします。

Scaffolding としてこの問題を考えていきます。封筒の数字は，6面体の公平なサイコロで決まると仮定しましょう。まず私がサイコロを1回だけ投げて，出た数字をそのまま1枚目の封筒に入れるとします。次に，もう1つの封筒に入れる数字は，最初の封筒の数字とは別の数字が出るまでサイコロを投げ続けて決めます。すると， $\epsilon_1, \epsilon_2 \in \{1,2,3,4,5,6\}$ かつ $\epsilon_1 \neq \epsilon_2$ が成り立ちます。サイコロと確率について知っていれば，閾値 $\alpha=3.5$ を設定することができます。これは公平な6面サイコロの数字の期待値です。図1の一番左の表にあるように， $\alpha=3.5$ ならば30種類のパターンのうち24種類のパターン (つまり半数以上のラウンド) で勝てます。 $\alpha=3.5$ は賢い戦略と言えます。

閾値 $\alpha$ をあまり賢くない方法で選んだらどうでしょうか。例えば $\alpha=2$ (図1の左から2番目) を設定すると30戦23勝に， $\alpha=1$ (図1の左から3番目) を設定すると30戦20勝になり，どちらも半分以上の確率で勝つことはできます。最悪なのは， $\alpha\lt 1$ や $\alpha\geq 6$ で，30戦15勝になります。 $\alpha\lt 1$ は封筒を切り替えないことと等価であり， $\alpha\geq 6$ は常に封筒を切り替えることと等価です。封筒を切り替えないことと封筒を常に切り替えることは，基本的に同じ戦略 (つまり，ランダムに封筒を1つ選んでそれに固執する) なので，半数のラウンドでしか勝てないことになります (参照：図1の左から4番目)。

これで，単純化された ("Scaffolded" と呼ぶ) 問題において，3つのことが真であると証明されました。第一に，あなたはこのゲームに半分以上の確率で勝つことができる。第二に，封筒の数字が取り得る範囲内に閾値 $\alpha$ の値があれば，半分以上の確率で勝つことができる。第三に，2つの数字が必ず異なる ( $\epsilon_1 \neq \epsilon_2$ ) という条件は非常に役に立つ情報です。

より抽象的な議論

条件によっては半分以上の確率で勝つことができるという証拠が得られたので，いくつかの条件を外して抽象的な考え方に進んでみましょう。私たちの閾値 $\alpha$ に焦点を当て，封筒の値についてあり得る3つのシナリオを考えます。シナリオ1は $\alpha$ が両方の封筒の値より小さい場合 (つまり， $\alpha \lt \epsilon_1$ かつ $\alpha \lt \epsilon_2$ )，シナリオ2は $\alpha$ が両方の封筒の値より大きい場合 (つまり， $\alpha\gt\epsilon_1$ かつ $\alpha \gt \epsilon_2$ )，シナリオ3は $\alpha$ が両方の封筒の値の間にある場合 (つまり， $\epsilon_1 \lt \alpha \lt \epsilon_2$ または $\epsilon_2 \lt \alpha \lt \epsilon_1$ ) です。シナリオ1と2は， $\epsilon_1$ と $\epsilon_2$ の大小関係によってさらに条件を分割することができますが，これは後述しますが，深く分析する必要ありません。

シナリオ1では，最初に選んだ封筒のまま保持することになります。シナリオ2では，封筒を常に交換することになります。これらのシナリオでは，最初にどの封筒を見るかをランダムに選ぶと仮定すると，平均して半分の確率で勝ちます。シナリオ3では， $\epsilon_1 \lt \alpha \lt \epsilon_2$ の場合には常に封筒を交換して常に勝ち， $\epsilon_2 \lt \alpha \lt \epsilon_1$ の場合には常に封筒を保持して勝ちます。

復習すると，シナリオ1と2では半分の確率で勝ち，シナリオ3では100%の確率で勝ちます。勝利の確率はすべてのシナリオの加重確率です (つまり，各シナリオで勝つ確率と各シナリオが発生する確率との積をとり，すべてのシナリオについて和をとる)。したがって，シナリオ3が発生する限りは半分以上の確率で勝ちます。つまり，勝利の確率はシナリオ3がどれだけ頻繁に発生するかに直接依存します。

例えば，3つのシナリオが同じ確率で発生する場合 (つまり，シナリオ1，シナリオ2，およびシナリオ3がそれぞれ1/3の確率で発生する場合)，平均して約66％の確率で勝ちます (1/3 * 1/2 + 1/3 * 1/2 + 1/3 * 1 = 2/3)。別の例として，シナリオ3が絶対に発生しない場合，勝率は50％です (1/2 * 1/2 + 1/2 * 1/2 + 0 * 1 = 1/2)。最後の例として，シナリオ3が半分の確率で，シナリオ1と2がそれぞれ4分の1の確率で発生する場合，勝率は75％です (1/4 * 1/2 + 1/4 * 1/2 + 2/4 * 1 = 3/4)。

結果について考察

上記のアプローチから，取り得る値の範囲内に閾値がある場合，半分以上の確率で勝つことができることを学びました。しかし，取り得る値の範囲が分からない状況ではどうやって閾値を決めていけばよいでしょうか？非常に単純な方法として，最初のラウンドで見た数字を閾値として使用することができます。サイコロの例を考えれば，生成される (封筒に入れられる) ランダムな数字の中央値を推測するのが賢いアプローチだと直感的に分かります。したがって，多くのラウンドをプレイすることを前提として，いくつかのラウンドをプレイしていく過程で中央値の推定値を更新することが，より賢いアプローチかもしれません。

哲学的に言えば，未知のランダム性に直面しても一貫性を保つことが報われる (つまり，妥当な $\alpha$ を固定できれば半分以上の確率で勝つ) ということを示しました。私の仕事に戻ると，ドコモが運営するモバイルネットワークには，毎日多くの未知のランダム性 (例えば，ユーザーの位置，ユーザーの動き，または周囲の温度など，ネットワークに影響を与える様々な要素) に直面するため，ネットワークの運用パラメータ (例えば，電力レベルやリンク割り当て) を適切に設定する必要があります。パラメータを選択する際に賢い戦略をとれればネットワークの運用が改善されます。

誕生日

以下に述べる問題は「ハッシュ衝突」や「バースデー攻撃」と関連しているためコンピュータ科学者の間で人気があります。それが一部の無線ネットワークの運用に関係していることは，もしかしたらあまり知られていないかもしれません。

列車が停車してあなたは下車しました。あなたは駅前に新しくオープンした評判の喫茶店に到着しますが，ちょうど私もあなたと同じ時刻に到着します。喫茶店の注文カウンターは1つ。2人が同時に注文することはできないので，お先にどうぞと相手に譲り合います。どちらが先に注文するかを決めるためにコインを投げることにします。しかし，もし3人が同時に到着したらどうでしょうか？もしかしたら，もっと複雑なコイン投げが必要かもしれません。そして10人が同時に到着したら？誰が最初で，2番目で，3番目で…と順番を決めるためのシステムが必要になります。

そのようなシステムの一つとして，私たち一人一人がランダムに番号を選び，その番号に従って列を作るというものがあります。例えば，10人が1から10の間の番号を選ぶとします。1を選んだ人が最初に，2を選んだ人が次に行く，というように進めます。説明を明確にするために，番号を選んで順番を決めるプロセスを「ラウンド」と呼びます。2人以上が同じ番号を選んでしまった場合，彼らはいったん待機して次のラウンドに参加することになります。例えば，2人が1を選び，他の8人がそれぞれ異なる番号を選んだ場合，1を選んだ2人は最初のラウンドで他の8人が行くのを待ってから次のラウンドに参加します。

このシステムは機能しますが問題がないわけではありません。例えば，10人が1から10の間の番号をランダムに選ぶ場合，多くの人が同じ番号を選んで次のラウンドで待たされる可能性が非常に高くなります。逆に，10人が1から1,000,000の間の番号をランダムに選ぶ場合，2人が同じ番号を選ぶ可能性は非常に低いですが，次に行く人を決めるために各番号について順番に尋ねるのに長い時間がかかります（例えば，「90210を選んだ人はいますか？ 90211を選んだ人はいますか？」など)*2。数字の範囲が狭いと，同じ数字を選ぶ人の確率が高くなりますが，範囲が広いとラウンドの時間が長くなります。

$P$ 人いる場合，どれくらい大きな範囲 $R$ を選ぶべきでしょうか？さらに，全員が1回のラウンドで注文できる確率 (つまり，2人以上が同じ番号を選ばない確率) はどのくらいでしょうか？

Scaffolding で理解する

誕生日のパラドックスをよくご存知でしたら次の節に進んでください。 まず考えられる Scaffolding は，少なくとも2人が存在して範囲が1より大きいと仮定することです。すなわち， $P\geq2$ および $R\gt1$ です。さらに，その人たちは範囲内で一様なランダム性で番号を選ぶと仮定します (つまり，すべての数字が同じ確率で選ばれる)。いま，あなたがこのラウンドで注文できる確率について考えるとき，他のどの数字もあなたの数字と異なっている必要があります。全員がこのラウンドで注文できる確率について考えるとき，すべての数字が異なっている必要があります。この違いを理解するためにいくつかの単純な例を試してみましょう。この記事で深く考えたいのは後者です。

あなたと私だけでラウンドを始めます (すなわち， $P=2$ )，あなたがこのラウンドで注文できるならば，すなわち全員が注文できるということになります。範囲 $R=2$ の場合，4つのパターンがあります (つまり，2人とも1を選ぶ，2人とも2を選ぶ，あなたが1を選び私が2を選ぶ，あなたが2を選び私が1を選ぶ) で，これらは同じ確率で発生します。これら4つのパターンのうち，半分のパターンでは2人ともこのラウンドで注文できます。範囲が $R=3$ の場合，9つのパターンがあり，そのうち3つで私たちはこのラウンドで注文できません (つまり，2人とも同じ番号を選ぶ，それが1，2，3のどれであれ)。したがって，9つのパターンのうち6つで2人ともこのラウンドで注文できます。一般に， $P=2$ の場合，私たちが同じ番号を選ぶ確率は $1/R$ であり，2人が異なる番号を選ぶ確率は $(R-1)/R$ です。

3人の場合 (すなわち， $P=3$ ) になると面白くなります。まず， $R=2$ の場合，あなたがこのラウンドで注文できる確率は1/4です (例えば，あなたが1を選び，他の2人とも2を選ぶ)。しかし，3人全員が1ラウンドで注文できる確率は0です (少なくとも2人はどうしても同じ番号を選んでしまうため)。 $R=3$ の場合，全員がこのラウンドで注文できる確率は6/27です (可能な27のパターンのうち，6パターンだけ全員が異なる番号を選べます)。 $R=4$ の場合，全員がこのラウンドで注文できる確率は24/64です。全員が異なる番号を選ぶパターンの数は $R$ 個の数字から $P$ 個だけ重複せずに選ぶすべての組み合わせ，すなわち $R!/(R-P)!$ (ここで $n!=n*(n-1)*(n-2)*...2*1$ ) です。すべてのパターンはの数， $R$ 個の数字から $P$ 個だけ重複を許して選ぶすべての組み合わせ，すなわち $R^{P}$ です。

全員がこのラウンドで注文できる確率は次の式で表現できます。

$\displaystyle P(\text{all go}) = \frac{\frac{R!}{(R-P)!}}{R^P} = \frac{R!}{R^P (R-P)!}$

一方，誰かがこのラウンドで注文できない確率 (つまり少なくとも2人が同じ数字を選ぶ確率) は，確率1から上記の確率を引いて

$\displaystyle P(\text{not all go}) = 1 - P(\text{all go}).$

$P=3$ かつ $R=3$ の場合， $P(\text{all go})=6/27\approx 0.22$ になります。 $P=3$ かつ $R=4$ の場合， $P(\text{all go})=24/64 = 0.375$ になります。 $P=3$ かつ $R=5$ の場合， $P(\text{all go})=60/125\approx 0.48$ になります。そして， $P=3$ かつ $R=6$ の場合， $P(\text{all go})=120/216\approx 0.55$ になります。 $R$ が大きくなるにつれて，たしかに1ラウンドですべての人が行く確率は上昇しますが，確率の増加量は緩やかになります。どの程度の確率なら妥当か，何らかの方法で見積もる必要があります。経験則として， $N\approx \sqrt{R}$ の場合， $P(\text{all go}) \approx 0.5=P(\text{not all go})$ となり，1ラウンドで全員が注文できる確率をほぼ同じにするためには，範囲は少なくとも人数の二乗をとる必要があります。

$P(\text{all go})$ の方程式の面白い部分は，指数関数的増加と階乗的増加の性質によって簡単に騙されてしまう点です。一般的な例は， $R=365$ および $P=23$ の場合， $P(\text{all go}) \approx 0.49$ となり，これは「23人いると少なくとも2人の誕生日が一致する可能性が高い」という「誕生日のパラドックス」として知られています。よくある思い違いは2つあります。まず，この現象は，任意の2人 (またはそれ以上) の誕生日が一致する確率についてのものであり，あなた以外の22人の中から1人があなたの誕生日と一致することとは別の話です。

2つ目の思い違いは，指数関数的増加 (すなわち， $R^{P}$ ) と階乗的増加 (すなわち， $R!$ ) の違いにあります。問題を単純化して， $N$ 人の中から2人が範囲 $R$ から同じ数字を選んでいないか調べることにします。 $N$ 人の中で2人が同じ数字を選んだかどうかを総当りで調べるために必要な比較回数は $N*(N-1)/2$ です。例えば， $N=2$ の場合は比較回数は1回， $N=3$ の場合は3回， $N=4$ の場合は6回，そして $N=23$ の場合は253回の比較が必要です。比較を行うことを，不公平なコインを投げることと考えてみましょう。例えば，この不公平なコインは99.7%の確率で表が出て，0.3%の確率で裏が出ます (1/365が約0.3%)。いまコインを1回投げたときには表が出ると予想するでしょう。10回連続で投げたときには10回とも表が出ると予想するかと思います。では253回投げたときに253回連続で表が出ると予想しますか？コインの投げる回数は $N$ に伴って急速に増加します。一方，表が出る確率は $R$ を増やすことで上がりますが，決して100%にはなりません。

喫茶店の列と無線ネットワークの関係

有名な「誕生日のパラドックス」は，無線ネットワークとどのように関連しているのでしょうか？無線ネットワーク上でのユーザの通信方法の一つに，ランダムアクセスがあります。ランダムアクセスではユーザは「ランダムに」通信を開始します。しかし複数のユーザが同時に通信するのを避けたいです。喫茶店の例えに立ち返ると，無線デバイスは列に並んでお茶を注文する人々と同じで，ネットワークを介して通信することがお茶を注文することに相当します。ランダムアクセスの利点は，制御が完全に分散されており，処理のオーバーヘッドが最小限であることから，ユーザがシームレスにネットワークに出入りできることです。

ランダムアクセスでは，ユーザは事前に定められた範囲からランダムな数字を選び，その数字からゼロに達するまでカウントダウンしてから通信します。別のユーザが同じ番号を選んだ場合，私たちは「衝突」と呼ぶものが発生します。以前の喫茶店の注文の例えでは，それぞれの人はその場に並んでいる人数を調べて，衝突を防ぐための範囲を見積もることができました。ランダムアクセスの目的の一つは，それぞれの人が他の人と協調すること (他の人の人数を調べること) を最小限にすることです。つまり，ランダムアクセスな通信においてはユーザはネットワーク内の他のユーザの数を知らされませんし，ユーザ自身が調べることもありません。したがって，衝突が発生した場合，ユーザはランダムに数字を選ぶ範囲を増やします。つまり，衝突が発生する場合は，範囲が十分に大きくないことを意味するので次のラウンドに向けて範囲を大きくします。逆に，衝突が発生しない場合は，ユーザ数に対して範囲が大きすぎる可能性があります。

まとめ

封筒の問題では，ランダムな数字に対して2回目の機会，つまり封筒を交換することで，半分以上の確率で勝つことができました。未知のランダム性があっても，この追加のチャンスによって，私たちは直感が最初に示唆するよりも良い結果を得られます。

誕生日のパラドックスは，自分以外の人が自分と衝突し得ることだけでなく，自分以外の人同士で衝突し得ることを示しています。そこでは，めったに発生しないイベント (衝突) の発生確率であってもどこかで発生する確率が急速に増加することがあります。実は，衝突は無線ネットワーク上でかなり頻繁に発生し，それは安定的な通信を妨げます。

ランダム性を含むいくつかの数学的問題について面白いと感じていただければ幸いです。また，難しい問題に取り組む際に Scaffolding という考え方が便利であることを知っていただければ嬉しいです。これがこの記事を書いた私のもう一つの目標でもありました。もし Scaffolding や難しそうな問題の取り組み方についてもっと知りたい場合は，George Polya の "How to Solve It" という本を強くお勧めします。これは数学のスキルレベルにかかわらず，誰でも読める素晴らしい本です。

私の日々の仕事の大部分は，数学を使ってこのランダム性に対処することです。数学についてもっと学びたい場合，確率論，統計学，最適化 (例えば，組み合わせ最適化や確率的最適化)，情報理論などのトピックが，また工学の側面では，コンピュータネットワークや通信理論に関するトピックがあなたにとって興味深いものになると思います。

著者：David Ramirez，翻訳：井上義隆

*1:Wikipedia, "List of mountains and hills in Japan by height" によると小牧山は日本で最も小さな山

*2:注文の順序をもっと早く決める方法もありますが，ここでは番号の範囲によってラウンドの時間が増加する方法のみを考えます