Distribution of a random convergent sequence of nested intervals

58 Views Asked by At

Starting from the interval $[0,1]$, generate two uniform random numbers $x_1,y_1$ and sort them so $x_1<y_1$. This yields an interval $[x_1,y_1]$. Generate two numbers uniformly from this interval, sort them as $x_2<y_2$, and repeat. This produces a nested sequence of intervals whose lengths decrease geometrically (on average), and converges to some $x^*$ almost surely. What is the distribution of $x^*$?

So far, I have the following: Let $f(a)=P(x^*\le a)$. If the two random numbers $x_1,y_1$ are both smaller than $a$ then $x^*\le a$ for sure. If $x_1<c<y_1$, then we have the same problem again with a new value for $a$, namely $\frac{a-x_1}{y_1-x_1}$. Similarly if $y_1<c<x_1$. Thus we obtain the following integral equation for $f$:

$$f(a)=a^2+2\int_0^a\int_a^1f\left(\frac{a-x}{y-x}\right)\,dy\,dx$$

At this point I'm stuck. Is this equation elementarily solvable?

1

There are 1 best solutions below

0
On BEST ANSWER

We can reparameterize the integral with $x=a-u$, $y=a+v$, and $t=\frac u{u+v}$ to eliminate one of the integrals, and use $f(1-a)=1-f(a)$ to make the integral more symmetric: \begin{align*} f(a)&=a^2+2\int_0^a\int_0^{1-a}f\left(\frac{u}{u+v}\right)\,dv\,du\\ &=a^2+2\int_0^a\int_{u/(1-a+u)}^1\frac{u}{t^2}f(t)\,dt\,du\\ &=a^2+\int_0^1\frac{f(t)}{t^2}\int_0^{\min((1-a)t/(1-t),a)}2u\,du\,dt\\ &=a^2+\int_0^1\frac{f(t)}{t^2}\min\left(\frac{(1-a)t}{1-t},a\right)^2\,dt\\ &=a^2+\int_a^1f(t)\frac{a^2}{t^2}\,dt+\int_0^af(t)\frac{(1-a)^2}{(1-t)^2}\,dt\\ \end{align*}

Let $g(a)=\int_a^1f(t)\frac{a^2}{t^2}\,dt$, $h(a)=\int_0^af(t)\frac{(1-a)^2}{(1-t)^2}\,dt$, and $K=g(1)=\int_0^1f(t)/t^2\;dt$. Then we have the ODE:

\begin{align*} \tag{1}f(a)&=a^2+g(a)+h(a)\\ \tag{2}g'(a)&=-f(a)+\frac2ag(a)\\ \tag{3}h'(a)&=f(a)-\frac2{1-a}h(a)\\ \tag{4}f(1/2)&=1/2\\ \end{align*} Because $0$ is a singular point, it doesn't make a good initial condition, but it is possible to solve this ODE with an arbitrary choice of $h(1/2)$, and determine the value of $h(1/2)$ such that $f(0)=0$. Doing this numerically, I find $h(1/2)=1/16$ (and hence $g(1/2)=3/16$) to high accuracy. Here is a picture of $f(a)$ (top), $g(a)$ (middle) and $h(a)$ (bottom) for $a\in [0,1]$.

                        enter image description here

If you think it looks a lot like a cubic, you're right! It's indistinguishable from the unique cubic that passes horizontally through $(0,0)$ and $(1,1)$, namely $f(a)=3a^2-2a^3$. And lo and behold, if you plug this into the original integral equation, it is a solution. Go figure.