Cryptography Reference
In-Depth Information
and X ( D )=0—and one may be interested in the expectation for X . Referring to
(4.2), the expectation of X (i.e., E [ X ]) can be computed as follows:
1= 1
3
Consequently, if one plays the game, then one can reasonably expect to win
one third of a dollar in the average (i.e., the game is more than fair). Another typical
application of a random variable's expectation is the running time of a randomized
algorithm. Remember from Section 1.2 that a randomized algorithm depends on
internal random values and that a complete analysis of the algorithm would be
a specification of the running time of the algorithm for every possible sequence
of random values. This is clearly impractical, and one may analyze the expected
running time of the algorithm instead. This refers to a single value that may still
provide some useful information about the typical behavior of the algorithm.
In practice, the linearity of expectations is frequently used to compute the
expectation of a random variable X . The linearity of expectations basically means
that
E [ X ]= 1
2) + 1
0+ 2
6 ·
(
6 ·
3 ·
E [ aX ]= aE [ X ]
for all a
. Similarly, if X 1 ,X 2 ,...,X n are random variables over the same
sample space, then
R
E [ X 1 + X 2 + ... + X n ]= E [ X 1 ]+ E [ X 2 ]+ ... + E [ X n ] .
For example, we want to compute the expected number of heads when flip-
ping a coin n times. Without making use of the linearity of expectations, this com-
putation is quite involved. Making use of the linearity of expectations, however,
this computation becomes simple and straightforward. We define a random vari-
able X that is the sum of n random variables X 1 ,X 2 ,...,X n ,where X i is 1 if
the i th
coin flip is 1 ( X i is 0 otherwise). Then E [ X i ]= 2 ·
0+ 2 ·
1= 2
and
1
2 = n
E [ X ]= E [ X 1 + X 2 + ... + X n ]= E [ X 1 ]+ E [ X 2 ]+ ... + E [ X n ]= n
·
2 .
,then
f ( X ) is a real-valued random variable with an expected value that can be computed
as follows:
More generally, if f is a real-valued function whose domain includes
X
E [ f ( X )] =
x∈X
f ( x ) P X ( x )
Search WWH ::




Custom Search