4
$\begingroup$

Short version: Start with a closed interval of length $t>0$ and repeatedly remove a random and uniformly distributed subinterval of length $1$ so long as this is possible. For $t$ large, what is the asymptotic of the expected value $\varphi(t)$ of the number of steps that this process will run?

Long version:

Consider the following random process: start with a closed interval $I_0 = [0,t]$ of length $t>0$. Now repeat the following process: at step $\ell$, randomly and uniformly choose a $u$ such that the open interval $\mathopen]u,u+1\mathclose[$ is included in $I_\ell$ if such $u$ exists, and let $I_{\ell+1} = I_\ell \setminus \mathopen]u,u+1\mathclose[$. (Note: at every stage, $I_\ell$ is a finite union of closed intervals, and “uniformly” refers to the Lebesgue measure restricted/conditioned to this finite union.) The process stops when no such $u$ exists, in which case it is said to have had duration $\ell$. This $\ell$ is a random variable. Call $\varphi(t)$ its expected value.

(There are many ways to describe the same process. Maybe we should consider it as building a random binary tree $\mathscr{T}_t$ with children $\mathscr{T}_u$ and $\mathscr{T}_{t-1-u}$ for $u$ uniformy distributed in $[0,t-1]$, in which case $\ell$ is the number of edges in the tree.)

It is not difficult to find a functional equation for $\varphi$: $$ \varphi(t)=0\quad\text{if $t<1$} $$ $$ \varphi(t)=1 + \frac{2}{t-1}\int_0^{t-1}\varphi(u)\,du\quad\text{if $t\geq1$} $$ (the second equation follows by observing that the first step in the process divides the interval $[0,t]$ into two intervals $[0,u]$ and $[u+1,t]$ of length $u$ and $t-1-u$, so $\varphi(t)=1 + \frac{1}{t-1}\left(\int_0^{t-1}(\varphi(u)+\varphi(t-1-u))\,du\right)$). From this we deduce an induction formula giving the exact value of $\varphi$ on intervals $[k,k+1]$: $$ \varphi(t) = \varphi_k(t)\quad\text{if $k\leq t\leq k+1$} $$ $$ \text{where}\quad \varphi_k(t) = \frac{t-k}{t-1} + \frac{k-1}{t-1}\,\varphi_{k-1}(k) + \frac{2}{t-1}\int_{k-1}^{t-1}\varphi_{k-1}(u)\,du\quad\text{for $k\geq2$} $$ but the computation quickly turns messy: $$ \begin{aligned} \varphi_1(t) &= 1\\ \varphi_2(t) &= \frac{3t-5}{t-1}\\ \varphi_3(t) &= \frac{7t-4\log(t-2)-17}{t-1}\\ \varphi_4(t) &= {\scriptstyle\frac{1}{3(t-1)}(45t - 60\log(t-2) -24\log(t-2)\log(t-3) - 24\operatorname{Li}_2(3-t)-147-2\pi^2+48\log2)}\\ \end{aligned} $$ (assuming I didn't make any mistakes copying this result, which is unlikely).

However, an exact value isn't very interesting. I am more interested in asymptotics:

Question: What is an asymptotic formula for $\varphi(t)$ as $t$ is large?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I mean, it is obvious that $\frac{t}{2}-1 \le \phi(t) \le t$, so do you want to know the constant $c$ such that $\phi(t) \sim ct$? (for the upper bound, we can't use more than $t$ intervals since that's the total measure, and for the lower bound if we used less than that many intervals then at least one of the remaining intervals must be longer than $1$, regardless of our luck). $\endgroup$
    – Aleksei Kulikov
    Commented Mar 26 at 19:15
  • 1
    $\begingroup$ My intuition tells me that $c$ should be equal to $\frac{2}{3}$, but I have no idea how to prove it (because intuitively complementary intervals should have lengths uniformly distributed from $0$ to $1$, so for $k$ intervals we should have total length about $\frac{3}{2}k$). $\endgroup$
    – Aleksei Kulikov
    Commented Mar 26 at 19:21
  • $\begingroup$ @AlekseiKulikov Yes, I'd like to know at least the linear term $ct$, and perhaps something more precise (ideally up to $o(1)$, but already $o(t)$ would be nice). $\endgroup$
    – Gro-Tsen
    Commented Mar 26 at 19:51
  • 3
    $\begingroup$ @AlekseiKulikov Was $c = \int_0^\infty \exp\left(-2\int_0^x \frac{1-e^{-y}}{y}dy\right)dx$ your second guess? ;) $\endgroup$
    – mathworker21
    Commented Mar 26 at 22:24

1 Answer 1

Reset to default
7
$\begingroup$

This is exactly the so-called "Renyi parking process." Renyi proved

$$\varphi(x) = cx + c - 1 + o(1)$$

where $$c = \int_0^\infty \exp\left( -2 \int_0^x \frac{1 - e^{-y}}{y}\,dy \right)\,dx \approx 0.7475979203\,.$$

The $o(1)$ term is in fact $O( (2e/x)^{x - 3/2})$. See this recent reference by Clay and Simanyi. Lines (1.3) and (1.4) show the form above, and line (1.1) is exactly the integral expression you derive.

Improve this answer
$\endgroup$
1
  • $\begingroup$ wow, what an error term $\endgroup$
    – mathworker21
    Commented Mar 28 at 2:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .