Wald's equation

From Wikipedia, the free encyclopedia

In probability theory, Wald's equation is an important identity which simplifies the calculation of the expected value of the sum of a random number of random quantities. Formally, it relates the expectation of a sum of randomly many i.i.d. random variables to the expected number of terms in the sum and the random variables' common expectation.

Let X₁, X₂, ..., X_T be a sequence of T i.i.d. random variables distributed identically to some random variable X, such that

T > 0 is itself a random variable (integer-valued),
the expectation of X, E(X) < ∞, and
E(T) < ∞.

Then

$\operatorname{E}\left(\sum_{i=1}^{T}X_i\right)=\operatorname{E}(T)\operatorname{E}(X).$

In this case, the random number T acts as a stopping time for the stochastic process { X_i, i = 1, 2, ... }.

[edit] Proof

Define a second sequence of random variables, Y_n:

$Y_n = \sum_{i=1}^{n}X_i - n\operatorname{E}(X)$

It can be seen from elementary probability that Y_n is a martingale, and moreover satisfies the conditions of the optional stopping theorem. Hence

$\operatorname{E}\left(\sum_{i=1}^{T}X_i - T\operatorname{E}(X)\right) = \operatorname{E}(Y_T) = \operatorname{E}(Y_0) = 0$

And the result follows by simple rearrangement.

[edit] See also

Abraham Wald

[edit] References

Wald, Abraham (Sep 1944). "On Cumulative Sums of Random Variables". The Annals of Mathematical Statistics 15 (3): 283-296. doi:10.1214/aoms/1177731235.
Chan, Hock Peng; Fuh, Cheng-Der; Hu, Inchi (2006). "Multi-armed bandit problem with precedence relations" (subscription required). IMS Lecture Notes: Time Series and Related Topics 52: 223-235.