Uniformly Decreasing Chain

Expectation · Hard · Free problem

Let $X_1, X_2, \dots$ be IID $\text{Uniform}(0, 1)$ random variables. Define the stopping time

$N = \min\{n : X_n \neq \min(X_1, \dots, X_n)\}$

In words, you keep drawing uniforms as long as each new draw sets a new minimum. You stop at the first draw that fails to beat the current record. The value $X_{N-1}$ is the last record-setting minimum.

Compute $E[X_{N-1}]$. Report your answer to the nearest thousandth.

(Hint: you may find it helpful to solve the "Uniformly Increasing Chain" problem first.)

Hints

  1. Define $m(x)$ as the expected final minimum given the current running minimum is $x$. Condition on whether the next draw beats $x$ or not.
  2. You will get an integral equation: $m(x) = \int_0^x m(t) \, dt + x(1 - x)$. Convert it to an ODE by differentiating both sides.
  3. The resulting ODE is $m'(x) - m(x) = 1 - 2x$ with $m(0) = 0$. Solve using an integrating factor $e^{-x}$ and evaluate $m(1)$.

Worked Solution

How to Think About It: Think of this as a gambling problem. You are drawing uniforms and tracking the running minimum. The chain keeps going as long as each draw beats the current record (goes lower). The question asks: when the chain finally breaks, how small was the last record? Your gut says: the minimum can get pretty small, but it's fighting against the fact that each successive record is harder to beat. The expected minimum should be somewhere noticeably below $0.5$ but not too close to $0$.

Quick Estimate: After 1 draw the expected minimum is $0.5$. After 2 draws (given the second sets a new minimum), the expected minimum of 2 uniforms is

/3$. The chain length $N - 1$ has a geometric-like distribution -- on average around $e \approx 2.7$ draws are record-setters (this is related to the harmonic series). So the expected minimum should be roughly
/(e) \approx 0.37$, but actually lower since conditioning on the chain continuing biases toward smaller values. The exact answer turns out to be $3 - e \approx 0.282$.

Approach: Define $m(x)$ as the expected final minimum given the current minimum is $x$, then derive and solve an integral equation.

Formal Solution:

Let $m(x)$ be the expected value of the eventual minimum of the chain, given the current running minimum is $x$. The next draw $X \sim U(0,1)$ determines what happens:

  • If $X \geq x$: the chain breaks. The minimum stays at $x$, so the contribution is $x$.
  • If $X < x$: the new minimum is $X$, and the chain continues. The contribution is $m(X)$.

By the law of total expectation:

$m(x) = \int_0^x m(t) \, dt + \int_x^1 x \, dt = \int_0^x m(t) \, dt + x(1 - x)$

To solve this integral equation, differentiate both sides with respect to $x$:

$m'(x) = m(x) + 1 - 2x$

This gives the first-order linear ODE:

$m'(x) - m(x) = 1 - 2x$

The boundary condition is $m(0) = 0$ (if the current minimum is 0, it cannot decrease further).

Using the integrating factor $\mu(x) = e^{-x}$:

$\frac{d}{dx}\left[m(x)e^{-x}\right] = (1 - 2x)e^{-x}$

Integrate the right side by parts:

$\int (1 - 2x)e^{-x} \, dx = (2x + 1)e^{-x} + C$

(This can be verified by differentiating.) So:

$m(x)e^{-x} = (2x + 1)e^{-x} + C$

$m(x) = 2x + 1 + Ce^x$

Applying $m(0) = 0$: $0 = 1 + C$, so $C = -1$. The solution is:

$m(x) = 1 + 2x - e^x$

To get $E[X_{N-1}]$, we need $m(1)$, since before any draws the "current minimum" is effectively

$ (the maximum possible value, guaranteeing the first draw always sets a new record):

$m(1) = 1 + 2 - e = 3 - e \approx 0.282$

Bonus -- connection to the increasing chain: If the companion problem ("Uniformly Increasing Chain") asks for the expected maximum $M(0)$ of an analogous increasing chain, the answer is $e - 2$. Note that $(3 - e) + (e - 2) = 1$. This is not a coincidence: if $X_i \sim U(0,1)$, then

- X_i \sim U(0,1)$, and the minimum of $\{X_i\}$ equals
$ minus the maximum of $\{1 - X_i\}$.

Answer: $E[X_{N-1}] = 3 - e \approx 0.282$.

Intuition

This problem illustrates a powerful technique for sequential problems: define a value function that captures the "state" of the process (here, the current minimum), write an integral equation using the law of total expectation, then convert to an ODE. The trick of differentiating an integral equation to get a differential equation is broadly useful -- it appears in renewal theory, optimal stopping, and many inventory/queueing models.

The symmetry with the increasing chain ($m(1) + M(0) = 1$) is a beautiful consequence of the reflection symmetry of the uniform distribution. This kind of symmetry argument -- if it works -- saves you half the computation and serves as a powerful sanity check. In practice, look for symmetries like this whenever you solve one version of a problem and wonder about the complementary version.

Open the full interactive solver →