返回题库

交替升降抽样：期望次数

平均选中数字

专题
General / 综合
难度
L4

题目详情

量化面试题：交替升降抽样：期望次数。

英文原题

The numbers x1,x2,x3,…,x_{1},x_{2},x_{3},\ldots , are chosen uniformly at random from [0, 1] and inde- . pendently from each other as long as they follow the pattern x1>x2,x2<x3,x3>x_{1} > x_{2},x_{2}< x_{3},x_{3}> x4,x4<x5,…x_{4},x_{4}< x_{5},\ldots How many numbers on average can be chosen before the pattern is broken?

解析

独立均匀抽样 x1,x2,…∼Unif[0,1]x_1,x_2,\ldots\sim\mathrm{Unif}[0,1]，要求

x1>x2<x3>x4<⋯x_1>x_2<x_3>x_4<\cdots

直到模式第一次被破坏，令总次数为 NN。

设 f(t)=E[N∣x1=t]f(t)=\mathbb{E}[N\mid x_1=t]，可列积分方程并化为常微分方程

f′′(t)=−f(t),f(0)=1,f′(1)=1.f''(t)=-f(t),\quad f(0)=1,\quad f'(1)=1.

解得

f(t)=cos⁡t+1+sin⁡1cos⁡1sin⁡t.f(t)=\cos t+\frac{1+\sin 1}{\cos 1}\sin t.

因此

E[N]=∫01f(t) dt=1+sin⁡1cos⁡1−1.\mathbb{E}[N]=\int_0^1 f(t)\,dt=\frac{1+\sin 1}{\cos 1}-1.

也可写成

E[N]=sec⁡(1)+tan⁡(1)−1\boxed{\mathbb{E}[N]=\sec(1)+\tan(1)-1}

（角度单位为弧度）。

英文解析

x1>x2<x3>x4<⋯x_1>x_2<x_3>x_4<\cdots f′′(t)=−f(t),f(0)=1,f′(1)=1.f''(t)=-f(t),\quad f(0)=1,\quad f'(1)=1. f(t)=cos⁡t+1+sin⁡1cos⁡1sin⁡t.f(t)=\cos t+\frac{1+\sin 1}{\cos 1}\sin t. E[N]=∫01f(t) dt=1+sin⁡1cos⁡1−1.\mathbb{E}[N]=\int_0^1 f(t)\,dt=\frac{1+\sin 1}{\cos 1}-1. E[N]=sec⁡(1)+tan⁡(1)−1\boxed{\mathbb{E}[N]=\sec(1)+\tan(1)-1}