Suppose that a sequence of coin tosses is due to be performed. Let $p_i$ denote the probability that the $i$th coin toss lands on Heads and let $X_i$ denote the corresponding indicator random variable for this event. The success probabilities in the sequence $\lbrace p_1,p_2,\ldots \rbrace$ are neither identical nor independently drawn. For $i\in\mathbb{N}$, we instead have that $p_i := f_i(p_1,\ldots,p_{i-1})$ for some well-defined but complicated function $f_i$ such that, furthermore, we have that the constraint $0<p_i<1$ holds for any input into $f_i$, i.e. $f_i:(0,1)^{i-1}\rightarrow (0,1)$.

Coin tosses are performed until the first tail is encountered. That is, if we obtain the sequence of coin tosses such that $X_k = 1$ for all $k < K$ and $X_K = 0$, the entire process immediately ceases and we do not even compute $p_{K+1}$.

Under these circumstances, can we say that the probability of observing the infinite sequence of events $\lbrace X_i = 1 : i \in \mathbb{N}\rbrace$ occurs with probability zero?

Context: The purpose of this work is actually to prove that an algorithm I am currently writing terminates, in the almost sure sense, after only a finite number of iterations. The event $\lbrace X_i = 1 \rbrace$ corresponds to the event that the algorithm does not terminate at stage $i$.

  • 2
    $\begingroup$ This depends on $(p_i)$, clearly. $\endgroup$ – Did Apr 26 '16 at 15:00
  • 1
    $\begingroup$ Not really -- for instance, the following setting of $(p_i)_i$ seems to give a non-zero probability: $p_i = 1-\frac{1}{i^2}$. (the $p_i$'s do not even depend on each other, i.e. each $f_i$ is a constant). Then the probability of observing an infinite sequence of Heads is $\prod_{i=1}^\infty (1-\frac{1}{(i+1)^2}) > 0$. $\endgroup$ – Clement C. Apr 26 '16 at 15:12
  • 1
    $\begingroup$ @ClementC. $p_1=0$? :-) $\endgroup$ – Did Apr 26 '16 at 15:12
  • 1
    $\begingroup$ Yes, that would be enough (not necessary, but sufficient). $\endgroup$ – Clement C. Apr 26 '16 at 16:30
  • 1
    $\begingroup$ This would hide the feature that makes decreasing sequences suitable, which is that such sequences are bounded away from $1$, hence $\prod p_i=0$. $\endgroup$ – Did Apr 26 '16 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.