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
add comment

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.