Cryptography Reference
In-Depth Information
X
=
|
X
−
E
[
X
]
|
to provide some information about the likelihood that
X
deviates a lot from its
expectation. More specifically, if
X
is expected to be small, then
X
is not likely
to deviate a lot from its expectation. Unfortunately,
X
is not easier to analyze than
X
, and hence
X
is not particularly useful to consider as a complementary random
variable.
As a viable alternative, one may consider the complementary random variable
X
=(
X
E
[
X
])
2
.
−
Again, if the expectation of
X
is small, then
X
is typically close to its
expectation. In fact, the expectation of the random variable
X
turns out to be a
useful measure in practice. It is called the
variance
of
X
, denoted as
Var
[
X
],andit
is formally defined as follows:
E
[
X
])
2
]=
x
E
[
X
])
2
Var
[
X
]=
E
[(
X
−
P
X
(
x
)
·
(
x
−
∈X
Alternatively, the variance of
X
can also be expressed as follows:
E
[
X
])
2
]
Var
[
X
]=
E
[(
X
−
E
[
X
2
2
XE
[
X
]+(
E
[
X
])
2
]
=
−
E
[
X
2
]
2
E
[
XE
[
X
]] + (
E
[
X
])
2
=
−
E
[
X
2
]
2
E
[
X
]
E
[
X
]+(
E
[
X
])
2
=
−
E
[
X
2
]
2(
E
[
X
])
2
+(
E
[
X
])
2
=
−
E
[
X
2
]
(
E
[
X
])
2
=
−
For example, let
X
be a random variable that is equal to zero with probability
1
/
2 and to 1 with probability 1
/
2.Then
E
[
X
]=
2
·
0+
2
·
1=
2
,
X
=
X
2
(because
0=0
2
and 1=1
2
), and
1
2
−
1
4
=
1
4
.
Var
[
X
]=
E
[
X
2
]
(
E
[
X
])
2
=
−
