No harmonic, no foul

Calculus Level 4

n = 1 f ( n ) n \large \displaystyle\sum_{n=1}^{\infty} \dfrac{f(n)}{n}

Let S S denote the expression of the variable sum above where f ( n ) f(n) has a 50% chance of being 1 and a 50% chance of being -1 for each individual n n , (with the f ( n ) f(n) 's being independent of one another).

What is the probability that the series S S converges?

e π \dfrac{e}{\pi} 0 1 2 \dfrac{1}{2} 1 ϕ \dfrac{1}{\phi} ln ( 2 ) \ln(2) 1 1 4 \dfrac{1}{4}

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Thsi is known as a random harmonic series , which as a consequence of Kolmogorov's three-series theorem converges with probability 1 . \boxed{1}.

Sir how should we start studying infinite series with random variables {I think its really cool to replace nth terms by random variables :D :p }... I went through the wiki article but could get nothing out of it {theres a lot of internet stuff but i can't understand them}....... can u guide me through the basic materials .

Abhinav Raichur - 6 years ago

Log in to reply

When I first wondered about this concept (some time ago), I stumbled across this paper , which I found to be an excellent introduction. I suppose I'm being lazy, but there is no way I could match the clarity of the information provided in this paper.

Brian Charlesworth - 6 years ago

Log in to reply

Thanks :) will go through it.

Abhinav Raichur - 6 years ago

Yay intuition.

Jake Lai - 6 years ago

This problem makes me wonder... For what value of the probability (0.5 in this case) does the series diverge?

Geoff Pilling - 2 years, 4 months ago

Log in to reply

Yeah, that's a great question! My reading of the Kolmogorov theorem is that if there is any deviation from the 0.5 probability then the series would almost surely diverge, (albeit incredibly slowly for values close to 0.5). That would be a surprising result, so it might be worth testing it out with a program.... someday. :)

Brian Charlesworth - 2 years, 4 months ago

Interesting... What about if you say there is a 2/3 chance it is +1 and a 1/3 chance it is -2?

Geoff Pilling - 2 years, 4 months ago

Log in to reply

That would appear to have a shot at converging almost surely, but I'm not certain it would satisfy condition (iii) of the Kolmogorov theorem. Need to refresh on variances ...

Brian Charlesworth - 2 years, 4 months ago

Log in to reply

The third condition just becomes (for A = 3 A=3 ) n = 1 2 n 2 , \displaystyle \sum_{n=1}^\infty \frac{2}{n^2}, which converges, so that example converges almost surely.

I should also point out that the three-series theorem is unnecessary here, since the first condition becomes trivial (the random variables in the sum converge uniformly to 0 0 ). It perhaps would be better to quote Kolmogorov's two-series thereom instead.

Brian Moehring - 2 years, 4 months ago

This is a really interesting problem, in particular, the probability distribution function f f of the final sum. So happens that f ( 0 ) 1 4 f(0) ~ \frac{1}{4} and f ( 2 ) 1 8 f(2) ~ \frac{1}{8} . The (approach)[http://www.stat.ualberta.ca/people/schmu/preprints/rhs.pdf] found for deriving f f is also really ingenius, since S S is a continuous random variable that is made by the sum of discrete random variables, which should have made it hell to find f f .

It might be interesting to you that f f is smooth too.

Julian Poon - 2 years, 3 months ago

If the distribution of sign is biased, then again by Kolmogorov's three-series theorem, the series diverges with probability 1. So this puts the case of random harmonic series special.

Sangchul Lee - 2 years, 2 months ago
Brock Brown
May 25, 2015

If you want to watch how it converges (generally to some number between -3 and 3 but can be more or less with low probability), this is a fun little program:

Python 2.7:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import random
from fractions import Fraction as frac
from time import time
def f(n):
    return random.choice((1, -1))
print "How many seconds do you want to run simulations?"
seconds = int(raw_input("> "))
while True:
    total = 0
    n = 1
    end = time() + seconds
    while time() < end:
        total += frac(f(n),n)
        n += 1
        print float(total)
    print "Run again?"
    if raw_input("y/n: ") in ('y', ''):
        continue
    else:
        break

Great! Thanks for posting this. Your result is consistent with one of the papers I linked to, in that the vast majority of the time the sum converges to a value between -3 and 3, with an average absolute value of between 1 and 1.25.

Brian Charlesworth - 6 years ago

Log in to reply

Just curious, do you know of any random sums like this that only converge some of the time, instead of P { 1 , 0 } P \in \{1, 0\} ? Or does the Law of Large Numbers say that this can't happen?

Brock Brown - 6 years ago

Log in to reply

No, it can't happen. Since the convergence of a random series is a tail event (i.e. independent of every finite subset of r.v.s) Kolmogorov's zero-one law says that probability of convergence is either zero or one.

Abhishek Sinha - 6 years ago

Log in to reply

@Abhishek Sinha Thanks for the concise answer. :)

Brock Brown - 6 years ago

@Abhishek Sinha This is fascinating! Thank you so much for the link!

Jake Lai - 6 years ago

wow .... thanks :)

Abhinav Raichur - 6 years ago

Does random.choice() returns random or pseudo-random number?

Pranjal Jain - 6 years ago

Log in to reply

Pseudo-random, but the distribution is correct enough to be useful. Most of the time, you don't want to use true random anyway because it will take too much work.

Even the random numbers from random.org aren't really truly "random"; their random numbers come from atmospheric noise.

Brock Brown - 6 years ago

Log in to reply

How to generate numbers (either 0 or 1) with custom probability in python? For example, I want 30% 0's and 70% 1's (for my minesweeper game, 0 denotes mines)

Pranjal Jain - 6 years ago

Log in to reply

@Pranjal Jain You can use random.random to generate a random number between 0 and 1. Here's an example:

Python 2.7:

1
2
3
4
5
from random import random
if random() < 0.3:
    print "This is printed 30% of the time."
else:
    print "This is printed 70% of the time."

Python's Random Documentation

Brock Brown - 5 years, 12 months ago

Log in to reply

@Brock Brown Thanks! ¨ \ddot\smile

Pranjal Jain - 5 years, 12 months ago

Log in to reply

@Pranjal Jain No problem!

If you've ever got any more Python questions let me know:

[email protected]

Brock Brown - 5 years, 12 months ago
Aditya Ghosh
Apr 19, 2019

Let's write X n = f ( n ) / n X_n=f(n)/n . Then { X n } \{X_n\} is a sequence of independent random variables, each with mean 0 0 . Now, there is a result (which is essentially a version of Kolmogorov's three-series theorem) that states that n 1 X n \sum_{n\geq 1} X_n converges with probability 1 1 if n 1 Var ( X n ) < \sum_{n\geq 1} \text{Var}(X_n)<\infty . Here, we indeed have n 1 Var ( X n ) < \sum_{n\geq 1} \text{Var}(X_n)<\infty . Hence the given series converges with probability 1 1 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...