# How to verify almost sure convergence?

Let $X_n \sim \text{Exp}(c^n)$, with $c > 0$. Let $Y_n = \min\{X_1, \ldots, X_n\}$. Find the distribution of $Y_n$ and study its convergence in distribution. Finally, show that $(Y_n)_{n \in \mathbb N}$ converges almost surely to some random variable for every $c$.

With the use of the CDF and some algebra, we obtain $$Y_n \sim \text{Exp}\left(-\sum_{i = 1}^n c^i\right) = \text{Exp}\left(-\frac{c - c^{n + 1}}{1 - c}\right)$$ where last equality holds for $c \neq 1$.

For $0 < c < 1$, $$\lim_n F_{Y_n}(y) = 1 - \exp\left(-\frac{c}{1 - c}y\right)$$ and $c / (1 - c)$ is always positive, so $Y_n \xrightarrow{d} \text{Exp}(\frac{c}{1 - c})$. For $c \geq 1$, $Y_n \xrightarrow{d} 0$.

It's when I have to show almost sure convergence that I get stuck. For example, let $c \geq 1$. Then $$P(Y_n \to 0) = P(\{\omega \in \Omega \mid \lim_n Y_n(\omega) = 0\})$$ How do I show that this evaluates to $1$? Intuitively I would guess that positive values are progressively less and less likely, and so at infinity $0$ is the only possible outcome. But since $Y_n$ is a continuous variable, I cannot use the probability of getting $0$ since it's $0$.

I realize, though, that intuitively I'm thinking about the probability $P(Y_n > \varepsilon) \to 0$ for $\varepsilon > 0$, which is the convergence in probability. But the latter does not imply almost sure convergence...

• The argument to show that $(Y_n)$ converges almost surely is much simpler: for each $n$, $Y_{n+1}=\min\{Y_n,X_{n+1}\}$ almost surely hence $0<Y_{n+1}\leqslant Y_n$ almost surely, which implies that $Y_n\to Y$ almost surely, for some finite random variable $Y\geqslant0$. – Did Feb 12 '17 at 12:33
• @Did haha ahh yeah monotone convergence, forgot about that. – spaceisdarkgreen Feb 12 '17 at 12:55
• @Did Thanks for an alternative, quicker way to prove it. I really didn't think of formulating the sequence that way. – rubik Feb 12 '17 at 21:32

For $c>1$ you are basically right. Let $\epsilon>0.$ Then we have $P(Y_n>\epsilon) = e^{-\lambda_n\epsilon}$ where $\lambda_n = (c^{n+1}-c)/(c-1).$ Since $c>1,$ $\sum_{n=1}^\infty P(Y_n>\epsilon) <\infty,$ and thus by Borel-Cantelli, the probability $Y_n>\epsilon$ infinitely often is zero so $\limsup_n Y_n\le\epsilon$ almost surely. Similarly for $c=1,$ $P(Y_n>\epsilon) = e^{-\lambda n}$ and the same thing follows.

For $c<1$ it's a little trickier cause it's not immediately apparent how to reason about the random variable that $Y_n$ converges to. A good trick in these kinds of situations is to instead try and prove that the sequence is almost surely Cauchy, so you only need to refer to the $Y_n$. In fact we will be able to show the stronger fact that $Y_n$ is almost surely eventually constant.

Let's think about what's going on here. We have the rate $c^n\to 0$ which means the mean of the random exponential is increasing to infinity. Thus as $n\to \infty$ it becomes much less likely that $X_n$ is a new minimum. Thus much more likely that the minimum doesn't change, i.e. that $Y_n=Y_{n-1}.$

The probability that the minimum $Y$ changes after time $m$ can be bounded by the union bound $$P(|Y_{m}-Y_{m+n}| > 0 \;\forall n) \leq \sum_{n=1}^\infty P(X_{m+n} < Y_m)$$ since the minumum only changes if one of the $X$'s is less than the prevailing minimum. The $X$'s are independent (I hope, anyway, you didn't say they were but you used the assumption) so the $X_{m+n}$'s and $Y_m$ are all independent exponentials.

For two independent exponentials $X,Y$ with rates $\lambda_x,\lambda_y,$ the probability one is greater than the other is $$P(Y>X) = \frac{\lambda_x}{\lambda_x+\lambda_y}$$

So since $Y_m$ has rate $\lambda_y = \frac{c-c^{m+1}}{1-c}$ and $X_{m+n}$ has $\lambda_x = c^{m+n}$ so $$P(X_{m+n} <Y_m) = \frac{c^{m+n}}{c^{m+n} + \frac{c-c^{m+1}}{1-c}}$$ and then $$\sum_{n=1}^\infty P(X_{m+n} < Y_m) < \frac{1}{\frac{c-c^{m+1}}{1-c}} \sum_{n=1}^\infty c^{m+n}= \frac{c^m}{1-c^m}.$$

Now we can sum up $$\sum_m P(|Y_{n+m}-Y_m| > 0 \; \forall n) < \sum_m \frac{c^m}{1-c^m}< \infty$$ so by Borel Cantelli it is almost surely the case that the maximum changes after time $m$ for only finitely many $m$, in other words, $Y_n$ is almost surely eventually constant (and thus almost surely convergent).

EDIT

Or... you could not do what I did and--as Did said in the comments-- just use the fact that $Y_n$ is monotonically decreasing and bounded from below so it converges.

I'll still leave this up, cause it shows that it's eventually constant and shows some strategies for handling these kinds of problems, in lieu of a one-sentence solution.

• Very thorough answer, I appreciate it. Indeed, it showcases some general techniques that could be useful elsewhere. – rubik Feb 12 '17 at 21:32