Take the 2-minute tour ×

I have $P(t) = 1-(1-R^{-t})^N$ which is the probability that I need more than t operations in my algorithm, t is a random variable then, I can assign a probability to it.

Why is it that the sum of probabilities of t


is the average value for that variable? I mean: the formula for the average value of a random variable is:

$E[X]=\sum\limits_{i=1}^\infty{x_i p_i}$

but since my random variable is "I need more than t elements", which is its value $p_i$?

( http://en.wikipedia.org/wiki/Expected_value#Discrete_random_variable.2C_countable_case )

share|improve this question

3 Answers 3

up vote 4 down vote accepted

Your notation seems somewhat confused. Let me try to clarify it, so that it'll perhaps be easier to see what's going on.

Let's use the random variable $T$ to denote the number of operations needed in your algorithm. According to your description, $$P(t) = \mathbb P( T \ge t )= 1-(1-R^{-t})^N$$ is the probability that $T \ge t$, i.e. that the algorithm needs at least $t$ operations. (You write "more than" instead of "at least", but the formula you give below suggests that you did, in fact, mean "at least".)

Note: I'm following here the fairly common convention to use upper case letters for random variables and lower case letters for constants, since it's often important to have some way to distinguish the two. Also, I'll use the fancy $\mathbb P$ to denote the probability $\mathbb P(A)$ of an event $A$ occurring, leaving the ordinary $P$ free for custom notation such as your function $P(t)$. (Of course, the uppercase $R$ and $N$ in the formula above are presumably also constants, as indeed is $P(t)$, so I'm not being completely consistent with the case distinction.)

Now, as Wikipedia correctly notes, the expected value of the (discrete) random variable $T$ is given by the weighted average $$\mathbb E(T) = \sum_t t \, \mathbb P(T = t),$$ where the sum is taken over all possible values of $T$ (here, presumably $\mathbb N$).

Note that this formula does not involve $P(t) = \mathbb P(T \ge t)$; however, we can rewrite it in terms of $P(t)$ by noting that $$\mathbb P(T = t) = \mathbb P(T \ge t) - \mathbb P(T \ge t+1) = P(t) - P(t+1),$$ giving us $$\begin{aligned} \mathbb E(T) &= \sum_{t=0}^\infty t (P(t) - P(t+1)) \\ &= \sum_{t=0}^\infty t P(t) - \sum_{t=0}^\infty t P(t+1) \\ &= \sum_{t=0}^\infty t P(t) - \sum_{t=1}^\infty (t-1) P(t) \\ &= 0P(0) + \sum_{t=1}^\infty t P(t) - \sum_{t=1}^\infty (t-1) P(t) \\ &= 0P(0) + \sum_{t=1}^\infty (t - (t-1)) P(t) \\ &= 0P(0) + \sum_{t=1}^\infty 1 P(t) \\ &= \sum_{t=1}^\infty P(t). \end{aligned}$$

Ps. Another, possibly more intuitive way of seeing why this formula is valid is to note that the number of operations actually needed by the algorithm in any given case can be obtained by counting the actual operations needed: $$T = \sum_{t=1}^T 1 = \sum_{t=1}^\infty \mathbf 1_{T \ge t},$$ where $\mathbf 1_A$ denotes the indicator function of the event $A$, i.e. $$\mathbf 1_A = \begin{cases} 1 & \text{if }A \\ 0 & \text{if not }A. \end{cases}$$

Taking the expected value of both sides, we obtain $$\mathbb E(T) = \mathbb E \left( \sum_{t=1}^\infty \mathbf 1_{T \ge t} \right).$$ Since the expected value operator is linear, the expected value of a sum is the sum of the expected values of the terms, i.e. $$\mathbb E(T) = \sum_{t=1}^\infty \mathbb E(\mathbf 1_{T \ge t}),$$ and since $\mathbb E(\mathbf 1_A) = \mathbb P(A)$, we get $$\mathbb E(T) = \sum_{t=1}^\infty \mathbb P(T \ge t) = \sum_{t=1}^\infty P(t).$$

share|improve this answer
Great work! Thank you!! –  John Smith Sep 14 '12 at 20:47

What you say is wrong. The sum of the probabilities has to be 1. However, I think you misinterpret $P(t)$. $P(t)=\mathbb{P}(T\geq t)$, i.e. the probability you need more than $t$ operations. And in that case, it is true that the sum over all values of $t$ of the $P(t)$ is indeed the expected value, as you can read a bit further down on the same wikipage you quote.

share|improve this answer
Thank you but I think the indices on the wiki page you linked are wrong.. "interchanging the order of summation, we have" $\sum\limits_{i=1}^\infty P(X\geq i)&=\sum\limits_{j=1}^\infty \sum\limits_{i=1}^j P(X = j)$ I can't see why –  John Smith Sep 14 '12 at 17:48
The indices are right. I have however noticed a mistake in my own reply. $P(t)=\mathbb{P}(T\geq t)$ and it is thus the probability of needing more than $t$ operations. –  Raskolnikov Sep 14 '12 at 17:52

If you use $Q(t)=1-P(t)$, that gives you probability that you need $\le t$ operations. Then, $A(t)=Q(t)-Q(t-1)$ is the probability you need exactly $t$. $\sum t A(t)$ will give you the average number of ops.

share|improve this answer

Your Answer


