Cryptography Reference
In-Depth Information
E.2 Randomness, Expectation, and Variance
There is another probabilistic notion that will be used is the notion of “ex-
pectation”.
A real-valued function
X
:
S
→
R
S
{
}
is called a
random variable
. For simplicity, we assume that the random variables take on
only finitely many values.
of a set
=
s
1
,s
2
,...,s
n
Expectation
If the probabilities of
S
are given by
p
s
j
=
p
j
for
j
=1
,
2
,...,n
, then the
expected value
of
X
is given by
E
(
X
)=
p
1
·
X
(
s
1
)+
p
2
·
X
(
s
2
)+
···
+
p
n
·
X
(
s
n
)
.
(
X
), is given
by looking at a large number of independent trials
N
, say, with outcomes
s
j
1
,s
j
2
,...,s
j
N
, for suGciently large
N
:
Moreover,
the
average value
,
which will be “close to”
E
X
(
s
j
1
)+
X
(
s
j
2
)+
···
+
X
(
s
j
N
)
.
N
Variance
The
variance
of
X
is defined by
(
X
))
2
)
.
var(
X
)=
E
((
X
−
E
The square root of the variance is called the
standard deviation
of
X
. The
following are central results on the notion of expectation and variance.
The Expectation Theorem
If
X
,
Y
are random variables and
a,b
∈
R
then
E
(
aX
+
bY
)=
a
E
(
X
)+
b
E
(
Y
)
,
and if
X
and
Y
are independent, then
E
(
XY
)=
E
(
X
)
·
E
(
Y
)
.
Search WWH ::
Custom Search