I am trying to understand the "story proof" found in this lecture.

I am a bit confused as how the expected value of a random variable differs from the the random variable itself when considering indicator functions.

Say there is a geometric distribution. $X$ counts the number of the failures before the first success, and $E(X)$ is the expected number of failures.

Now I want to compute the expected value given $p$, the probability of success, and $q$ otherwise.
Let $c=E(X)$.

Now I do first-step analysis, $$c=0\cdot p+(1+c)q.$$

In this step, I don't understand the coefficient of $q$. In $(1+c)$, $1$ makes sense but why $c$?
When computing the expected value: it is the $kp^kq^k$. So the coefficient $k$ is the value of the random variable. But in my example it is the expected value $c$ at the next step which confuses me.

  • $\begingroup$ What is start-step analysis? Also, in this case, $P(X = k) = (1-p)^kp$, so the usual approach is to attempt to compute $E[X] = \sum_{k = 0}^\infty k\cdot (1-p)^kp.$ $\endgroup$ – Em. Jun 1 '16 at 22:49
  • $\begingroup$ @probablyme I know that can get the answer, but I am considering the story proof mentioned here. youtube.com/watch?v=LX2q356N2rU at 48:20 $\endgroup$ – Abhishek Bhatia Jun 1 '16 at 22:52
  • 1
    $\begingroup$ At the first step, you either succeed (and stop) with probability $p$ or fail (count $1$ failure and start again) with probability $q$. Starting again involves the same expected number going forward, plus $1$ for the failure already observed. So $E[X] = 0\cdot p + (1+E[X])\cdot q$ so $E[X]=\frac{q}{1-q}=\frac{q}{p}=\frac{1-p}{p}$ $\endgroup$ – Henry Jun 1 '16 at 22:54
  • 1
    $\begingroup$ That's an hour long lecture; try to include all relevant information in posts, and a time stamp if you refer to any videos. Anyway, it's usually called first-step analysis, and the basic idea is that you're "starting over", as Henry points out. Also, properly format your post. Use \cdot for multiplication (if you must). Formatting tips here. $\endgroup$ – Em. Jun 1 '16 at 22:59
  • $\begingroup$ @Henry Thanks for the reply! I can't comprehend the recursive formulation you mentioned here. What does Starting again involves the same expected number mean? Why are you multiply that with the probability of failure. It should multiplied by the value of random variable not the expected value of it. $\endgroup$ – Abhishek Bhatia Jun 1 '16 at 23:00

Let $c=E(X)$. We use a conditional expectation argument, conditioning on the result of the first trial.

Either (i) we have a success on the first trial, or (ii) we have a failure on the first trial.

Case (i) has probability $p$.

Case (ii) has probability $q=1-p$. In that case, we have had a failure, and the expected number of additional failures before the first success is $c$. So the conditional expectation of $X$, given that there was a failure on the first trial, is $1+c$.

By the Law of Total Expectation, we therefore have $$E(X)=c=(p)(0)+(q)(1+c).$$ Finally, solve this linear equation for $c$. We get $c(1-q)=q$, and therefore $c=\frac{q}{1-q}=\frac{q}{p}=\frac{1}{p}-1$.

| cite | improve this answer | |
  • $\begingroup$ Thanks! Can you elaborate more on the Law of Total Expectation. $\endgroup$ – Abhishek Bhatia Jun 1 '16 at 23:09
  • $\begingroup$ Why is q=1 in the last step? Is that a typo?$c=q/p$. $\endgroup$ – Abhishek Bhatia Jun 1 '16 at 23:14
  • $\begingroup$ If the random variable $X$ is equal to (the random variable) $X_1$ with probability $p_1$, to $X_2$ with probability $p_2$, and so on, where $P_1+p_2+\cdots +p_n=1$, then $E(X)=p_1E(X_1)+\cdots +p_nE(X_n)$. There are fancier versions, which you can read about on Wikipedia. Note that there are other ways to find $E(X)$ in our example, but the conditioning trick, which you called first step analysis, is the simplest one. $\endgroup$ – André Nicolas Jun 1 '16 at 23:17
  • $\begingroup$ @AbhishekBhatia: That was a typo, I wrote $\frac{1}{p}=1$ where I meant $\frac{1}{p}-1$. Aimed for the minus key and missed. $\endgroup$ – André Nicolas Jun 1 '16 at 23:19

This answer is similar to others, but here the first-step analysis $(^*)$ is expressed entirely in terms of random variables before taking expectations, and then without using conditional expectation.

Let the sequence of i.i.d. Bernoulli trials be $(Y_1,Y_2,Y_3,...)$, with $P(Y_1=\text{success})=p\ $, and define $$X_i = \text{ number of failures before the first success in }(Y_i,Y_{i+1},Y_{i+2},...).$$

Note that $(X_1, X_2, X_3,...)$ are identically distributed, and that $X_i$ is independent of $Y_j$ for any $j<i$; therefore, using indicator functions $[...]$, $$X_1 = 0\cdot[Y_1=\text{success}] + (1 + X_2)\cdot[Y_1=\text{failure}],\tag{*}$$ so $$\begin{align}\mathbb{E}(X_1) &= \mathbb{E}(1 + X_2)\cdot\mathbb{E}[Y_1=\text{failure}]\\ &= (1 + \mathbb{E}(X_2))\cdot P(Y_1=\text{failure})\\ &= (1 + \mathbb{E}(X_1))\cdot (1-p)\\ \\ \therefore\ \mathbb{E}(X_1) &= \frac{1-p}{p}. \end{align} $$

| cite | improve this answer | |

Another approach is that when $X$ counts the number of failures before the first success (in a sequence of iid Bernoulli trials of success rate $p$), then:

$$\begin{align}\mathsf E(X) =&~ \sum_{k=0}^\infty k~\mathsf P(X=k) \\[1ex] =&~ \sum_{k=0}^\infty k(1-p)^{k} p \\[1ex] =&~ 0(1-p)^0p+\sum_{k=1}^\infty k(1-p)^{k}p\\[1ex] =&~ 0\,p + \sum_{h=0}^\infty (h+1)(1-p)^{h+1}p \\[1ex] =&~ 0\,p + (1-p)~\sum_{h=0}^\infty (h+1)(1-p)^hp \\[1ex] =&~ 0\,p+(1-p)\mathsf E(X+1) \\[1ex] =&~ 0\,p+(1-p)\,(1+\mathsf E(X))\\[2ex]\therefore~\mathsf E(X) =&~ \tfrac {1-p}p \end{align}$$

That is a bit of a slog but should give some insight as to why (and how) partitioning on the result of the first trail works.   If the first trial is a success then we are done and the expected count is 0 (on that condition).   If the first trial is a failure then the expected count (on that condition) is one more than the expected count after that failure before the first success.   This little bit of reasoning saves some effort and we immediately jump to the end by using the Law of Total Expectation.

Let $X_1$ be the count of successes in the first trial; which is $1$ or $0$ ; with probabilities $p$ and $1-p$ respectively.

$$\begin{align}\mathsf E(X) =&~ \mathsf E(\mathsf E(X\mid X_1)) \\[1ex] =&~ \mathsf P(X_1=1)~\mathsf E(X\mid X_1=1)+\mathsf P(X_1=0)~\mathsf E(X\mid X_1=0) \\[1ex] =&~ p\cdot 0 + (1-p)~(1+\mathsf E(X))\end{align}$$

| cite | improve this answer | |

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.