The decreasing run of uniforms

Draw X1,X2,X_1, X_2, \dots independently from Uniform(0,1)\text{Uniform}(0,1). Let NN be the first index nn at which XnX_n is not the smallest of X1,,XnX_1, \dots, X_n (i.e. the first time a draw fails to set a new minimum). Then X1>X2>>XN1X_1 > X_2 > \dots > X_{N-1}, and XN1X_{N-1} is the smallest value seen before the run breaks. The value E[XN1]\mathbb{E}[X_{N-1}] can be written as a+bea + b\,e for integers a,ba, b (with ee Euler's number). Find a+ba + b.

Show hints (2)+
  1. Condition on the run length mm: the first mm draws are decreasing (density factor (1x)m1/(m1)!(1-x)^{m-1}/(m-1)! given Xm=xX_m=x) and the (m+1)(m{+}1)th exceeds XmX_m (factor 1x1-x).
  2. You'll reach k1k!(1k+21k+3)\sum_k \frac{1}{k!}\big(\frac{1}{k+2}-\frac{1}{k+3}\big); evaluate the two pieces as 01xexdx\int_0^1 xe^x\,dx and 01x2exdx\int_0^1 x^2 e^x\,dx.

Answer

Reveal answer →

2

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Asked at: Jane Street, Two Sigma

Related questions