# Almost sure convergence on an inductively defined random variable

Define a sequence of random variables inductively with $X_0=1$ and $X_{n+1}$ selected randomly and uniformly from $[0,X_n]$. Show $\dfrac{1}{n}\log X_n$ converges almost surely to a constant and evaluate the limit.

A sequence of random variables $X_n$ goes to $c$ almost surely if $P(\lim_{n\to\infty} X_n=c)=1$. From the definition of $X_n$ it is clear that $X_{n-1}\geq X_n \;\forall\; n\geq0$ and since $X_n$ is uniform, $P(X_k)=\frac{1}{X_{k-1}}$. But I'm not really sure where to go from here since the limit is on the inside of the probability. Am I supposed to apply to weak or long law of strong numbers somewhere? Any help would be greatly appreciated.

-

Assuming that the results $(U_n)_{n\geqslant1}$ of the successive random uniform selections are i.i.d., one gets $X_n=U_1\cdots U_n$ for every $n\geqslant1$, where $(U_k)_{k\geqslant1}$ is i.i.d. with uniform distribution on $(0,1)$.

Thus, $\log X_n=\sum\limits_{k=1}^n\log U_k$ is a sum of i.i.d. increments. If $\log U_1$ is integrable, the law of large numbers says that $\log X_n=n\mathrm E(\log U_1)+o(n)$ almost surely, in other words $\frac1n\log X_n\to\mathrm E(\log U_1)$ almost surely.

Now you must simply evaluate $\mathrm E(\log U_1)$...

Edit Here is an example showing that non independent choices can make things go awry. Assume that for each nonnegative integer $k$, $U_n$ has the same value $V_k$ for every positive $n$ such that $2^{k-1}< n\leqslant2^{k}$. Assume furthermore that $(V_k)_{k\geqslant1}$ is i.i.d. uniform on $(0,1)$. Hence each $U_n$ is uniform on $(0,1)$ but $U_n$ and $U_m$ are not independent unless $n$ and $m$ are separated by a power of $2$.

Then $\log X_{2^k}=\sum\limits_{i=1}^k2^{i-1}\log V_i$ hence $\frac1{2^k}\log X_{2^k}=\sum\limits_{i=0}^{k-1}2^{-i-1}\log V_{k-i}$. For large values of $k$, this sum behaves like $$W_k=\sum\limits_{i\geqslant0}2^{-i-1}\log V_{k-i},$$ which is a Markov chain with dynamics $W_{k}=\frac12(W_{k-1}+\log V_k)$. It is a relatively standard exercise to show that $(W_k)_k$ is recurrent in the sense that it visits every open interval in $(-\infty,0)$ infinitely often, almost surely. In particular, $(W_k)$ diverges almost surely hence the sequence of general term $\frac1n\log X_n$ diverges almost surely.

-
But are they IID? Since $X_0$=1 and $X_{n+1}$ is chosen from $[0,X_n]$ how to we know that they are independent? – chris Oct 12 '11 at 5:25
@chris You do not need to know that $U_k$ are i.i.d., only that distributions of each individual $U_k$ is a standard uniform. – Sasha Oct 12 '11 at 5:36
@chris, you have to assume independence since this is not explicitely stated in your exercise. – Did Oct 12 '11 at 5:50
@Sasha, I wonder how one knows the behaviour of the sum without independence of its increments. – Did Oct 12 '11 at 5:52
@Sasha Then I'm not quite sure how to get $X_n=U_1\cdots U_n$. And when finding $E[log U_1]$ don't we have that $P(X_1=U_i)=0$ for any fixed $U_i$? Which would mean that it converges almost surely to $0$. – chris Oct 12 '11 at 5:55