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

标签：

• TITech
• Geometric-Distribution
• Coupon-Collector-Problem

Author

GPT-5

Description

(1) A coin shows heads with probability $p\in(0,1)$ . Express the expectation and variance of the number of tosses needed to see the first head.

(2) A bag contains one ball of each of $N$ types, where $N\geq2$ . In each independent trial a ball is drawn uniformly at random, its type is recorded, and it is returned. Let $S_k$ be the number of trials needed to record $k$ types.

(i) Express the expectation and variance of $S_{k+1}-S_k$ in terms of $N$ and $k$ .

(ii) Show that the expectation $\mu$ and variance $\sigma^2$ of $S_N$ are

$$\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.$$

各待ち時間 $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}$$

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