# Order statistics of iid uniform RV and Pólya's urn model. Question about a.s. convergence

Let $U_1,U_2,U_3,\dots$ be IID uniform on $[0,1]$. For each $n\geq 1$ let $$U_{1:n}<U_{2:n}<\dots<U_{n:n}$$ be the order statistic of $(U_1,\dots,U_n)$. Independent of the $U$ process there is a standard polya urn process $S=(S_n)_{n\geq 1}$ with distribution specified by $$(S_n)_{n\geq 1}~~\sim~~\big(1+\sum_{j=1}^{n-1} 1(V_j\leq V_0)\big)_{n\geq 1},$$ where $V_0,V_1,V_2,\dots$ are IID uniform on $[0,1]$. So it is clear that $\frac{1}{n}S_n$ converges alsmost surely towards some $V_0$ and $V_0$ is uniform on $[0,1]$.

Now let $B\subseteq [0,1]$ be any Borel set and $1_B(\cdot)$ the indicator function of $B$. Question: $$\text{Does 1_B(U_{S_n:n}) converge almost surely as n\rightarrow\infty towards 1_B(V_0)?}$$

It is clear that $U_{S_n:n}$ tends to $V_0$ almost surely. Since the random variables in the question are $\{0,1\}$-valued, a.s. convergence means that they stay finally constant a.s..

Remark: This question is about some kind of '0-1'- representations of Borel sets. For each Borel set $B\subseteq [0,1]$ and $n\geq 1$ I'm interested in the $\{0,1\}$-string $$\big[1_B(U_{1:n}),1_B(U_{2:n}),\dots,1_B(U_{n:n})\big]~\in\{0,1\}^n.$$ For large $n$ these strings should 'look like' the set $B$ (modulo uniform distribution). What can one say about long substrings $11\dots 11$ for large $n$?

• Seems like a job for the Lebesgue density theorem... – Nate Eldredge Jun 28 '16 at 13:42

Suppose that $U_n,V$ are some random variables such that $V$ is uniformly distributed on $[0,1]$, $U_n$ converges to $V$ a.s. and for every $n$, $P(U_n\ne V)=1$ (To be honest, I got a bit confused trying to read your definitions, but it certainly looks like no fixed variable can be exactly equal to the limiting one with positive probability). Then there exists a Borel set $B\subset [0,1]$ such that $1_B(U_n)$ fails to converge to $1_B(V)$ a.s. The construction is pretty straightforward. First, create sets $A_n$ of measure about $\mu_n$ such that $P(\text{there is }k>n\text{ such that }U_k\in A_n)>1/2$ (just split $[0,1]$ into short intervals of length $\ell$ and choose each one independently with probability $\mu_n$. Note that for fixed $\omega$, the events $U_k(\omega)\in A_n$ and $U_m(\omega)\in A_n$ are independent if $|U_k(\omega)-U_m(\omega)|>\ell$ and there are infinitely many different values $U_k(\omega)$ for a.e. $\omega$). Now just take $B=\cup A_n$ where $\mu_n$ are chosen so that $\sum_n\mu_n\le 1/4$. Of course, the first two assumptions can be dropped, but then you have to do some casework and the argument gets longer.

• Thank's a lot for your answers! I understand the other answer, but I have some troubles with this one...First of all: Yes, no fixed vairable is equal to the limiting one a.s. I have some trouble handling the 'random-set-construction' of the counter example...Why is $P(\text{there is$k>n$such that$U_k\in A_n$})>1/2$? – user240643 Sep 2 '16 at 15:31
• @user240643 If you have plenty of independent random events of a fixed probability (however small), then the probability that at least one happens is close to $1$. So, just choose $\ell$ so small that for the vast majority of $\omega\in\Omega$ you can find $1/\mu_n$ or so $\ell$-separated values among $U_k(\omega)$ with $k\ge n$. – fedja Sep 2 '16 at 16:49