この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

確率論の問題

難易度 2大学院の講義の演習問題レベル大学院数学確率論

2 つの箱 A, B と、番号 $1, 2, 3, 4$ の付いた $4$ 個の玉がある。はじめ ( $n = 0$ ) に $4$ 個の玉はすべて箱 A に入っている。各時刻 $n = 1, 2, 3, \dots$ に、 $4$ 個の玉の中から $1$ 個を等確率 $\frac{1}{4}$ で選ぶ（選択は時刻ごとに独立）。選んだ玉を、それが入っている箱からもう一方の箱へ移す。

$4$ 個の玉がはじめてすべて箱 B に入っている時刻を
$T = min {n \geq 1 : 時刻 n の操作後にすべての玉が箱 B にある}$
とする。期待値 $E [T]$ を求めよ。

この問題で使うもの

マルコフ連鎖と推移確率（説明と入口の問題）
到達確率と平均到達時間（説明と入口の問題）

この問題を解けるようになるまで（64 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

箱 B にある玉の個数 $X_{n}$ はマルコフ連鎖になる。状態は $0, 1, \dots, 4$ で、 $1$ ステップで $\pm 1$ しか動かない。

ヒント 2

$k$ から初めて $k + 1$ に到達するまでの平均時間を $t_{k}$ とおくと、 $E [T] = t_{0} + t_{1} + t_{2} + t_{3}$ である。また $t_{k} = 1 + \frac{k}{4} (t_{k - 1} + t_{k})$ が成り立つ。

ヒント 3

$t_{0} = 1$ , $t_{1} = \frac{5}{3}$ , $t_{2} = \frac{11}{3}$ となる。残りは $t_{3}$ を求めて和をとるだけである。

答えと解説

答えを見る

\frac{64}{3}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

時刻 $n$ の操作後に箱 B に入っている玉の個数を $X_{n}$ とする。 $X_{0} = 0$ である。 $X_{n} = k$ のとき、選ばれた玉が箱 A にある確率は $\frac{4 - k}{4}$ 、箱 B にある確率は $\frac{k}{4}$ である。選択は時刻ごとに独立なので、 $(X_{n})$ は状態空間 ${0, 1, 2, 3, 4}$ 上の時間的に一様なマルコフ連鎖（エーレンフェストのモデル）であり、推移確率は
$P (k, k + 1) = \frac{4 - k}{4}, P (k, k - 1) = \frac{k}{4}$
である。 $T$ は状態 $4$ への到達時刻である。

この連鎖は $1$ ステップで $\pm 1$ しか動かないので、 $0$ から $4$ へ行くには $1, 2, 3$ を順に初めて通過する必要がある。 $k$ から初めて $k + 1$ に到達するまでの時間の期待値を $t_{k}$ とおくと、強マルコフ性より
$E [T] = t_{0} + t_{1} + t_{2} + t_{3}$
である。

$k$ から $1$ ステップ進めると、確率 $\frac{4 - k}{4}$ で $k + 1$ に到達して終わり、確率 $\frac{k}{4}$ で $k - 1$ に移る。後者の場合、そこから $k$ に戻るまでに平均 $t_{k - 1}$ 、さらに $k + 1$ に到達するまでに平均 $t_{k}$ かかる。よって
$t_{k} = 1 + \frac{k}{4} (t_{k - 1} + t_{k}), すなわち \frac{4 - k}{4} t_{k} = 1 + \frac{k}{4} t_{k - 1} .$

$k = 0$ : $t_{0} = 1$ 。
$k = 1$ : $\frac{3}{4} t_{1} = 1 + \frac{1}{4} \cdot 1 = \frac{5}{4}$ より $t_{1} = \frac{5}{3}$ 。
$k = 2$ : $\frac{1}{2} t_{2} = 1 + \frac{1}{2} \cdot \frac{5}{3} = \frac{11}{6}$ より $t_{2} = \frac{11}{3}$ 。
$k = 3$ : $\frac{1}{4} t_{3} = 1 + \frac{3}{4} \cdot \frac{11}{3} = \frac{15}{4}$ より $t_{3} = 15$ 。

したがって
$E [T] = 1 + \frac{5}{3} + \frac{11}{3} + 15 = 16 + \frac{16}{3} = \frac{64}{3} .$

（検算）定常分布は $π (k) = (k 4) /16$ である。詳細つり合い $π (j) P (j, j + 1) = π (j + 1) P (j + 1, j)$ を用いると $t_{k} = \frac{\sum _{j \leq k} π ( j )}{π ( k ) P ( k , k + 1 )}$ と表せる。たとえば $t_{3} = \frac{15/16}{( 4/16 ) ( 1/4 )} = 15$ となり、上の計算と一致する。

別解

箱 B にある玉の個数を $k$ とすると、 $k$ は Ehrenfest 型の Markov 連鎖になる。推移は $k \to k + 1$ （確率 $\frac{4 - k}{4}$ ）、 $k \to k - 1$ （確率 $\frac{k}{4}$ ）である。求めるのは $k = 0$ から $k = 4$ に初めて到達するまでの時間の期待値で、 $k = 0$ から出発するので $n \geq 1$ の条件は自動的に満たされる。

$e_{k}$ を $k$ から $k + 1$ に初めて到達するまでの期待時間とする。1 回の操作で $k - 1$ に戻った場合は、 $k - 1 \to k$ にかかる時間 $e_{k - 1}$ と $k \to k + 1$ にかかる時間 $e_{k}$ が追加でかかるので、
$e_{k} = 1 + \frac{k}{4} (e_{k - 1} + e_{k})$
が成り立つ。これを解いて
$e_{k} = \frac{4 + k e _{k - 1}}{4 - k}$
を得る。

$e_{0} = 1$
$e_{1} = \frac{4 + 1}{3} = \frac{5}{3}$
$e_{2} = \frac{4 + 2 \cdot \frac{5}{3}}{2} = \frac{11}{3}$
$e_{3} = \frac{4 + 3 \cdot \frac{11}{3}}{1} = 15$

したがって
$E [T] = 1 + \frac{5}{3} + \frac{11}{3} + 15 = \frac{64}{3}$ 。

検算として、玉の個数を 2 個にした場合に同じ方法で計算すると $e_{0} = 1$ , $e_{1} = 3$ で合計 4 となり、Ehrenfest 型の既知の値 $2^{N} = 4$ と一致する。

確率論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題