Cryptography Reference
In-Depth Information
Definition 4.2 (Random variable)
Let
(Ω
,
Pr)
be a discrete probabiliy space with
sample space
Ω
and probability measure
Pr[
·
]
. Any function
X
:Ω
→X
from the
sample space to a measurable set
X
is a
random variable
.Theset
X
, in turn, is the
range
of the random variable
X
.
Consequently, a random variable is a function that on input an arbitrary
element of the sample space of a discrete probability space (or random experiment)
outputs an element of the range. In a typical setting,
X
is either a subset of the real
numbers (i.e.,
X⊆
R
) or a subset of the binary strings of a specific length
n
(i.e.,
n
).
3
If
x
is in the range of
X
(i.e.,
x
X⊆{
0
,
1
}
∈X
), then the expression (
X
=
x
) refers
to the event
, and hence Pr[
X
=
x
] is defined and something
potentially interesting to compute. If only one random variable
X
is considered, then
Pr[
X
=
x
] is sometimes also written as Pr[
x
].
If, for example, we roll two fair dice, then the sample space is Ω=
{
ω
∈
Ω
|
X
(
ω
)=
x
}
{
2
and the probability distribution is uniform (i.e., Pr[
ω
1
,ω
2
]=1
/
6
2
=
1
/
36 for every (
ω
1
,ω
2
)
1
,
2
,...,
6
}
∈
Ω). Let
X
be the random variable that associates
ω
1
+
ω
2
to every (
ω
1
,ω
2
)
∈
Ω. Then the range of the random variable
X
is
X
. For every element of the range, we can compute the probability
that
X
takes this value. In fact, by counting the number of elements in every possible
event, we can easily determine the following probabilities:
=
{
2
,
3
,...,
12
}
Pr[
X
=2]=1
/
36
Pr[
X
=3]=2
/
36
Pr[
X
=4]=3
/
36
Pr[
X
=5]=4
/
36
Pr[
X
=6]=5
/
36
Pr[
X
=7]=6
/
36
The remaining probabilities (i.e., Pr[
X
=8
,...,
Pr[
X
= 12]) can be
computed by observing that Pr[
X
=
x
]=Pr[
X
=14
−
x
]. Consequently, we
have
Pr[
X
=8] = Pr[
X
=14
−
8] = Pr[
X
=6]=5
/
36
Pr[
X
=9] = Pr[
X
=14
−
9] = Pr[
X
=5]=4
/
36
3
In some literature, a random variable is defined as a function
X
:Ω
→
R
.