東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問5

标签：

• institute-of-science-tokyo
• Geometric-Distribution
• Coupon-Collector-Problem

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

(1) 確率 $p\in(0,1)$ で表の出るコイン投げを考える。表が出るまでの投擲回数の期待値と分散を $p$ を用いて表せ。

(2) 袋の中に $N\geq2$ 種類の玉が一つずつ入っている。無作為に一つ取り出し、種類を記録して袋に戻す操作を試行と呼ぶ。各試行は独立で、玉の種類は一様分布に従う。$k$ 種類を記録するまでの試行回数を $S_k$ とする。

(i) $S_{k+1}-S_k$ の期待値と分散を $N,k$ を用いて表せ。

(ii) $S_N$ の期待値と分散をそれぞれ $\mu,\sigma^2$ とするとき、

$$\mu=N\sum_{i=1}^N\frac1i, \qquad \sigma^2=N\sum_{i=1}^{N-1}\frac{N-i}{i^2}$$

を証明せよ。

题目描述

1. 一枚硬币在每次投掷中以概率 $p\in(0,1)$ 出现正面。求从开始投掷到首次出现正面为止的投掷次数的期望和方差，并用 $p$ 表示结果。

2. 袋中共有 $N$ 类球，每类恰有一只，其中 $N\geq2$。每轮从袋中等概率抽取一只球，记下类别后放回；各轮抽取相互独立。以 $S_k$ 表示首次记录到 $k$ 个不同类别时累计进行的抽取次数。

   1. 分别用 $N$ 和 $k$ 表示增量 $S_{k+1}-S_k$ 的期望与方差。
   2. 证明收集完全部 $N$ 类球所需次数 $S_N$ 的期望 $\mu$ 与方差 $\sigma^2$ 满足

$$\mu=N\sum_{i=1}^N\frac1i, \qquad \sigma^2=N\sum_{i=1}^{N-1}\frac{N-i}{i^2}.$$

Kai

(1)

最初の表が出るまでの回数 $T$ は成功確率 $p$ 、台 $\{1,2,\ldots\}$ の幾何分布に従う。したがって

$$\boxed{E[T]=\frac1p, \qquad \operatorname{Var}(T)=\frac{1-p}{p^2}}.$$

(2)(i)

$k$ 種類を既に記録した時点で、次の試行が未記録の種類を与える確率は

$$q_k=\frac{N-k}{N}$$

である。よって $D_k=S_{k+1}-S_k$ は成功確率 $q_k$ の幾何分布に従い、

$$\boxed{E[D_k]=\frac{N}{N-k}},$$

$$\boxed{\operatorname{Var}(D_k) =\frac{1-q_k}{q_k^2} =\frac{kN}{(N-k)^2}}.$$

(2)(ii)

$S_0=0$ とおけば

$$S_N=\sum_{k=0}^{N-1}D_k.$$

過去の全履歴を条件としても、$k$ 種類を集めた後の待ち時間は成功確率 $(N-k)/N$ の幾何分布であり、その条件付き分布は履歴に依存しない。従って $D_k$ は互いに独立であり、

$$\begin{aligned} E[S_N] &=\sum_{k=0}^{N-1}\frac{N}{N-k} =N\sum_{i=1}^{N}\frac1i. \end{aligned}$$

また

$$\begin{aligned} \operatorname{Var}(S_N) &=\sum_{k=0}^{N-1}\frac{kN}{(N-k)^2}\\ &=N\sum_{i=1}^{N}\frac{N-i}{i^2} =N\sum_{i=1}^{N-1}\frac{N-i}{i^2}, \end{aligned}$$

となり、所望の式を得る。