Section 13.3

Records and Monotone Runs

Drawing until the sequence stops increasing, waiting to beat the first value, records: answers involving e or infinite expectations.

Toolkit

For i.i.d. continuous variables, exchangeability makes any ordering of the first $k$ values equally likely, so $\mathbb{P}(\text{first }k\text{ increasing}) = 1/k!$ . Records and run-lengths are analysed by conditioning on the current extreme value and using either the tail-sum formula or a first-step (renewal) recursion.

Tail-sum: $\mathbb{E}[N] = \sum_{n\ge 0}\mathbb{P}(N>n)$ .
Run-length of increasing sequences: $\mathbb{P}(\text{run}\ge k) = 1/k!$ , giving $\mathbb{E}[N] = \sum_{n\ge 0} 1/n! = e$ .
Waiting to beat a fixed value $u$ : geometric with success probability $1-u$ , mean $1/(1-u)$ ; averaging over $U\sim\mathrm{Unif}(0,1)$ gives $\mathbb{E}[1/(1-U)]=\int_0^1 \frac{du}{1-u}=\infty$ .
First-step/ODE method: if $f(x)$ is an expected functional of the process starting from current value $x$ , write $f(x) = (\text{immediate contribution}) + \int_x^1 f(y)\,dy$ (density $1$ for uniform values), differentiate to get a first-order linear ODE for $f$ , solve with the boundary condition at $x=1$ .

Problems