This is a homework question:

Suppose that $X_0=1$ and that for $n\geq 1$ $$X_n\sim \left\{ \begin{array}{l l} U(0,X_{n-1}) & \quad \text{with probability $1-X_{n-1}/2$}\\ U(X_{n-1},1) & \quad \text{with probability $X_{n-1}/2$} \end{array} \right.$$ Determine the limiting behavior of $X_n$.

My attempt:

1) Check if this is a (sub/super)martingale

2) By the martingale convergence theorems, since it is bounded (below by 0, above by 1) this random variable must converge to something.

3) It can't possible converge to some value $x\in (0,1)$ since if $X_n=x$, then theres a high probability that $X_{n+1}$ is more than $\epsilon$ units away from $x$ for any $\epsilon>0$. So it should converge to either 0 or 1 (or both).

4) My guess is $X_n \overset{a.s.}{\longrightarrow} X\sim \text{bernoulli}(p=1/2)$.

A quick simulation however suggests that it converges almost surely to just 0!

quiz5_number2 <- function(reps=1000, path=NULL){
  for(i in 1:reps){
    y<-rbinom(1, size=1, prob= 1-x0/2) 
    x1<- runif(1, min=0,max=x0)*y + runif(1, min=x0,max=1)*(1-y)

enter image description here

How would you answer this problem?

I realize the problem seems poorly worded. Blame my teacher :)

EDIT: On further analysis it is quite simple to see that while 0 is an 'absorbing' state (if you get to zero you will stay there), 1 is not an absorbing state (if you are at 1 you have 0.5 chance to be drawn from uniform(0,1) and 0.5 chance to stay). So I guess it makes a lot of sense that it converges to 0. Thank you for reading.

  • $\begingroup$ Where is $q$ in your code? Is that a typo? $\endgroup$ – Stat Dec 18 '13 at 0:55
  • $\begingroup$ What are you referring to? q? what is q? EDIT: AHH! yes that is a typo! $\endgroup$ – bdeonovic Dec 18 '13 at 1:03
  • $\begingroup$ Apart from a full formal proof, I think I have figured it out that it does indeed converge almost surely to 0. $\endgroup$ – bdeonovic Dec 18 '13 at 1:24
  • $\begingroup$ If $X_N=0$ for some $N\geq 1$, then by definition, $X_{N+1}=U(0,0)=0$ with probability 1 and $X_{N+1}=U(0,1)$ with probability 0. So zero is like an absorbing point. When the process hits that, it is gonna stay there forever! $\endgroup$ – Stat Dec 18 '13 at 1:40
  • $\begingroup$ Yes I came to that same conclusion awhile ago :) Thanks for the input! $\endgroup$ – bdeonovic Dec 18 '13 at 1:50

You are correct in suggesting to use the martingale convergence theorem.

Let us compute $\mathbf{E}[X_n|X_{n-1}]$. A trite calculation shows that this equals $$(1-X_{n-1}/2)\mathbf{E}[U(0,X_{n-1})|X_{n-1}]+(X_{n-1}/2)\mathbf{E}[U(X_{n-1},1)|X_{n-1}].$$ Computing the uniform expectations and then reducing, we find $$\frac{X_{n-1}}{2}\cdot(3/2-X_{n-1}).$$ Since $X_{n-1}$ clearly lies between $0$ and $1$ for all $n$, the last quantity is positive, and in fact it is bounded by $(3/4)\cdot X_{n-1}$. Thus the sequence is a positive supermartingale. It converges almost surely, and it is clear that the limiting random variable must be positive almost surely and have zero expectation (just take the expectation in the above calculation to show that the expectation must decrease to zero exponentially): $$\mathbf{E}X_n \le \left(\frac{3}{4}\right)^n.$$ So the limit is zero.

| cite | improve this answer | |
  • $\begingroup$ @ phils: This is self-study question (see the tags), you are not supposed to solve them, give some hints next time. $\endgroup$ – Stat Dec 18 '13 at 2:34
  • $\begingroup$ Ok. I will remember. $\endgroup$ – phils Dec 18 '13 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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