東京大学情報理工学研究科 2022年8月実施数学第3問

Author

Description

丸石 $○$ と四角い石をランダムに左から右に一直線上に一つずつ並べる。として、丸石を確率、四角い石を確率で独立同一分布に従って並べていく。を正の整数として、四角い石が個連続して並べられた直後に並べることを停止する。の場合の例を以下に示す。

列 $○$
列 $○ ○ ○$

停止後の石の数を表す確率変数をとする。上に示した列の場合、列と列はそれぞれ、となる。

並べている途中の状態を考える。を非負整数とし、右端から四角い石が個連続している状態をとする。例えば、の時に以下の列を考える。

列 $○ ○ ○$
列 $○ ○ ○$

の場合を考えているため、列と列はまだ停止していない。列は右端から四角い石が個連続しているので状態である。列は右端に四角い石がないので状態である。状態から個石を並べたときに初めて停止条件を満たす確率をとする。ここでは非負整数である。に対して以下のような母関数を定義する。

この時、以下の問いに答えよ。

(1) の時、の平均と分散を求めよ。

(2) が満たす漸化式を求めよ。

(3) をを用いて表せ。

(4) の平均を求めよ。

Kai

(1)

の場合、四角い石が出た時点で操作は停止される。

よって、状態から個石を並べたときに初めて停止条件を満たす確率は、

となる。

よって、

となる。

(参考: これは幾何分布と呼ばれる分布である)

(2)

まず、状態は定義されない事に注意する。(あるいは、定義されても )

また、状態の場合、既に操作は停止しているので、より、となる。

の場合を考える。この時、状態遷移図は次のようになる。

この図に示した通り、

確率で四角い石が出る時、1個石を並べた上で、状態に遷移する。
確率で丸石が出る時、1個石を並べた上で、状態に遷移する。

という関係性があるので、

となる。あるいは、同じことだが、

となる。

(なお、答えの書き方は色々あると思うが、恐らく上式のいずれかだけで十分だと思う。)

(3)

(2) の結果より、

となっていく。

つまり、

となる。

特に、の場合を考えると、

整理して、

となる。

(4)

(3) の結果より、

である。

(1) と同様の考え方から、答えはである。

よって、これを微分して、代入整理すると、

となる。

(なお、を代入すると、これはとなり、(1) の結果に一致する)

Additions

コードによって、正当性を検証する。

import random

import matplotlib.pyplot as plt


def trial(M: int, q: float):
    cnt = 0
    ans = 0
    while cnt < M:
        x = random.random()
        ans += 1
        if x < q:
            cnt += 1
        else:
            cnt = 0
    return ans


def main():
    for M in [1, 2, 3]:
        for q in [0.1, 0.2, 0.3, 0.4, 0.5]:
            answers = []
            for _ in range(10000):
                answers.append(trial(M, q))
            avg = sum(answers) / len(answers)
            # plt.title()
            # plt.hist(answers)
            # plt.show()
            print("=" * 10)
            print(f"{M=}, {q=}")
            print(f"{avg=}")
            print(f"{(1 - q**M) / ((1 - q) * (q**M))=}")


if __name__ == "__main__":
    main()

M=1, q=0.1
avg=10.0076
(1 - q**M) / ((1 - q) * (q**M))=9.999999999999998
==========
M=1, q=0.2
avg=4.9994
(1 - q**M) / ((1 - q) * (q**M))=4.999999999999999
==========
M=1, q=0.3
avg=3.3353
(1 - q**M) / ((1 - q) * (q**M))=3.333333333333333
==========
M=1, q=0.4
avg=2.4801
(1 - q**M) / ((1 - q) * (q**M))=2.5
==========
M=1, q=0.5
avg=2.0025
(1 - q**M) / ((1 - q) * (q**M))=2.0
==========
M=2, q=0.1
avg=110.8138
(1 - q**M) / ((1 - q) * (q**M))=109.99999999999997
==========
M=2, q=0.2
avg=30.3796
(1 - q**M) / ((1 - q) * (q**M))=29.999999999999993
==========
M=2, q=0.3
avg=14.6192
(1 - q**M) / ((1 - q) * (q**M))=14.444444444444445
==========
M=2, q=0.4
avg=8.626
(1 - q**M) / ((1 - q) * (q**M))=8.749999999999998
==========
M=2, q=0.5
avg=5.9403
(1 - q**M) / ((1 - q) * (q**M))=6.0
==========
M=3, q=0.1
avg=1106.5573
(1 - q**M) / ((1 - q) * (q**M))=1109.9999999999998
==========
M=3, q=0.2
avg=153.216
(1 - q**M) / ((1 - q) * (q**M))=154.99999999999994
==========
M=3, q=0.3
avg=50.901
(1 - q**M) / ((1 - q) * (q**M))=51.48148148148149
==========
M=3, q=0.4
avg=24.4842
(1 - q**M) / ((1 - q) * (q**M))=24.374999999999993
==========
M=3, q=0.5
avg=13.7934
(1 - q**M) / ((1 - q) * (q**M))=14.0

確かに、大まかに一致しているため、正しいと考えられる。

Author​

Description​

Kai​

(1)​

(2)​

(3)​

(4)​

Additions​

Author

Description

Kai

(1)

(2)

(3)

(4)

Additions