The reader is referred to [Wan96] for a comprehensive survey of the mathematical theory of average-case computational complexity. For convenience, we provide below some basic definitions and results.
We use the binary alphabet 
for encoding strings.
Denote by 
the length of a binary string 
.
Denote by 
the standard lexicographical order on 
.
A probability distribution
is a real-valued function from
to [0,1] such that 
.
We assume that on the empty string is always 
.
We may also use distribution, probability, weight,
or density to denote
probability distribution.
The distribution function of , denoted by 
, is
defined by
, where is
the standard lexicographical order on .
For a function 
, we use 
to denote 
for
and use 
to denote the inverse of .
We use the standard notations 
, 
, and 
(see, for example,
[CLR90]).