Randomized Convergence

Printable View

December 27th 2010, 06:36 PM
chiph588@

Randomized Convergence

I have essentially no knowledge of statistics, so this may be a well known topic.

Let $r:\mathbb{N} \to \{0,1\}$ be arbitrary.

What are the odds $\displaystyle \sum_{n=1}^\infty \frac{(-1)^{r(n)}}n$ converges?

-Thanks all!
December 27th 2010, 11:01 PM
CaptainBlack

Quote:

Originally Posted by chiph588@

I have essentially no knowledge of statistics, so this may be a well known topic.

Let $r:\mathbb{N} \to \{0,1\}$ be arbitrary.

What are the odds $\displaystyle \sum_{n=1}^\infty \frac{(-1)^{r(n)}}n$ converges?

-Thanks all!

Is that what you really want to ask? What you are asking appears to be:

does (or rather what is the probability that):

$\displaystyle \sum_{n=1}^{\infty}\dfrac{z_n}{n}$

converges where the $$$z_n$ 's are sampled uniformly on the top half of the unit circle in the complex plane.

If that is what you mean, then the answer is probably (I will need to work out how to prove it but this is what I would place my money on): the real part converges with probability 1 and the imaginary part converges with probability 0.

The heuristic argument behind this is the the real part behaves on average like the alternating harmonic series, while the imaginary part behaves on average like the harmonic series.

CB
December 27th 2010, 11:05 PM
chiph588@

Quote:

Originally Posted by CaptainBlack

Is that what you really want to ask? What you are asking appears to be:

does (or rather what is the probability that):

$\displaystyle \sum_{n=1}^{\infty}\dfrac{z_n}{n}$

converges where the $$$z_n$ 's are sampled uniformly on the top half of the unit circle in the complex plane.

If that is what you mean, then the answer is probably (I will need to work out how to prove it but this is what I would place my money on): the real part converges with probability 1 and the imaginary part converges with probability 0.

The heuristic argument behind this is the the real part behaves on average like the alternating harmonic series, while the imaginary part behaves on average like the harmonic series.

CB

$\{0,1\}$ is the set containing just $0$ and $1$ , not $[0,1]$ .
December 27th 2010, 11:27 PM
CaptainBlack

Quote:

Originally Posted by CaptainBlack

Is that what you really want to ask? What you are asking appears to be:

does (or rather what is the probability that):

$\displaystyle \sum_{n=1}^{\infty}\dfrac{z_n}{n}$

converges where the $$$z_n$ 's are sampled uniformly on the top half of the unit circle in the complex plane.

If that is what you mean, then the answer is probably (I will need to work out how to prove it but this is what I would place my money on): the real part converges with probability 1 and the imaginary part converges with probability 0.

The heuristic argument behind this is the the real part behaves on average like the alternating harmonic series, while the imaginary part behaves on average like the harmonic series.

CB

Ahhh.. rereading this what I should have taken this to mean is

does (or rather what is the probability that):

$\displaystyle \sum_{n=1}^{\infty}\dfrac{z_n}{n}$

converges where the $$$z_n$ 's are sampled uniformly on $\{-1, 1\}$ (that is take the values $\pm1$ each with probability $0.5$ ).

Then the same heuristic would suggest that this converges with probability 1. I can show that the partial sums approach a random variable with zero mean and variance 2 (but this only guarantees that the sum becomes unbounded with probability 0, not that the sum converge)

CB
December 28th 2010, 12:39 AM
Moo

Hello,

Considering CB's formulation : does the series $\displaystyle\sum_{n=1}^\infty \frac{z_n}{n}$ , where $\displaystyle P(z_n=1)=P(z_n=-1)=1/2$ , converge ? Yes it does and we can prove it using martingales. I'm sorry but for that, you will need some knowledge of probability :p

Consider the natural filtration $\displaystyle \mathcal F_n=\sigma(z_1,\dots,z_n)$ and define $\displaystyle M_n=\sum_{i=1}^n \frac{z_i}{i}$ .

It's easy to prove that $M_n$ is a $\mathcal F_n$ -martingale, because the $z_i$ are independent with mean 0.

With this independence and mean 0, we can also write that $\displaystyle E[M_n^2]=\sum_{i=1}^n E\left[\frac{z_i}{i}\right]^2=\sum_{i=1}^n \frac{1}{i^2}<\sum_{i=1}^\infty \frac{1}{i^2}<\infty$

Hence $M_n$ is bounded in $L^2$ and from a martingale theorem, we deduce that it converges almost surely and in $L^2$ to a random variable $M_\infty$ , which is in $L^2$ .

So we get that $\displaystyle \sum_{i=1}^\infty \frac{z_i}{i}=\lim_{n\to\infty}\sum_{i=1}^n\frac{z _i}{i}$ converges almost surely (that is to say with probability 1).
December 29th 2010, 12:26 AM
matheagle

You can use the Khintchine-Kolmogorov Convergence Theorem instead.
December 29th 2010, 06:55 AM
chisigma

Let's define a random variable $\chi$ as...

$\displaystyle \chi= \sum_{n=1}^{\infty} \chi_{n} = \sum_{n=1}^{\infty} \frac{z_{n}}{n}$ (1)

... where the $z_{n}$ are discrete random variables with $P \{z_{n}=-1\}= P \{z_{n}=+1 \}= \frac{1}{2}$ . Each $\chi_{n}$ has p.d.f. given by...

$\displaystyle \sigma_{n}(x)= \frac{\delta(x -\frac{1}{n}) + \delta(x+ \frac{1}{n})}{2}$ (2)

... and each $\sigma_{n} (*)$ has Fourier transform given by...

$\displaystyle \Sigma_{n} (\omega) = \cosh (i\ \frac{\omega}{n}) = \cos \frac{\omega}{n}$ (3)

Setting $\sigma(x)$ the p.d.f of $\chi$ and $\Sigma(\omega)$ its Fourier transform is...

$\displaystyle \Sigma(\omega)= \prod_{n=1}^{\infty} \Sigma_{n} (\omega) = \prod_{n=1}^{\infty} \cos \frac{\omega}{n}$ (4)

Now $\sigma(x)$ [if it exists...] can be obtained as inverse Fourier Transform of $\Sigma(\omega)$ ... but that requires some more efforts from me! (Thinking)...

Kind regards

$\chi$ $\sigma$
December 29th 2010, 07:58 AM
Moo

Quote:

Originally Posted by chisigma

Let's define a random variable $\chi$ as...

$\displaystyle \chi= \sum_{n=1}^{\infty} \chi_{n} = \sum_{n=1}^{\infty} \frac{z_{n}}{n}$ (1)

... where the $z_{n}$ are discrete random variables with $P \{z_{n}=-1\}= P \{z_{n}=-1 \}= \frac{1}{2}$ . Each $\chi_{n}$ has p.d.f. given by...

$\displaystyle \sigma_{n}(x)= \frac{\delta(x -\frac{1}{n}) + \delta(x+ \frac{1}{n})}{2}$ (2)

... and each $\sigma_{n} (*)$ has Fourier transform given by...

$\displaystyle \Sigma_{n} (\omega) = \cosh (i\ \frac{\omega}{n}) = \cos \frac{\omega}{n}$ (3)

Setting $\sigma(x)$ the p.d.f of $\chi$ and $\Sigma(\omega)$ its Fourier transform is...

$\displaystyle \Sigma(\omega)= \prod_{n=1}^{\infty} \Sigma_{n} (\omega) = \prod_{n=1}^{\infty} \cos \frac{\omega}{n}$ (4)

Now $\sigma(x)$ [if it exists...] can be obtained as inverse Fourier Transform of $\Sigma(\omega)$ ... but that requires some more efforts from me! (Thinking)...

Kind regards

$\chi$ $\sigma$

But what's the point of all this ?
Also, precise with respect to which measure you're taking the pdf oO
December 29th 2010, 11:21 AM
chisigma

Quote:

Originally Posted by Moo

But what's the point of all this ?
Also, precise with respect to which measure you're taking the pdf oO

The following example will [I do hope...] clarify...

... let's define the random variable $\chi$ as...

$\displaystyle \chi= \sum_{n=1}^{\infty} \chi_{n} = \sum_{n=1}^{\infty} \frac{z_{n}}{2^{n}}$ (1)

... where the $z_{n}$ are discrete random variables with $P \{z_{n}=-1\}= P \{z_{n}=+1 \}= \frac{1}{2}$ . Each $\chi_{n}$ has p.d.f. given by...

$\displaystyle \sigma_{n}(x)= \frac{\delta(x -\frac{1}{2^{n}}) + \delta(x+ \frac{1}{2^{n}})}{2}$ (2)

... and each $\sigma_{n} (*)$ has Fourier transform given by...

$\displaystyle \Sigma_{n} (\omega) = \cosh (i\ \frac{\omega}{2^{n}}) = \cos \frac{\omega}{2^{n}}$ (3)

Setting $\sigma(x)$ the p.d.f of $\chi$ and $\Sigma(\omega)$ its Fourier transform is...

$\displaystyle \Sigma(\omega)= \prod_{n=1}^{\infty} \Sigma_{n} (\omega) = \prod_{n=1}^{\infty} \cos \frac{\omega}{2^{n}}$ (4)

Now it is well known the 'infinite product'...

$\displaystyle \prod_{n=1}^{\infty} \cos \frac{\omega}{2^{n}} = \frac{\sin \omega}{\omega}$ (5)

... so that is...

$\displaystyle \sigma(x)= \mathcal{F}^{-1} \{\frac {\sin \omega}{\omega} \} = \left\{\begin{array}{ll}\frac{1}{2} ,\,\,|x|<1\\{}\\0 ,\,\, |x|>1\end{array}\right.$ (6)

... i.e. $\chi$ is uniformely distributed between -1 and +1... and that's not a surprise! (Wink)...

For the [very interesting...] question proposed by chip588@ we have to extablish if exists or not...

$\displaystyle \sigma(x)= \mathcal{F}^{-1} \{ \prod_{n=1}^{\infty} \cos \frac{\omega}{n} \}$ (7)

Kind regards

$\chi$ $\sigma$