Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $S_1=\lbrace u_1 \rbrace$ where $u_1$ is a random uniform drawing on $[0,1]$. To build $S_{n+1}$ draw $u_{n+1}$ uniformly on $[0,1]$ (independently from previous draws) and draw $v_{n+1}$ uniformly on $[0,1]$ (independently from previous draws) then

A) if $v_{n+1}$ is smaller than the largest element in $S_n \cup \lbrace u_{n+1}\rbrace $ then let $w_{+1}=\min \lbrace S_n \cup \lbrace u_{n+1\}\rbrace \cap ]v_{n+1},1] \rbrace$ (that is to say $w_{n+1}$ is the element of $S_n \cup \lbrace u_{n+1}\rbrace $ immediately to the right of $v_{n+1}$) and then set $S_{n+1}=S_n \cup \lbrace u_{n+1\}\rbrace \backslash \lbrace w_{n+1} \rbrace.$

B) If $v_{n+1}$ is larger than the largest element in $S_n \cup \lbrace u_{n+1}\rbrace $ then set $S_{n+1}=S_n \cup \lbrace u_{n+1}\rbrace $

The question is does the cardinal of $S_n$ admits a limiting distribution (after some proper normalisation) ? I already know that the cardinal divided by square root of $n$ diverges (as simulations show it is a very very slow divergence) and that the cardinal divided by $n$ goes to zero a.s.

The problem is linked to several interesting applications among which exact non parametric testing, random condensation/dispersion processes,... It is closely related to the length of the longest increasing sub-sequence in a independent identically distributed sample. The cardinal of $S_n$ would be exactly this if we had $v_{n+1}=u_{n+1}.$ The limiting distribution of the longest increasing sub-sequence of an iid sample is known. The normalizing sequence is root $n$ but the distribution is not gaussian.

Some easy comments may help. Obviously $S_{n}$ is an order 1 markovian process. However the conditional distribution of the cardinal of $S_n$ given the cardinals of $S_{n-1}$, $S_{n-2}$,... is not that of $S_n$ given the cardinal of $S_{n-1}$ only. The cardinal of the set increases in case B only otherwise it remains the same because we add $u_{n+1}$ but we remove $w_{+1}.$

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.