4
$\begingroup$

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})$?

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – Tsuyoshi Ito Oct 2 '10 at 11:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Oct 2 '10 at 13:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Per Vognsen Oct 2 '10 at 13:41
  • 2
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Oct 2 '10 at 14:37
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Oct 2 '10 at 15:29
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Incredible Oct 2 '10 at 13:23
  • $\begingroup$ @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. $\endgroup$ – Per Vognsen Oct 2 '10 at 13:56

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.