0
$\begingroup$

I know that any specific event (or a specific subset of events) with a non-zero probability will occur almost surely (i.e, with probability 1) at some point given an infinite sequence of events.

My question is, under which conditions do we also know that the expected time to encounter this event (or subset of events) is finite? For example, in the infinite monkey theorem/borel-cantelli's second lemma, given a uniform distribution, the expected time is finite.

I am not sure that it holds in the general case for any distribution.

Is there some useful theorem or conditions that suffice to prove a finite expected time? I imagine it also may be viewed in the perspective of Markov chains (of which I am woefully ignorant)

Many thanks for your help

$\endgroup$
2
  • 1
    $\begingroup$ The situation needs to be clarified. You might be talking about mutually independent events $A_1, A_2, A_3, ...$ with $P[A_i]=p$ for all $i$, for some $p \in (0,1]$. The time $X \in \{1, 2, 3, ...\}$ that the first event occurs is a geometric random variable with success probability $p$. So $E[X]=1/p$. $\endgroup$
    – Michael
    Commented Jul 2 at 15:46
  • $\begingroup$ Hi Michael, thank you very much for your quick response! Your example is a special case. Let me clarify. I asked about arbitrary distributions. That is, given a possibly infinite set of disjoint events $A_1, A_2, ...$ such that $P[A_i] = p_i$, not necessarily same $p$. For simplicity let us also assume independence, so the probability of subsets of $A_i$s is straightforward. The question is, given an event or subset of events (whose probability we can compute from the arbitrary probability distribution), when is the expected time finite? $\endgroup$
    – Sefi Potashnik
    Commented Jul 2 at 16:33

1 Answer 1

Reset to default
2
$\begingroup$

If $T:=\min\{n: A_n$ occurs$\}$, then $$ \{T\ge k\} = \cap_{n=1}^{k-1}A_n^c, $$ so $$ P(T\ge k) =\prod_{n=1}^{k-1}(1-p_n),\qquad k\ge 1, $$ the empty sum being understood to equal $1$. Therefore $$ E(T) =\sum_{k=1}^\infty P(T\ge k)=\sum_{k=1}^\infty (1-p_1)(1-p_2)\cdots (1-p_{k-1}). $$

For example, if $p_n=r/n$ for some $r>0$, then $P(T<\infty)=1$. If $r>1$, then $E(T)<\infty$.

$\endgroup$
1
  • $\begingroup$ Thank you very much $\endgroup$
    – Sefi Potashnik
    Commented Jul 2 at 18:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .