3
$\begingroup$

A counterintuitive result in probability theory that may warrant the description of a veridical paradox is the fact that repeating an experiment with a nonzero chance of success infinitely often does not always guarantee eventual success. This is the case if the probability of success shrinks with each iteration quickly enough to compensate for the repetitions.

Is there a name for this paradox and has it been explicitly discussed anywhere? The paradox arises in branching processes used to model extinction probabilities, including Galton and Watson's 1874 work on the extinction of family names. It also occurs in 3D random walks, where the probability of return to the origin is less than 1, proved by Pólya in 1921.

Do these or any other sources discuss the apparent paradox?

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you state more precisely what the paradox is, because in some cases at least infinite repetition does guarantee success in the sense that its probability converges to 1, as in the case of getting heads on coin tosses, or monkeys typewriting Shakespeare mathisdermaler.wordpress.com/2010/11/23/… $\endgroup$
    – Conifold
    Mar 22, 2016 at 22:09
  • $\begingroup$ The paradox is the fact that this is not always the case. The two examples I can think of are 3D random walks, where there is a chance of never getting back to the origin, and branching processes, where there is a chance that a population will never go extinct. I'll add links once I'm at a computer. $\endgroup$
    – Uri Granta
    Mar 23, 2016 at 4:50
  • $\begingroup$ According to Quine, "veridical paradox produces a result that appears absurd but is demonstrated to be true nevertheless". I fail to see why if the probability of success shrinks with each iteration the lack of eventual success "appears absurd". But a bigger problem with the question is that "repeating an experiment with a nonzero chance of success infinitely often" is not even what happens in the mentioned examples, there is no "repeated experiment" there. There is vast literature on 3D walks and Galton-Watson process, but no "paradox" since they are not independent trials. $\endgroup$
    – Conifold
    Mar 24, 2016 at 3:52
  • $\begingroup$ As mentioned below, I find this result paradoxical in the same way as Simpson's Paradox or Braess's paradox: there is a superficially convincing argument against it (namely that something with a nonzero probability repeated infinitely often is bound to happen eventually). But clearly YMMV and the lack of literature may indicate that I'm alone here. $\endgroup$
    – Uri Granta
    Mar 24, 2016 at 7:59

1 Answer 1

Reset to default
1
$\begingroup$

If we have a trial with non-zero probability of success $p>0$, and we repeat the trial $n$ times, the probability of at least one success is $p(n)=1-(1-p)^n$, which converges to $1$ when $n\to\infty$. An example would be tossing a fair coin (with $p=1/2$), and expecting to get heads eventually. Even if the coin is loaded for tails as long as $p>0$ we can still expect getting heads eventually. Of course, if the probability $p$ changes from trial to trial then it is possible that $p(n)$ does not converge to $1$, but that would not be repeating "the same" trial, nor would it be paradoxical.

Probability of eventual return in 3D random walks is discussed on Math Overflow for example, or in this book chapter, neither of which describes its values as paradoxical. The paradoxes mentioned are unrelated: the birthday paradox and the Levinthal paradox of protein folding. Similarly, the only paper I found that mentions a "paradox" in connection with the Galton-Watson process refers to something else.

These are not however cases of "repeating the same trial" for eventual success. In 3D walks for example the outcomes of random "trials" are individual steps $X_i$ chosen at random, but "success" is defined in terms of the final position $S_n=X_1+\cdots+X_n$, not individual $X_i$, which is clearly different from success in coin tosses. Moreover, each step is performed in different locations at different distances from the origin, so they are not "the same" trials by any stretch. The probability of eventual return is $1$ in 1D and 2D, but only about $0.65$ in 3D, which in principle is not very surprising since there is a lot more room to wander around in 3D (frankly, it might be more surprising that it is still $1$ in 2D). MO thread gives a more detailed intuitive explanation for the difference based on convergence/divergence of $1/n^{d/2}$ series.

A more general phenomenon at play here is the difference between recurrent and transient states in Markov chains. A state is called recurrent (persistent) if the probability of eventual return to it is $1$, and transient otherwise. Independent trials form a so-called Bernoulli scheme, which is a very special case of a Markov chain, where the next state does not depend even on the previous one (which is what makes them "the same" trial). By the first paragraph above in a Bernoulli scheme all states are recurrent, but general Markov chains are free to have transient ones.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The question is explicitly about non constant probabilities. I fully understand why this happens, but the result is paradoxical in the Quine veridical sense: it is counterintuitive and catches people out. I've heard CS researchers assume this can't happen. I was therefore wondering if this counter intuition was discussed in any of the literature on extinctions or random walks. Sorry if that was unclear from the question. $\endgroup$
    – Uri Granta
    Mar 24, 2016 at 1:28
  • 1
    $\begingroup$ @Uri Perhaps you could elaborate on what exactly you consider paradoxical in the question, "catches people out" and "I've heard CS researchers assume this" sounds anecdotal. I looked through some references on 3D walks and Galton-Watson, but none of them considers a less than 1 recurrence probability in a Markov chain "counterintuitive" as such . $\endgroup$
    – Conifold
    Mar 24, 2016 at 4:05
  • $\begingroup$ If you update your answer to say that references on 3D walk and Galton Walton don't describe the result as counterintuitive I'd be happy to upvote it! I find this result paradoxical in the same way as Simpson's Paradox or Braess's paradox: there is a superficially convincing argument against it (namely that something with a nonzero probability repeated infinitely often is bound to happen eventually). But clearly YMMV. $\endgroup$
    – Uri Granta
    Mar 24, 2016 at 5:22
  • 1
    $\begingroup$ @Uri Here is my hypothetical: if the probability of success is fixed, say 1/3, success is expected roughly 1/3 of the time, so for certain eventually. People often intuit in extremes, and the other extreme is that probability falls to 0 after finitely many trials. So unless we get lucky fast we never get lucky, and fast luck is clearly not certain. I expect most people to hesitate in the intermediate cases rather than to have strong intuition either way. $\endgroup$
    – Conifold
    Mar 27, 2016 at 0:37
  • 1
    $\begingroup$ But I can see something like what you describe happening if people register that (transition) probabilities are fixed at each step, but overlook that they are not probabilities of "success" and fall back on the intuition of independent trials with fixed probability. It would then be a psychological paradox of sorts to them I guess. $\endgroup$
    – Conifold
    Mar 27, 2016 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.