6
$\begingroup$

Starting from the length-1 list whose only entry is 1, iterate the process of replacing the last (and largest) entry in the list of length $n$ (call that entry $m$) by the two numbers $mU_n$ and $m(1-U_n)$, where $U_1,U_2,\dots$ are independent identical draws from the uniform distribution on $[0,1]$, and sorting the new list from smallest to largest. Show that after $n-1$ steps the length-$n$ list that we see is likely to be close to $(1/N,2/N,\dots,n/N)$ with $N=n(n+1)/2$.

This must be a classic fragmentation process, but five minutes of Googling failed to turn up anything relevant.

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you make more precise the part about likely to be close to? Some experiments show that the list minus $(1/N,...n/N)$ might oscillate with increasing amplitude. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Feb 3, 2022 at 21:53
  • $\begingroup$ In my experiments, the maximum difference between $(a_1,...,a_n)$ and $(1/N,...,n/N)$ is small compared to $1/n$; I predict that the probability of there existing $i$ between 1 and $n$ such that $|a_i - i/N| > 1/n$ goes to zero as $n$ goes to infinity. I wonder if your code contains an error, or if mine does. $\endgroup$
    – James Propp
    Commented Feb 3, 2022 at 22:37
  • 3
    $\begingroup$ I believe some version of your question is addressed in Pyke's "The asymptotic behavior of spacings under Kakutani's model for interval subdivision" (Annals of Probability, 1980) $\endgroup$
    – Kevin P. Costello
    Commented Feb 4, 2022 at 0:00
  • $\begingroup$ @JamesPropp I confirm the statement in your comment. Seems like these oscillations are small compared to $n$. In fact, again experimenting, seems like $n\max_i|a_i-i/N|$ tends to 0 as $n$ increases. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Feb 4, 2022 at 6:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .