1
$\begingroup$

In page 21 of A Problem seminar, D. J. Newman presents a novel way (at least for me) to determine the expectation of a discrete random variable. He refers to this expression as the failure probability formula. His formula goes like this

$f_{0}+f_{1}+f_{2}+\ldots$

where $f_{n}$ is the probability that the experiment fails to produce the desired outcome for $n$ steps.

He goes on to outlining two ways to establish the validity of this formula, but I'm having a hard time to unravel his second proof. I'll insert it here in order for my inquiry to be self-contained:

Since the expected amount of time spent on the $n$ trial is equal to the probability that the $n$ trial occurs, and since this equal to $f_{n-1}$, we do obtain the net expectation of $f_{0}+f_{1}+f_{2}+\ldots$ as asserted.

Can any of you guys explain in greater detail this Newmanian argument? I'd also like to know whether the denomination failure probability formula is a standard one in the mainstream of Probability literature.

Thank you very much for your continued support.

$\endgroup$
3
  • 1
    $\begingroup$ Not an answer to the question asked, but it seems interesting to note that it is not only for integer-valued random variables that this works. If you have any non-negative-valued random variable $X$, its expected value is of course given by the Riemann-Stieltjes integral $\int_0^\infty x\,dF(x)$ where $F(x) = \Pr(X \le x)$ is the cumulative distribution function, but it's also given by the Riemann integral $\int_0^\infty \Pr(X > x) \,dx$, which is the same as what you gave when the values are nonnegative integers. $\endgroup$ Jun 15, 2010 at 21:40
  • 2
    $\begingroup$ I don't think there's a standard name for this trick, but the formula itself is reasonably well-known. I suspect that Newman gives it a name because he wants to refer to it later and it's easier to say "by the failure probability formula" than "by that thing we did before". $\endgroup$ Jun 16, 2010 at 12:55
  • $\begingroup$ Thanks for taking the time to leave your comments, gentlemen. $\endgroup$ Jun 16, 2010 at 16:46

2 Answers 2

3
$\begingroup$

Well, this is certainly a known idea, but I suspect it's not important enough to have its own name. For example, I believe it is used without special mention in Hammersley's "A Few Seedlings of Research" (Proc. 6th Berkeley Symp. on Math. Stat. and Prob., 1971), which has as its target audience a graduate student just beginning research in mathematical statistics.

Here's one way of thinking about the argument: imagine the countably infinite sequence of experiments starting all lined up and ready to go; each experiment will run if the preceding one runs but is unsuccessful. The expected number of steps is the same as the expected number of these experiments that actually run. Thus, the expected number of steps is the sum over $n$ of the probability that the $n$th experiment runs. But this is precisely $f_{n - 1}$ (the probability that all the experiments before it fail).


An alternative perspective: let $p_n$ be the probability that it requires exactly $n$ steps. Then summing $$\begin{array}{ccccc} p_1 & & & & \\\\ p_2 & p_2 & & & \\\\ p_3 & p_3 & p_3 & & \\\\ p_4 & p_4 & p_4 & p_4 & \\\\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$ first by rows gives the "usual" expression for expected value while summing first by columns gives this expression you're dealing with. (If everything converges then it converges absolutely, so no need to worry about rearranging.)

Basically the same phenomenon is going on in the continuous version Michael Hardy mentions -- in that case we are calculating the area of one region in the $xy$-plane in two different ways, integrating with respect to $x$ in one and with respect to $y$ in the other.

$\endgroup$
0
3
$\begingroup$

I have not heard about this terminology. I am not a native English speaker though.

It is essentially integration by parts, see the section titled "Formulas for special cases" in http://en.wikipedia.org/wiki/Expected_value.

UPD. Let $Y_n$ be time spent while waiting during the time period no. $n$, i.e. $Y_n=1_{X\ge n}$. It can be $0$ or $1$, so that $\mathbf{E}Y_n=\mathbf{P}[Y_n=1]=\mathbf{P}[X\ge n]=f_{n-1}$.

The formula in question follows from $X=\sum_{n=1}^{\infty} Y_n$.

EXERCISE. Find out why this computation is the same as in the wikipedia article.

$\endgroup$
1
  • $\begingroup$ Well, the principal aim of the question was to obtain insights into the Newmanian argument showcased in the above gray box. $\endgroup$ Jun 3, 2010 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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