2
$\begingroup$

We repeat independent trials when each time more than 2 events can happen:

  • event $A$ with probability $p$
  • event $B$ (in the complement of $A$) with probability $q$
  • something different with probability $1-p-q$

(For example we can consider rolling a die where $A=$"result is 6" and $B=$ "result is 5 or 4").

Problem: what is the expected waiting time for $A$ and $B$ to have both of them happened at least once in the trials so far?

Here is what I have done:

  1. I compute the probability that $A$ happens before $B$ in an infinite sequence of trials: $$ P(A \text{ happens before B})=\sum_{k=0}^\infty P(\text{A and B didn't happen in $k$ trials})p $$ $$ = p\sum_{k=0}^\infty (1-q-p)^k=\frac {p}{p+q} $$
  2. I assume event $A$ happens before $B$ and compute conditional expected waiting time, that is we compute how long we wait for $A$ to happen assuming $B$ is not going to happen: it is $T$ such that $$ T=1 \cdot P(\text{$A$ happens}|\text{$B$ doesn't happen})+(T+1)\cdot P(\text{$A$ doesn't happen}|\text{$B$ doesn't happen}) $$ that is $$ T=\frac p {1-q}+(T+1)\frac {1-p-q}{1-q} $$ solving fot $T$ we have $$ T=\frac {1-q}{p} $$
  3. I compute the expected time to have event $B$ (after $A$ has just happened): $T$ satisfies $$ T=1 \cdot q+ (T+1) \cdot (1-q) $$ that is $T=\frac 1 q$. This time must be added to the time computed in 2 in order to have the first time that both $A$ and $B$ have occurred that is $T=\frac 1 q$.
  4. I put all together to compute expected time to have $A$ and $B$ both happened. Call $T$ such expected time, then we must have: $$ T=P(\text{$A$ happens fist})\cdot \left(\frac {1-q}{p}+\frac 1 q\right)+P(\text{$B$ happens fist})\cdot \left(\frac {1-p}{q}+\frac 1 p\right) $$ (the first part follows from computation above, the second by symmetry) then we substitute the probabilities in point 1: $P(\text{$A$ happens fist})=\frac {p}{p+q}$ and $P(\text{$A$ happens fist})=\frac {q}{p+q}$ (by simmetry) and I get the result $$ T=\frac 1 p +\frac 1 q -1. $$ that seems quite implausible.

Questions: What is wrong with this computation? Are there quicker/better ways to do this computation?

$\endgroup$
3
$\begingroup$

It is easy to show that if neither $p$ nor $q$ is $0$, the expectation exists. Let $E$ be the desired expectation. Condition on the result of the first trial.

If $A$ occurs, then the expected additional time for $B$ to occur is $\frac{1}{q}$. If $B$ occurs, the expected additional time for $A$ to occur is $\frac{1}{p}$.

If neither occurs then the expected additional time is $E$. In all cases we have "used up" one trial. Thus $$E=1+p\cdot\frac{1}{q}+q\cdot\frac{1}{p}+(1-p-q)E.$$ Solve for $E$.

$\endgroup$
  • $\begingroup$ Superquick! The result seems to be $E=\frac 1 p + \frac 1 q - \frac 1 {p+q}$ (that could also suggest another way of reasoning). $\endgroup$ – Marco Disce Feb 24 '16 at 16:05
  • $\begingroup$ I'm a little bit confused now... The formula $E=\frac 1 p$ for the waiting time of $p$ comes from the equation $E=p+(1-p)(E+1)$, if instead we wanted to use $E-1=p+(1-p)E$ we would get $E=\frac 1 p +1$. They can both be ok, it depends on whether the last trial must count as 1 more unit of time or not. But shouldn't we be coherent when we concatenate formulas obtained in this way? $\endgroup$ – Marco Disce Feb 24 '16 at 16:32
  • $\begingroup$ For the expected additional time for $B$ to occur given that $A$ has occurred on the first trial, I simply quoted the standard result about the expectation of a geometric distribution. One can derive that expectation by using a simpler version of the reasoning I used in the answer, but one would not use the same letter $E$ for that calculation. Let the expectation of the additional time in that case be $F$. Then $F=q\cdot 1+(1-q)(1+F)$, which gives $F=1/q$. $\endgroup$ – André Nicolas Feb 24 '16 at 16:41

Your Answer

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

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