6
$\begingroup$

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.

1 Answers 1

4

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.

  • 0
    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?2011-10-12
  • 0
    @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.2011-10-12
  • 0
    @chris, you have to *assume* independence since this is not explicitely stated in your exercise.2011-10-12
  • 0
    @Sasha, I wonder how one knows the behaviour of the sum without independence of its increments.2011-10-12
  • 0
    @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$.2011-10-12
  • 0
    @DidierPiau: maybe in the statement of the exercise *randomly* refers to independence?2011-10-12
  • 0
    @DidierPiau Thanks for the illuminating example. I stand corrected.2011-10-12
  • 0
    @Sasha: My pleasure. Trying to see what can go wrong with a (plausible) argument is often a learning experience.2011-10-12