# Expected Halt Time

I'm sorry if the following question seems too obvious. In fact, I oversimplified a much harder problem to this one.

Consider the following algorithm, where $0 < p \le 1$ is a constant:

1. Halt with probability p.
2. GOTO 1.


Obviously, the algorithm's expected running time is $O({1 \over p})$.

Now, assume that p is not a constant; it is drawn from a Bernoulli (0-1) distribution whose mean (=expectation) is p ($0 < p \le 1$):

1. Draw X independently from a Bernoulli distribution with mean p.
2. Halt if X=1.
3. GOTO 1.


Can we say that the second algorithm's expected running time is $O({1 \over p})$?

• This question is too localized or elementary. Hint: What happens if you consider steps 1 and 2 together as one subroutine? (I am assuming that each p is drawn iid.) – Tsuyoshi Ito Oct 2 '10 at 11:25
• I agree with Tsuyoshi, this is an easy question in elementary probability theory. The expectation for the number of coin flips until we see the first head. – Kaveh Oct 2 '10 at 13:25
• The calculation is trivial, but I figured it was a chance to make some comments on nested random variables. They show up in a few common places (e.g. hyper-distributions in Bayesian analysis, density matrices as classical superpositions over quantum superpositions, etc). One of the things that isn't usually remarked is that expectation is a monadic join: a deterministic world isn't the same as a probabilistic world, but a probabilistic world within a probabilistic world is isomorphic to a single probabilistic world. – Per Vognsen Oct 2 '10 at 13:41
• @Per: I am afraid that you have made the problem harder by thinking that way. As I suggested in my first comment, the first two steps in the second algorithm merely implement the step 1 in the first algorithm. – Tsuyoshi Ito Oct 2 '10 at 14:37
• @Per: The point of my reply to you was that not only the calculation but also the idea was simple, because you stated that the calculation was trivial. I would not say the problem is trivial just because the calculation is simple, if a brilliant idea is needed to lead to the simple calculation. – Tsuyoshi Ito Oct 2 '10 at 15:29

I'm not exactly sure why you say the distribution in step 1 is Bernoulli. It actually doesn't matter if all you care about is the expected running time.

Let $P_i$ be the random variable whose value is the halting probability in step $i$ and let $T$ be the running time. The expected running time is then

$$\mathbb{E}[T] = \sum n\ (1 - P_1) \cdots (1 - P_{n-1})\ P_n$$

Despite being an expected value, it's still a random variable! To flatten the last layer of randomness, you must hit it one last time with the expectation operator:

$$\mathbb{E}[\mathbb{E}[T]] = \sum n\ \mathbb{E}[(1 - P_1) \cdots (1 - P_{n-1})\ P_n]$$

This is as far as we can go without making any assumptions. If the $P_i$ are IID then expectation is multiplicative, so let us assume they are:

$$\mathbb{E}[\mathbb{E}[T]] = \sum n\ (1 - p)^{n-1} p,$$

where $p = \mathbb{E}[P_1] = \mathbb{E}[P_2] = \cdots$. This is the expected waiting time of a Bernoulli process with probability $p$, which indeed equals $1/p$.

The moral is that everything flattens in a trivial way with nested expectation values of independent variables.

• Very excellent explanation. Could you just clarify why you computed E[E[T]] while we were after E[T]? Should we do this every time E[T] is a random variable instead of some number? – Incredible Oct 2 '10 at 13:23
• @Incredible: It's because there are two layers of randomness. The first expectation strips away the randomness in step 1. It's as if step 1 always picked the same value of $p$ (which is $\mu$). Thereby the second problem is reduced to the first problem. – Per Vognsen Oct 2 '10 at 13:56