递增均匀链 II

Increasing Uniform Chain II

专题: Probability / 概率
难度: L4
来源: QuantQuestion

个人笔记

题目详情

设 $X_1,X_2,\dots\sim\mathrm{Unif}(0,1)$ 独立同分布。

令 $N$ 为首次出现

X_n\ne \max\{X_1,\dots,X_n\}

的下标 $n$ 。

求 $\mathbb{E}[N]$ 。已知答案可写为 $a+be$ （ $a,b$ 为整数， $e$ 为自然常数）。求 $a+b$ 。

英文原题

Let $X_1, X_2, \dots \sim \text{Unif}(0,1)$ IID. Let $N$ be the first index $n$ where $X_n \neq \text{max}\{X_1,\dots, X_n\}$ . Find $\mathbb{E}[N]$ . The answer will be in the form $a + be$ for integers $a$ and $b$ . Note here that $e$ is Euler's constant. Find $a + b$ .

解析

事件 $\{N>n\}$ 表示前 $n$ 项每一项都是当前最大值，即

X_1<X_2<\cdots<X_n.

对连续 iid 样本，前 $n$ 项的相对次序等可能，因此严格递增的概率为 $1/n!$ 。于是对 $n\ge 1$ 有 $P(N>n)=1/n!$ ，且显然 $P(N>0)=1$ 。

用尾和公式：

\mathbb{E}[N]=\sum_{n=0}^{\infty}P(N>n)=1+\sum_{n=1}^{\infty}\frac{1}{n!}=e.

所以 $a=0,b=1$ ， $a+b=\boxed{1}$ 。

英文解析

Event $\{N>n\}$ indicates that each of the first $n$ items is the current maximum, i.e.

X_1<X_2<\cdots<X_n.

For consecutive iid samples, the relative order of the first $n$ term is possible, so the strictly increasing probability is $1/n!$ . So there was $P(N>n)=1/n!$ for $n\ge 1$ , and apparently $P(N>0)=1$ .

With Tail Sum Formula:

\mathbb{E}[N]=\sum_{n=0}^{\infty}P(N>n)=1+\sum_{n=1}^{\infty}\frac{1}{n!}=e.

So $a=0,b=1$ , $a+b=\boxed{1}$ .