東京大学 情報理工学研究科 2022年8月実施 数学 第3問 Author hari64boli64
Description 丸石 ◯ \bigcirc ◯ □ \square □ 0 < q < 1 0 < q < 1 0 < q < 1 1 − q 1 - q 1 − q q q q M M M M M M M = 4 M = 4 M = 4
列 1 1 1 ◯ □ □ □ □ \bigcirc\square\square\square\square ◯ □□□□
列 2 2 2 □ ◯ □ ◯ ◯ □ □ □ □ \square\bigcirc\square\bigcirc\bigcirc\square\square\square\square □ ◯ □ ◯ ◯ □□□□
停止後の石の数を表す確率変数を L L L 1 1 1 2 2 2 L = 5 L = 5 L = 5 L = 9 L = 9 L = 9
並べている途中の状態を考える。k k k k k k C k C_k C k M = 4 M = 4 M = 4
列 3 3 3 ◯ □ □ □ ◯ ◯ □ □ \bigcirc\square\square\square\bigcirc\bigcirc\square\square ◯ □□□ ◯ ◯ □□
列 4 4 4 □ ◯ □ ◯ ◯ \square\bigcirc\square\bigcirc\bigcirc □ ◯ □ ◯ ◯
M = 4 M = 4 M = 4 3 3 3 4 4 4 3 3 3 2 2 2 C 2 C_2 C 2 4 4 4 C 0 C_0 C 0 C k C_k C k n n n a k n a_{kn} a kn n n n a k n a_{kn} a kn A k ( t ) A_k(t) A k ( t )
A k ( t ) = ∑ n = 0 ∞ t n a k n A_k(t) = \sum_{n=0}^{\infty} t^n a_{kn} A k ( t ) = n = 0 ∑ ∞ t n a kn この時、以下の問いに答えよ。
(1) M = 1 M = 1 M = 1 L L L
(2) A k ( t ) A_k(t) A k ( t )
(3) A k ( t ) A_k(t) A k ( t ) q , M , t , k q, M, t, k q , M , t , k
(4) L L L
题目描述
从左到右独立地逐个放置圆石和方石：圆石概率为 1 − q 1-q 1 − q q q q 0 < q < 1 0<q<1 0 < q < 1 M M M M M M L L L
在尚未停止时，若末尾恰有 k k k C k C_k C k C k C_k C k n n n a k n a_{kn} a kn
A k ( t ) = ∑ n = 0 ∞ t n a k n . A_k(t)=\sum_{n=0}^{\infty}t^na_{kn}. A k ( t ) = n = 0 ∑ ∞ t n a kn . 回答下列问题。
（1）当 M = 1 M=1 M = 1 L L L
（2）求 A k ( t ) A_k(t) A k ( t )
（3）用 q , M , t , k q,M,t,k q , M , t , k A k ( t ) A_k(t) A k ( t )
（4）求一般 M M M L L L
连续成功的等待时间 ：把末尾连续方石数作为有限状态，建立首步分析递推。概率母函数 ：将停止时间分布递推转化为关于 A k ( t ) A_k(t) A k ( t ) 母函数求矩 ：由 A 0 ′ ( 1 ) A_0'(1) A 0 ′ ( 1 ) M = 1 M=1 M = 1
Kai (1)
M = 1 M=1 M = 1
よって、状態 C 0 C_0 C 0 n n n a 0 n a_{0n} a 0 n
a 0 n = { 0 ( n = 0 ) ( 1 − q ) n − 1 q ( n ≥ 1 ) \begin{aligned}
a_{0n} =
\begin{cases}
0 & (n = 0 ) \\
(1-q)^{n-1}q & (n \geq 1)
\end{cases}
\end{aligned} a 0 n = { 0 ( 1 − q ) n − 1 q ( n = 0 ) ( n ≥ 1 ) となる。
よって、
E [ L ] = ∑ n = 0 ∞ n a 0 n = ∑ n = 1 ∞ n ( 1 − q ) n − 1 q = q d d t ( ∑ n = 1 ∞ t n ) t = 1 − q = q d d t ( 1 1 − t ) t = 1 − q = q 1 ( 1 − ( 1 − q ) ) 2 = 1 q \begin{aligned}
\mathbb{E}[L] & = \sum_{n=0}^{\infty} na_{0n} \\
& = \sum_{n=1}^{\infty} n(1-q)^{n-1}q \\
& = q\frac{\text{d}}{\text{d}t}\left(\sum_{n=1}^{\infty}{t^n}\right)_{t=1-q} \\
& = q\frac{\text{d}}{\text{d}t}\left(\frac{1}{1-t}\right)_{t=1-q} \\
& = q\frac{1}{(1-(1-q))^2} \\
& = \frac{1}{q} \\
\end{aligned} E [ L ] = n = 0 ∑ ∞ n a 0 n = n = 1 ∑ ∞ n ( 1 − q ) n − 1 q = q d t d ( n = 1 ∑ ∞ t n ) t = 1 − q = q d t d ( 1 − t 1 ) t = 1 − q = q ( 1 − ( 1 − q ) ) 2 1 = q 1 V [ L ] = E [ L 2 ] − E [ L ] 2 = ∑ n = 0 ∞ n 2 a 0 n − 1 q 2 = ∑ n = 1 ∞ n 2 ( 1 − q ) n − 1 q − 1 q 2 = 2 − q q 2 − 1 q 2 = 1 − q q 2 \begin{aligned}
\mathbb{V}[L] & = \mathbb{E}[L^2] - \mathbb{E}[L]^2 \\
& = \sum_{n=0}^{\infty} n^2a_{0n} - \frac{1}{q^2} \\
& = \sum_{n=1}^{\infty} n^2(1-q)^{n-1}q - \frac{1}{q^2} \\
& = \frac{2-q}{q^2}-\frac{1}{q^2} \\
& = \frac{1-q}{q^2} \\
\end{aligned} V [ L ] = E [ L 2 ] − E [ L ] 2 = n = 0 ∑ ∞ n 2 a 0 n − q 2 1 = n = 1 ∑ ∞ n 2 ( 1 − q ) n − 1 q − q 2 1 = q 2 2 − q − q 2 1 = q 2 1 − q となる。
(参考: これは幾何分布と呼ばれる分布である )
(2)
まず、状態 C k ( k > M ) C_k(k>M) C k ( k > M ) A k ( t ) = 0 A_k(t)=0 A k ( t ) = 0
また、状態 C k ( k = M ) C_k(k=M) C k ( k = M ) a k 0 = 1 a_{k0}=1 a k 0 = 1 A k ( t ) = 1 A_k(t)=1 A k ( t ) = 1
k < M k<M k < M
この図に示した通り、
確率 q q q C k + 1 C_{k+1} C k + 1
確率 1 − q 1-q 1 − q C 0 C_0 C 0
という関係性があるので、
A k ( t ) = q t A k + 1 ( t ) + ( 1 − q ) t A 0 ( t ) ( 0 ≤ k < M ) \begin{aligned}
A_k(t)=qtA_{k+1}(t)+(1-q)tA_0(t) \quad (0 \leq k < M)
\end{aligned} A k ( t ) = qt A k + 1 ( t ) + ( 1 − q ) t A 0 ( t ) ( 0 ≤ k < M ) となる。あるいは、同じことだが、
A M − i ( t ) = q t A M − i + 1 ( t ) + ( 1 − q ) t A 0 ( t ) ( 0 < i ≤ M ) \begin{aligned}
A_{M-i}(t)=qtA_{M-i+1}(t)+(1-q)tA_0(t) \quad (0 < i \leq M)
\end{aligned} A M − i ( t ) = qt A M − i + 1 ( t ) + ( 1 − q ) t A 0 ( t ) ( 0 < i ≤ M ) となる。
(なお、答えの書き方は色々あると思うが、恐らく上式のいずれかだけで十分だと思う。)
(3)
(2) の結果より、
A M − 1 ( t ) = q t A M ( t ) + ( 1 − q ) t A 0 ( t ) = q t + ( 1 − q ) t A 0 ( t ) A M − 2 ( t ) = q t A M − 1 ( t ) + ( 1 − q ) t A 0 ( t ) = q t ( q t + ( 1 − q ) t A 0 ( t ) ) + ( 1 − q ) t A 0 ( t ) = q 2 t 2 + ( 1 − q ) q t 2 A 0 ( t ) + ( 1 − q ) t A 0 ( t ) = q 2 t 2 + ( ( 1 − q ) q t 2 + ( 1 − q ) t ) A 0 ( t ) A M − 3 ( t ) = q t A M − 2 ( t ) + ( 1 − q ) t A 0 ( t ) = q t ( q 2 t 2 + ( ( 1 − q ) q t 2 + ( 1 − q ) t ) A 0 ( t ) ) + ( 1 − q ) t A 0 ( t ) = q 3 t 3 + ( ( 1 − q ) q 2 t 3 + ( 1 − q ) q t 2 + ( 1 − q ) t ) A 0 ( t ) \begin{aligned}
A_{M-1}(t) & =qtA_{M}(t)+(1-q)tA_0(t) \\
& =qt+(1-q)tA_0(t) \\
A_{M-2}(t) & =qtA_{M-1}(t)+(1-q)tA_0(t) \\
& =qt\left(qt+(1-q)tA_0(t)\right)+(1-q)tA_0(t) \\
& =q^2t^2+(1-q)qt^2A_0(t)+(1-q)tA_0(t) \\
& =q^2t^2+\left((1-q)qt^2+(1-q)t \right)A_0(t) \\
A_{M-3}(t) & =qtA_{M-2}(t)+(1-q)tA_0(t) \\
& =qt\left(q^2t^2+\left((1-q)qt^2+(1-q)t\right)A_0(t)\right)+(1-q)tA_0(t) \\
& =q^3t^3+\left((1-q)q^2t^3+(1-q)qt^2+(1-q)t\right)A_0(t) \\
\end{aligned} A M − 1 ( t ) A M − 2 ( t ) A M − 3 ( t ) = qt A M ( t ) + ( 1 − q ) t A 0 ( t ) = qt + ( 1 − q ) t A 0 ( t ) = qt A M − 1 ( t ) + ( 1 − q ) t A 0 ( t ) = qt ( qt + ( 1 − q ) t A 0 ( t ) ) + ( 1 − q ) t A 0 ( t ) = q 2 t 2 + ( 1 − q ) q t 2 A 0 ( t ) + ( 1 − q ) t A 0 ( t ) = q 2 t 2 + ( ( 1 − q ) q t 2 + ( 1 − q ) t ) A 0 ( t ) = qt A M − 2 ( t ) + ( 1 − q ) t A 0 ( t ) = qt ( q 2 t 2 + ( ( 1 − q ) q t 2 + ( 1 − q ) t ) A 0 ( t ) ) + ( 1 − q ) t A 0 ( t ) = q 3 t 3 + ( ( 1 − q ) q 2 t 3 + ( 1 − q ) q t 2 + ( 1 − q ) t ) A 0 ( t ) となっていく。
つまり、
A M − i ( t ) = q i t i + ( ∑ j = 0 i − 1 ( 1 − q ) q j t j + 1 ) A 0 ( t ) = ( q t ) i + ( 1 − q ) t ( ∑ j = 0 i − 1 ( q t ) j ) A 0 ( t ) = ( q t ) i + ( 1 − q ) t ( 1 − ( q t ) i 1 − q t ) A 0 ( t ) ( 0 < i ≤ M ) \begin{aligned}
A_{M-i}(t) & =q^it^i+\left(\sum_{j=0}^{i-1}(1-q)q^{j}t^{j+1}\right)A_0(t) \\
& =(qt)^i+(1-q)t\left(\sum_{j=0}^{i-1}(qt)^{j}\right)A_0(t) \\
& =(qt)^i+(1-q)t\left(\frac{1-(qt)^i}{1-qt}\right)A_0(t) \quad (0 < i \leq M)
\end{aligned} A M − i ( t ) = q i t i + ( j = 0 ∑ i − 1 ( 1 − q ) q j t j + 1 ) A 0 ( t ) = ( qt ) i + ( 1 − q ) t ( j = 0 ∑ i − 1 ( qt ) j ) A 0 ( t ) = ( qt ) i + ( 1 − q ) t ( 1 − qt 1 − ( qt ) i ) A 0 ( t ) ( 0 < i ≤ M ) となる。
特に、i = M i=M i = M
A 0 ( t ) = ( q t ) M + ( 1 − q ) t ( 1 − ( q t ) M 1 − q t ) A 0 ( t ) \begin{aligned}
A_0(t) = (qt)^M+(1-q)t\left(\frac{1-(qt)^M}{1-qt}\right)A_0(t) \\
\end{aligned} A 0 ( t ) = ( qt ) M + ( 1 − q ) t ( 1 − qt 1 − ( qt ) M ) A 0 ( t ) 整理して、
A 0 ( t ) = ( q t ) M 1 − ( 1 − q ) t ( 1 − ( q t ) M 1 − q t ) = ( 1 − q t ) ( q t ) M 1 − t + t ( 1 − q ) ( q t ) M A M − i ( t ) = ( q t ) i + ( 1 − q ) t ( 1 − ( q t ) i 1 − q t ) ( 1 − q t ) ( q t ) M 1 − t + t ( 1 − q ) ( q t ) M ( 0 < i ≤ M ) = ( q t ) i 1 − t + t ( 1 − q ) ( q t ) M − i 1 − t + t ( 1 − q ) ( q t ) M ( 0 < i ≤ M ) A k ( t ) = ( q t ) M − k 1 − t + t ( 1 − q ) ( q t ) k 1 − t + t ( 1 − q ) ( q t ) M ( 0 ≤ k < M ) \begin{aligned}
A_0(t) & =\frac{(qt)^M}{1-(1-q)t\left(\frac{1-(qt)^M}{1-qt}\right)} = \frac{(1-qt)(qt)^M}{1-t+t(1-q)(qt)^M} \\
A_{M-i}(t) & =(qt)^i+(1-q)t\left(\frac{1-(qt)^i}{1-qt}\right)\frac{(1-qt)(qt)^M}{1-t+t(1-q)(qt)^M} \quad (0 < i \leq M) \\
& = (qt)^i \frac{1-t+t(1-q)(qt)^{M-i}}{1-t+t(1-q)(qt)^M} \quad (0 < i \leq M) \\
A_{k}(t) & =(qt)^{M-k} \frac{1-t+t(1-q)(qt)^{k}}{1-t+t(1-q)(qt)^M} \quad (0 \leq k < M) \\
\end{aligned} A 0 ( t ) A M − i ( t ) A k ( t ) = 1 − ( 1 − q ) t ( 1 − qt 1 − ( qt ) M ) ( qt ) M = 1 − t + t ( 1 − q ) ( qt ) M ( 1 − qt ) ( qt ) M = ( qt ) i + ( 1 − q ) t ( 1 − qt 1 − ( qt ) i ) 1 − t + t ( 1 − q ) ( qt ) M ( 1 − qt ) ( qt ) M ( 0 < i ≤ M ) = ( qt ) i 1 − t + t ( 1 − q ) ( qt ) M 1 − t + t ( 1 − q ) ( qt ) M − i ( 0 < i ≤ M ) = ( qt ) M − k 1 − t + t ( 1 − q ) ( qt ) M 1 − t + t ( 1 − q ) ( qt ) k ( 0 ≤ k < M ) となる。
(4)
(3) の結果より、
A 0 ( t ) = ( 1 − q t ) ( q t ) M 1 − t + t ( 1 − q ) ( q t ) M \begin{aligned}
A_0(t) =\frac{(1-qt)(qt)^M}{1-t+t(1-q)(qt)^M}
\end{aligned} A 0 ( t ) = 1 − t + t ( 1 − q ) ( qt ) M ( 1 − qt ) ( qt ) M である。
(1) と同様の考え方から、答えは ( d d t A 0 ( t ) ) t = 1 \left(\frac{\text{d}}{\text{d}t}A_0(t)\right)_{t=1} ( d t d A 0 ( t ) ) t = 1
よって、これを微分して、代入整理すると、
1 − q M ( 1 − q ) q M \begin{aligned}
\frac{1-q^M}{(1-q)q^M}
\end{aligned} ( 1 − q ) q M 1 − q M となる。
(なお、M = 1 M=1 M = 1 1 q \frac{1}{q} q 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 ) 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 確かに、大まかに一致しているため、正しいと考えられる。
