Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.