Transcript a n ) =0+…+ - s3.amazonaws.com

Lecture 14
Continuous sample space,
Special case of the law of
large numbers, and
Probability density function
K. Shum
A non-discrete sample space
• Sample space: I={x: 0 x <1}
0
1
• Probability function: For an event E, e.g. an
interval within the sample space, then P(E)
= length of E.
– Example P(0.2 x <0.5) = 0.3.
K. Shum
Probability of one point
• Given a point a in the sample space I, e.g. 1/5, 2/7, 1/,
whatever, if we randomly and uniformly pick a real
number in I, the probability that it is equal to a is zero.
0
1
a

– This fact can be interpreted in terms of precision. A
randomly chosen point  is equal to a predetermined
value a if they are equal with precision of infinitely
many decimal places.
• P( equals a to the 1st decimal place) = P((a-0.05,a+0.05)) = 0.1.
• P( equals a to the 2nd decimal place) = P((a-0.005,a+0.005)) =
0.01.
• …..
K. Shum
Probability of two points
• So for a fixed value of a, we say that with
probability zero, we drawn number is equal
to a, or P(a) = 0.
• For the same reason, if we fix two values a1
and a2 before we draw any number, the
random number we will draw is equal to a1
or a2 with probability zero.
– P(a1 or a2) = 0.
K. Shum
Probability of n points
• Let a1,…,an, be n points in the sample space
I. Pick a random point  in I.
P ( = a1 or…or an) = 0.
– Reason: Third axiom of probability.
P ( = a1 or…or an) = P ( = a1)+…+ P ( = an)
=0+…+0 = 0.
K. Shum
Probability of countably infinite
number of points
• A set S is “countably infinite” means
– mathematically, there is a bijection between S
and the natural numbers.
– data-structure-ly, S can be stored in an infinitely
long link list.
• If S is an event that is countably infinite,
then P(S)=0. If we randomly draw a point,
it belongs to S with probability zero.
K. Shum
Example of countably infinite set
• Set of rational number in I whose
denominator is a power of 2.
• Set of rational numbers in I.
• Subset of a countably infinite set.
• Union of a countably infinite set and a finite
set.
• Union of two countably infinite sets.
K. Shum
Non-examples
• {0 x <1}
– Cantor’s diagonal argument.
• {0 x <1}-{a1,…, an}, the complement of a
finite set in I.
• Complement of a countably infinite set in I.
K. Shum
Probability zero, probability one
• We see that a non-empty event may have
probability zero. Even an event with infinite
cardinality may have probability zero.
• We say that an event happens with
probability one if the complement is an
event with probability zero.
– For example, with probability one, a randomly
drawn number in I is irrational.
K. Shum
Binary expansion
• In Matlab, to display a number, say 1/2, in binary,
you can type “dec2bin(1/sqrt(2)*2^60,60)”.
• Every numbers in I gives rise to an infinitely long
binary expansion.
• Thus the sample space I is a probability model for
tossing infinitely many coins, by mapping 1 to T
and 0 to H.
• The tosses are independent with P(T)=P(H)=0.5.
K. Shum
An ambiguity with probability 0
• The numbers 0.12, 0.012, 0112, etc. have two
different binary expansions.
• There are two expansions for the same number if
it is a rational number with denominator a power
of 2. The mapping from these numbers to bit
sequence is not well-defined.
• So, we use the convention that we choose the one
with terminating zeros.
• Anyway, this happens with probability zero and
we don’t really care about this small difficulty.
K. Shum
Is the numbers of 1’s and 0’s
asymptotically equal?
• For  between 0 and 1, define
n
S ( , n)   ( k th bit of  )
k 1
• We ask whether the partial sum divided by n is
equal to 0.5 asymptotically:
lim n S ( , n) / n  0.5 ?
• A number satisfying the above equation is called
normal in base 2.
K. Shum
Graphes of S(,n)/n
• In Matlab,
– dec2bin(0.123*2^50,50) is the first 50 bits of
0.123 in string format.
– dec2bin(0.123*2^50,50)-48 is the first 50 bits
of 0.123 in vector format.
– cumsum(dec2bin(0.123*2^50,50)-48) is the
cumulative sum, namely, S(,n)/n.
– plot(cumsum(dec2bin(0.123*2^50,50)48)./(1:50)) gives you the graph of S(,n)/n.
K. Shum
There are infinitely many
numbers that are not normal
•
•
•
•
3/7 = 0.011011011011011011011011… 2.
7/15 = 0.011101110111011101110111… 2.
15/31= 0.01111011110111101111… 2.
…
K. Shum
Is there any normal numbers?
• We cannot show this by Matlab.
– Limited precision.
– Limited life. Even if there is an ideal computer
with infinite precision, we cannot check the
limit of an infinite sequence of 0 and 1.
• We can prove that normal numbers exist.
K. Shum
Emile Borel’s normal number
theorem (1909)
• Borel’s theorem in fact not only shows that
normal numbers exist, it also proves that
they exist in abundance.
– Theorem of normal number: If we pick a real
number uniformly between 0 and 1, then it is a
normal number with probability 1:
P(normal numbers) = 1.
• This is a special case of the strong law of
large number.
K. Shum
Relation to random walk
• In the binary expansion, if we substitute 0
by –1, we get a one-dimensional random
walk.
• In matlab,
2*(dec2bin(0.123*2^50,50)-48)-1 are the first 50
steps of a random walk corresponding to 0.123.
plot(cumsum(2*(dec2bin(0.123*2^50,50)-48)-1))
is the graph of the random walk.
K. Shum
How to predict the histogram?
• Two parameters
– Number of samples
– Bin width
• Height of a bin is directly proportional to
– Number of samples
– Bin width
K. Shum
Six examples
•
•
•
•
•
•
Uniform between 0 and 1
Uniform between 0 and 2
Sum of two (uniform between 0 and 1)
Square root of a uniform between 0 and 1
Square of a uniform between 0 and 1
-loge (uniform between 0 and 1)
K. Shum
Probability density function
• Definition:
– Non-negative function defined on the real line.
– Area under the curve is equal to one.
• Histogram of samples will be approximated
by (No. of samples) * (bin width) * pdf.
K. Shum