NTTデータ数理システム新卒採用試験<数学>問題紹介 第四回 ~確率~

  • HOME
  • NTTデータ数理システム新卒採用試験<数学>問題紹介 第四回 ~確率~

※試験の設定は2023年度時点の情報であり、2024年度以降は変更の可能性があります。試験内容についてはエントリーされた方にお送りする情報をご確認ください。

こんにちは、シミュレーション & マイニング部の大坪と申します。昨年に引き続き、当社の入社試験問題を紹介する企画の第四回です。今年度はこの記事のみの予定です。

入社試験問題例

2022年度に出題した問題の中から、私が担当した確率の問題を紹介します。

問題. 2つの壺 A、B があり、合わせて $N$ 個のボールが入っているとする。
次の操作をくり返し行う: $N$ 個のボールの中から一様な確率でボールを1個選択し、$\varepsilon$ の確率で何もせず、$1-\varepsilon$ の確率でそのボールを今いる壺とは異なる壺へ移動させる( $0 < \varepsilon < 1$ とする)。
ただし初期状態では、$N$ 個のボールは全て壺 A に入っているとする。
以下のとおり記号を定義するとき、設問に答えよ。上記操作を $t$ 回行った後に、壺 A 内にあるボールの個数の確率分布を $N+1$ 次元のベクトル値関数 ${\bm P}(t)$ で表すことにする。わかりやすさのためベクトルの添え字は 0 始まりとし、${\bm P}(t)$ の第 $i$ 成分 $P_i(t)$ はボールの個数が $i$ 個の確率を表すとする。

(1) 上記操作に伴う確率分布の変化は、$N+1$ 次正方行列 $K$ を用いて、${\bm P}(t+1) = K{\bm P}(t)$ と表される。${\bm P}(t+1) = K{\bm P}(t)$ の第 $i$ 行( $0\leq i\leq N$ )を必要に応じて場合分けして書き下しなさい。
(2) 操作をくり返し行うと、確率分布は定常分布 ${\bm P}^{\rm S}$ に収束する。定常分布は ${\bm P}^{\rm S} = K{\bm P}^{\rm S}$ を満たすことを使って ${\bm P}^{\rm S}$ を求めよ。

(2022年度 株式会社NTTデータ数理システム 入社試験問題)

実はこの問題は、エーレンフェストの壺という熱力学第二法則に関するトイモデルが元になっています。その面白さについて紹介する前に、まずは問題の解説から始めたいと思います。

解答

(1) $t + 1$ 回目の操作後に壺 A 内にボールが $i$ 個あるためには、$t$ 回目の操作後のボールの個数は $i-1, i, i+1$のいずれかである必要があります。したがって、${\rm P}_i(t+1)$ は ${\rm P}_{i-1}(t), {\rm P}_i(t), {\rm P}_{i+1}(t)$ の式で書き表すことができます。例えば、$i-1$ 個から遷移するには壺 B からボールが選択される必要があるので(その確率は$(N-(i-1))/N$)、${\rm P}_{i-1}(t)$ の係数は $1-\varepsilon$ の確率と合わせて $(1-\varepsilon)(N-i+1)/N$ となります。同様に全ての遷移パターンを考えることで、答えは以下の通り求めることができます。$i = 0, N$ の境界のケースに気をつけましょう。

${\rm P}_0(t+1) = \frac{1-\varepsilon}{N} {\rm P}_1(t) + \varepsilon {\rm P}_0(t)$  
${\rm P}_i(t+1) = (1-\varepsilon) \left(\frac{N-i+1}{N} {\rm P}_{i-1}(t) + \frac{i+1}{N} {\rm P}_{i+1}(t)\right) + \varepsilon {\rm P}_i(t) ~~~(1\leq i\leq N-1 の場合)$  
${\rm P}_{N}(t+1) = \frac{1-\varepsilon}{N} {\rm P}_{N-1}(t) + \varepsilon {\rm P}_{N}(t)$  

(2) まず ${\bf P}^{\rm S} = K{\bf P}^{\rm S}$ について、式変形により $\varepsilon$ を消去することができます:

${\rm P}_0^{\rm S} = \frac{1}{N} {\rm P}_1^{\rm S}$
${\rm P}_i^{\rm S} = \frac{N-i+1}{N} {\rm P}_{i-1}^{\rm S} + \frac{i+1}{N} {\rm P}_{i+1}^{\rm S} ~~~(1\leq i\leq N-1)$  
${\rm P}_N^{\rm S} = \frac{1}{N} {\rm P}_{N-1}^{\rm S}$  

具体的に ${\rm P}_1^{\rm S}$、${\rm P}_2^{\rm S}$ あたりを ${\rm P}_0^{\rm S}$ を使って書き表すと ${\rm P}_1^{\rm S} = N {\rm P}_0^{\rm S}$、${\rm P}_2^{\rm S} = N(N-1)/2 \cdot {\rm P}_0^{\rm S}$ となり、一般の $i$ について ${\rm P}_i^{\rm S} = {}_NC_i {\rm P}_0^{\rm S}$ となることが予想できますが、実際これが上記の式を満たすことは容易に確かめられます(実際の試験では二項係数の公式をいくつかヒントとして与えています)。確率分布なので和が 1 になるという条件から $P_0^{\rm S} = 1/2^N$ と求まり、最終的な答えは ${\rm P}^{\rm S}_i = {}_NC_i/2^N$ となります。

エーレンフェストの壺について

さて小問 (2) の結果によると、定常状態において壺 A 内のボールの個数は $n = N, p = 1/2$ の二項分布に従うことがわかります。二項分布は平均が $np$、標準偏差が $\sqrt{np(1-p)}$ なので、定常状態ではボールの個数は $N/2$ の周りを揺ら揺らと変動することになります。一方、初期状態である $i = N$ の状況が再び現れる確率は、$1/2^N$と$N$ について指数的に小さい値となります。これは具体的に計算すると、$N = 100$ ならおよそ$2^{100}\simeq 10^{30}$ 回に一度、$N = 1000$ ならおよそ$2^{1000} \simeq 10^{301}$回に一度しか起こらない事象であると見積もることができるので、ほぼ確実に元に戻ることはないと言えます。

選択したボールを他方の壺に移動するという操作は、逆再生したものも同じ規則にもとづいて起こり得ます。それにも関わらずボールの個数の移り変わりを見れば、不可逆な方向性があるように見えるというのが不思議なところです。エーレンフェストの壺は、運動の基本法則に「時間の向き」がなくても、数多くの要素からなる系では特別な状態からありふれた状態への一方向の変化がほぼ確実に起こるということを示しています。そういう意味で、熱力学第二法則における不可逆性の説明に用いられるモデルとなっています。エーレンフェストの壺と「時間の向き」の議論に興味を持った方は、こちらの動画をお勧めします。

なお本問題では、本家のエーレンフェストの壺モデルに加えて $\varepsilon$ という移動させるかどうかの確率を追加していますが、これは $\varepsilon$ を付けないと確率分布が収束しないというちょっとした事情があります。必ず移動操作を行うことにすると、操作回数の偶奇でボールの個数の偶奇が決まってしまうためです。詳しくはマルコフ連鎖の収束条件をお調べください。

応募者募集!

当社の筆記試験では、会社の雰囲気を伝える機会でもあると考え、解きがいのある面白い問題を出題するようにしています。興味を持っていただけた方は、ぜひ説明会にお越しください!

アカリク NTTデータ数理システム 求人情報ページ

監修:株式会社NTTデータ数理システム 機械学習、統計解析、数理計画、シミュレーションなどの数理科学を 背景とした技術を活用し、業種・テーマを問わず幅広く仕事をしています。
http://www.msi.co.jp NTTデータ数理システムができること
「数理科学の基礎知識」e-book無料ダウンロードはこちら