<p>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.</p>

<p>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</p>

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

<p>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:</p>

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

<p>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:</p>

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

<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$.</p>

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

CC BY-SA 2.5
2010-10-02T13:23:15.357Z
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
CC BY-SA 2.5
2010-10-02T13:56:13.507Z
@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
CC BY-SA 2.5
2010-10-02T12:02:57.583Z
2010-10-02T12:39:42.930Z
2010-10-02T12:39:42.930Z
Per Vognsen
<p>I'm sorry if the following question seems too obvious. In fact, I oversimplified a much harder problem to this one.</p>

<p>Consider the following algorithm, where $0 &lt; p \le 1$ is a constant:</p>

<pre><code>1. Halt with probability p.
2. GOTO 1.
</code></pre>

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

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

<pre><code>1. Draw X independently from a Bernoulli distribution with mean p.
2. Halt if X=1.
3. GOTO 1.
</code></pre>

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

CC BY-SA 2.5
2010-10-02T11:25:09.310Z
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
CC BY-SA 2.5
2010-10-02T13:21:57.917Z
@Tsuyoshi, @Kaveh: You are right about the first algorithm, but what I'm asking is about the second one. The excellent answer, provided by Per Vognsen, shows that it is not as trivial as it seems.
Incredible
CC BY-SA 2.5
2010-10-02T13:25:46.617Z
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
CC BY-SA 2.5
2010-10-02T13:33:16.257Z
I have read Per Vognsen's answer, it does not change my opinion, this is an elementary probability theory question.
Kaveh
CC BY-SA 2.5
2010-10-02T13:41:56.340Z
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
CC BY-SA 2.5
2010-10-02T14:24:09.480Z
@Kaveh: In my opinion, too easy questions should be marked as “too localized” instead of “off topic.”  Please see [the reason](http://meta.cstheory.stackexchange.com/questions/356/the-reason-to-close-too-elementary-questions).  If you or anyone else has comments about this, please write in the linked discussion instead of here.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-02T14:30:02.517Z
@Incredible: I am afraid that you misunderstood my first comment.  It refers to the second algorithm.  Specifically, “steps 1 and 2” refer to the first two steps in the second algorithm.  I have not said anything about the first algorithm.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-02T14:37:26.583Z
@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
CC BY-SA 2.5
2010-10-02T15:09:41.907Z
@Tsuyoshi: Sure. You can always eliminate intermediate distributions. A problem like the present one is too simple to shine light on the finer points. The question poster said his original problem was more complex than what he posted, so I figured it might be worthwhile to go into more detail. In case you were worried, I didn't actually work it out in my head the way I wrote it in the answer; I saw the answer instantly based on the same kind of reasoning that guided your response.
Per Vognsen
CC BY-SA 2.5
2010-10-02T15:29:17.837Z
@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
<ds.algorithms><pr.probability>
Expected Halt Time
Incredible
# Expected Halt Time

(Asked by: username_0 on 2010-10-02)

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

**Tags:** ds.algorithms, pr.probability
> **Comments:**
> **username_1**: 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.)  
> **username_0**: @Tsuyoshi, @Kaveh: You are right about the first algorithm, but what I'm asking is about the second one. The excellent answer, provided by Per Vognsen, shows that it is not as trivial as it seems.  
> **username_2**: 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.  
> **username_2**: I have read Per Vognsen's answer, it does not change my opinion, this is an elementary probability theory question.  
> **username_3**: 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.  
> **username_1**: @Kaveh: In my opinion, too easy questions should be marked as “too localized” instead of “off topic.”  Please see [the reason](http://meta.cstheory.stackexchange.com/questions/356/the-reason-to-close-too-elementary-questions).  If you or anyone else has comments about this, please write in the linked discussion instead of here.  
> **username_1**: @Incredible: I am afraid that you misunderstood my first comment.  It refers to the second algorithm.  Specifically, “steps 1 and 2” refer to the first two steps in the second algorithm.  I have not said anything about the first algorithm.  
> **username_1**: @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.  
> **username_3**: @Tsuyoshi: Sure. You can always eliminate intermediate distributions. A problem like the present one is too simple to shine light on the finer points. The question poster said his original problem was more complex than what he posted, so I figured it might be worthwhile to go into more detail. In case you were worried, I didn't actually work it out in my head the way I wrote it in the answer; I saw the answer instantly based on the same kind of reasoning that guided your response.  
> **username_1**: @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.  

---

## 1 answers

### Answer by username_3 on 2010-10-02. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_3**: @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.  

---

