# Limiting behavior of a martingale

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){
x0<-1
path<-c(path,x0)
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)
x0<-x1
path<-c(path,x0)
}
path
}
path<-quiz5_number2(100)
plot(path)


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.

• Where is $q$ in your code? Is that a typo? – Stat Dec 18 '13 at 0:55
• What are you referring to? q? what is q? EDIT: AHH! yes that is a typo! – bdeonovic Dec 18 '13 at 1:03
• Apart from a full formal proof, I think I have figured it out that it does indeed converge almost surely to 0. – bdeonovic Dec 18 '13 at 1:24
• 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! – Stat Dec 18 '13 at 1:40
• Yes I came to that same conclusion awhile ago :) Thanks for the input! – bdeonovic Dec 18 '13 at 1:50

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.