Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Michael Hardy Jun 15 '10 at 21:40
2  
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". –  Michael Lugo Jun 16 '10 at 12:55
    
Thanks for taking the time to leave your comments, gentlemen. –  J. H. S. Jun 16 '10 at 16:46
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you very much for such a detailed reply, Joel. –  J. H. S. Jun 16 '10 at 16:45
add comment

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.

share|improve this answer
    
Well, the principal aim of the question was to obtain insights into the Newmanian argument showcased in the above gray box. –  J. H. S. Jun 3 '10 at 22:08
    
Thanks for taking the time to reply, Professor Bakhtin. –  J. H. S. Jun 16 '10 at 16:46
    
no problem, J.H.S. –  Yuri Bakhtin Jun 16 '10 at 23:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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