COS 341, September 22, 1997Handout Number 3
The Dating Problem and the Lottery Problem
Probability
A probability space 
is
a pair (A, p) where A is a finite set, and
is a function such that
. An event T is
a subset of A. The probability for T
to occur is defined as 
.
The notion of probability space is used to model a random process, in which A is the set of all possible configurations, and configuration a is the realized configuration with probability p(a). We restrict A to be a finite set for simplicity (in general A could be infinite). The notion of event models a boolean predicate that is of interest.
The Dating Problem
In the Dating Problem with parameters n,k, the probability
space is 
, where A is the set of
all permutations of 
, and
p(a)=1/|A| for all 
. It is easy to
see that a permutation 
is
in T if and only if the following conditions are satisfied:
C1: 
;
C2: Let 
where 
, then
the minimum of 
is
among the first k of these numbers.
Let 
denote the set of all a's satisfying C1, C2 with j
being the j in C2. Then T is the disjoint union of such .
By the Addition Principle, we have
We assert that for each ,
To see this, note that is itself the disjoint union of
, where 
consists
of 
with the minimum of 
occurring at 
. Now each element of can be
specified by first choosing an (n-j)-permuation of
(to fix 
),
and then a (j-2)-permutation of the set
minus its minimum element (to fix
). Therefore, by the
Multiplication Principle, we have
This proves (2). (Alternatively, one can argue that it is
equally likely for a random a with to have the
minimum of to occur at s for any
. Since there are (n-1)! a's with
,
the number of such permutations with the minimum occurring in
the first k locations is equal to 
.)
It follows from (1) and (2) that
Since |A|=n!, this means
This completes the analysis of the probability of success under the strategy used with parameters n,k.
For example, if n=8, k=4,
Lottery
We considered in class a simplified version of California Lottery.
Let 
. The probability space is ,
where A is the set of all 6-combinations of S, and p is
uniform on A (i.e., p(a)=1/|A| for all ).
Assume that you have picked a particular 6-combination
. When the lottery drawing is to be
done, the event T corresponding to your winning 5 dollars is
the set of all 6-combinations that intersects
in exactly three elements.
(If the intersection is larger than 3, you win more than 5
dollars.) What is p(T)?
Clearly, p(T)=|T|/|A|. As 
, we only need to calculate |T|. For each subset 
of size 3, let 
be the set of all 6-combinations of S
that have J as their intersection with I. Then by the Addition
Principle,
As each 
, we have
. Thus,
