Results 1 to 9 of 9

Math Help - Randomized Convergence

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    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!
    Last edited by chiph588@; December 27th 2010 at 06:57 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by chiph588@ View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by CaptainBlack View Post
    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] .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    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
    Last edited by CaptainBlack; December 28th 2010 at 12:20 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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

    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).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor matheagle's Avatar
    Joined
    Feb 2009
    Posts
    2,763
    Thanks
    5
    You can use the Khintchine-Kolmogorov Convergence Theorem instead.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    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! ...

    Kind regards

    \chi \sigma
    Last edited by chisigma; January 1st 2011 at 11:12 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by chisigma View Post
    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! ...

    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by Moo View Post
    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! ...

    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
    Last edited by chisigma; January 1st 2011 at 11:11 AM. Reason: error in (7) corrected...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question on randomized algorithm/hash function.
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: December 11th 2011, 07:46 AM
  2. Replies: 0
    Last Post: July 4th 2010, 12:05 PM
  3. Replies: 2
    Last Post: May 1st 2010, 09:22 PM
  4. Replies: 0
    Last Post: November 22nd 2009, 10:12 AM
  5. completey randomized ANOVA
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 17th 2006, 11:18 PM

Search Tags


/mathhelpforum @mathhelpforum