Let `f` be a function that chooses a random integer from 1 to 100 (inclusive) with a uniform probability distribution. Then the probability that what `f` returns is an even integer is 1/2. We will use `f * f` to denote calling `f` twice and multiplying the results, so it is simply the product two randomly chosen integers. In general, let `f^n` represent calling `f` `n` times and multiplying the `n` random integers returned.
Let `P(a = E)` be the probability that `a` is an even integer and `P(a = O)` the probability that `a` is odd. Show that
`P(f^n = E) = 1 - (1/2)^n`
`P(\sum_{k=1}^n f^k = E) = 1/2`
So the probability that the product of a large number of these random integers is even is close to 1, but the probability that the sum of the products of these random integers is even is always 1/2.
What happens if `f` chooses a random integer from 1 to 3? Or more generally, assume that `f` is choosing from some finite set of positive integers with `a` even integers and `b` odd integers. Now what is the probability that the sum of the products, `\sum_{k=1}^n f^k`, is even?
Let `s_n = P(\sum_{k=1}^n f^k = E)`. Set `p = b/(a+b)`, so `s_1 = 1 - p`. Following the proof of (2), we can write a recursive expression for `s_{n+1}`:
`s_{n+1} = P(f^{n+1} = E) s_n + P(f^{n+1} = O) (1 - s_n) = (1 - p^{n+1})s_n + p^{n+1} (1 - s_n) = p^{n+1} + (1 - 2p^{n+1})s_n`.
Since `|s_{n+1} - s_n| < p^{n+1}`, the sequence `\{s_n\}` forms a Cauchy sequence, and so converges to some value `A`.
But what is `A`? Numerical experiments indicate that it is not 1/2 (or if it is, then the rate of convergence is very slow) and a closed form expression for `s_n` generated by Maple is not especially helpful. So at this point I'm stumped.