東京工業大学 情報理工学院 数理・計算科学系 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}.$$

考点

• 几何分布的矩：把“等待首次成功”和“等待下一种新球”的次数识别为几何分布，并计算其期望与方差。
• 集齐问题的分段求和：将 $S_N$ 分解为各阶段独立等待时间之和，依据当前已记录种类数确定成功概率并汇总均值和方差。

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}$$

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