Almost sure convergence of an algorithm

68 Views Asked by At

You designed an algorithm and you proved that this algorithm converges almost surely. Let's note $X_n$ the value of your algorithm at step $n$, which is a random variable, and $X$ the true converged value. Thus, one has: $\mathbb{P}[\ \lim_{n\to+\infty}X_n = X]\ = 1$

What does it mean concretely? For instance, does it meean that if you run it many times, it may fail to converge as $n$ goes to $+\infty$? What is the difference with pointwise convergence in this context?

1

There are 1 best solutions below

0
On

I will give you a practical example with Strong Law of Large Numbers. You can use the random number generator to create a sequence of independent and identically distributed random variables and then compute its mean. If this sequence is long enough, this mean will be close to the true mean of a random variable you used to generate a sequence. Now, imagine you generate many such sequences, over and over again. Almost sure convergence implies that means computed for all these sequences will be close to the true mean. You can, of course, imagine a valid sequence whose mean is quite far from the true mean, but almost sure converges guarantees that probability of such a sequence is 0, i.e., for a large enough sequence size the random number generator will never produce a sequence like that.