1. Genesis of the Problem
There is a long tradition of setting unsolved problems on mathematics examina- tions. The most famous example is Stokes’s Theorem, a three-dimensional version of which appeared on the 1854 Smith’s Prize Exam at Cambridge Uni- versity [1] , several years before a proof was published by Hankel.
The following problem appeared on the final examination in the author’s course Mathematics 117, “Probability and Random Processes with Economic Applications,” in December 2016.
“The initial membership of a newly founded MGSO (mixed gender social organization) is three women and one man. At the start of week
(starting with week 0), there are
members, of whom
are male. A member is chosen at random, and he or she recruits a new member of the same gender as himself/herself.
Show that the fraction of the membership that is male, the random variable
is a martingale. State what property of this martingale guarantees that it converges almost surely, and describe the probability distribution for
.”
An equivalent problem was stated and solved by Eggenberger and Pólya in 1923 [2] . Instead of a consanguinity with male and female members, they considered an urn which initially, for the special case in the exam problem, contained
red balls and
(
for “Schwarz”) black balls. A ball was repeatedly chosen at random from the urn and then replaced, along with another ball of the same color.
Since the students had done examples based on Pólya’s urn and had studied the martingale convergence theorem, everything was straightforward except for “describe the probability distribution for
,” which the author of the exam question had not taken the trouble to work out!
This variant of Pólya’s urn is of political interest at Harvard because of sanctions against single-gender social organizations that have been proposed for the 2017-18 academic year [3] . An existing single-gender organization can presumably avoid the sanctions by adding a single member of the opposite gender, and the proposed model for expanding the membership is not unreasonable.
The term “consanguinity” for an MGSO whose name consists of Greek capital letters was suggested to the author by Prof. Richard Thomas of the Harvard Classics Department. Instead of saying “X is my fraternity brother” or “Y is my sorority sister,” one can say “Z is my consanguinity sibling.”
None of the nine students who took the exam correctly guessed the describe the probability distribution for
. Perhaps James Clerk Maxwell, who tied for first on the 1854 Smith’s Prize Exam, would have fared better.
Pólya’s urn has developed since 1923 into an entire branch of mathematics. It is the subject of a recent book [4] . An excellent online resource that contains most of the key results is [5] .
The rest of the paper is organized as follows. The well-known proof that the proportion of the membership
that is male is a convergent martingale is reviewed in Section 2 and is supplemented by a second martingale that involves
. In Section 3, the probability distribution for
is derived by an elemen- tary counting argument, and it is shown that for large
, the probability of adding
male members is proportional to
, consistent with the fact that a beta distribution with parameters 1 and 3 has the density function
. In Section 4, it is shown that the expected number of weeks before a second male member is added is infinite. In Section 5, the general case of starting with
male members and
female members is analyzed.
2. Martingale Analysis
We first specify the sample space
and probability measure for an experi- ment in which a consanguinity evolves for
weeks. An element
of this sample space is a sequence
where
specifies which of the four original members selects the member added in week 1,
specifies which of the five members present after week 1 selects the member added in week 2, and so forth. We specify not merely whether the new member added in week
is male or female, but also which existing member made the selection. Our probability model is then that each
is equally likely.
Let the random variable
denote the number of males in the cons- anguinity after
weeks.
is a function on the sample space, whose value for each element
can be determined by identifying the gender of each member who makes a selection. After
weeks the total membership is
. The ratio
is also a random variable, the proportion of the membership that is male after
members have been added.
We next review briefly the fundamentals of conditional expectation and martingales, a simplification of sections 8.2, 9.1 and 9.2 of the textbook used in Math117. [6]
Let
be a sample space, which in the case at hand is finite. Let
be an event (a subset of
), which in our case might be “after four weeks there are three male members.” Then the conditional expectation
is computed by restricting the sample space to the subset
and calculating expectation in the usual way for this restricted sample space.
The random variable
generates a finite partition of the sample space into events of the form
, i.e. “after
weeks, the consanguinity includes
male members.” Since these are the only events of interest to us, we need make no mention of sigma-fields and can use the simplified notation
Since the number of males
and the proportional of males
both generate the same partition of the sample space, “conditioning on
” and “conditioning on
” are equivalent.
This conditional expectation defines a new random variable as follows: given an element
of the sample space, we determine the value
, then compute the expectation of
using only those elements
that lead to that value.
We cite the three laws of conditional expectation, a simplified version of Proposition 8.8 from [6]
1) Taking out what is known (TOWIK):
If
is constant on each level set of
, then
(1)
2) Independence drops out (IDO):
If
is independent of
, then
(2)
3) Tower Law:
If
, then
(3)
The term “martingale” was in use by roulette players long before it found its way into mathematics. Imagine that you are playing roulette in a fair casino where there is no zero on the wheel. If after
plays you have
chips and bet one chip on red, you are equally likely to end up with
chips or
chips, for an expectation of
chips. If random variable
is the size of your stack of chips after
plays, then the sequence
has the martingale property
.
For a consanguinity, the number of male members
, which can never decrease, is not a martingale. However, even someone who is unfamiliar with the term “martingale” is likely to guess correctly that the average number of male members is going to remain one-fourth, for the simple reason that the probability of choosing a new male member is equal to the probability that the new member is selected by a male, which in turn is equal to the proportion of the membership that is male.
More formally, we need to prove that the sequence of random variables
has the martingale property: the expectation of
, conditioned on
, is equal to
, or
First we consider the case
. The random variable
has the constant value
. For
there are two possible values. With probability
, a new male member is selected, and the proportion of males rises to
. With probability
, a new female member is selected, and the proportion of males drops to
. The expectation of
is therefore
The general proof is scarcely more difficult. Introduce a new random variable
, the number of male members chosen in week
. This random variable has the value 1 with probability
, the value 0 with probability
.
Clearly
, and since expectation is linear,
For the first term, conditioning
on a function of itself changes nothing (TOWIK) (1). For the second term, the expectation of
is simply the probability that it equals 1 rather than 0, namely
, so
Dividing by
we find
which is the martingale property.
By the Tower Law(3), we can condition
first on
, then on
, and eventually on
and conclude that
(4)
reaching a conclusion that requires half a page of computation in [2] , page 281.
This analysis appears in almost every introduction to martingales; for example, as exercise 27 on page 258 of [7] . What appears not to be well known is that there is also a second-degree martingale that makes the computation of variance equally easy.
The inspiration for this second martingale is a symmetric random walk, as described, for example, in Example 9.6 of [6] .
Let
denote the
th step in the walk: it is a random variable that has values +1 and -1, each with probability 1/2.
Let
Then
By TOWIK (1),
By IDO (2),
and we conclude that
For a second-degree martingale, define a new random variable,
Then
Again condition on
.
By TOWIK(1),
By IDO (2),
Finally,
is the constant random variable 1.
So
which is the martingale property.
In the case of the consanguinity we can write
where
is the number of male members (0 or 1) added in week
. However, in this case
is no longer independent of
―indeed this lack of independence is precisely why Eggenberger and Pólya [2] found the urn problem interesting.
It took a bit of experimentation for the author to discover a second degree martingale even for the simple special case that appeared on the examination.
The martingale turns out to be
(5)
roof: consider
Since
This time it will be more difficult to deal with the second term, because
is not independent of
.
Again we condition everything on
. The key is that
By TOWIK (1),
By TOWIK (1),
Since
equals 0 or 1, its square is equal to itself, and
Combining all the terms we find
or
which establishes the martingale property for the random variable
(5).
By the Tower Law (3), therefore,
It follows that
But we already know (4) that
and so
Thus the variance is
(6)
in agreement with the value that Eggenberger and Pólya calculate from the probability mass function [2] .
The Martingale Convergence Theorem, stated and proved, for example, in section 9.2 of [6] , asserts that if a sequence of random variables like
is uniformly integrable, it converges almost surely to a random variable
. Since each
is bounded below by 0 and above by 1, the requirement of uniform integrability is trivially satisfied.
Although we have still not determined the probability mass function, we now know enough to determine the expectation and variance of
. Since
has
an expectation of
for all
, so does
. From the results that we have just
obtained, combined with the fact that
, it follows that
At this point we might conjecture an answer to the original exam question, “describe the probability distribution for
.” Perhaps the limit is a beta distribution with parameters
and
, for which the density function is
. Any book on mathematical statistics, e.g. [8] has the formulas for the expectation and variance of the beta distribution. The expecta- tion is
while the variance is
So the conjectured beta distribution has the right expectation and variance. Rather than attempt to compare higher moments, though, it will simpler just to work out the probability mass function and take its limit.
3. The Probability Mass Function
The following derivation is equivalent to that of Eggenberger and Pólya [2] , but it is strictly an elementary counting argument, making no mention of the fact that the number of males
is the sum of a set of random variables which, although not independent, are nonetheless “exchangeable.”
We have already identified a finite sample space whose elements all have equal probability. The number of elements in the sample space is the product of the number of equally likely choices that can be made in successive weeks: namely
Now we must count the number of elements of the sample space whose effect is to add
males and
females to the membership.
For the first male added there is only one candidate for the member who did the choosing; for the second male added, there are two candidates, and so forth. Given a fixed set of
weeks in which males are chosen, there are in all
alternatives. Similarly, for the weeks in which females are chosen, there are
alternatives for the female choosers.
There are
ways to select the set of
weeks in which a male is chosen. So the number of elements of the sample space that contribute to the event “
males are added” is
The probability of adding
males is simply the proportion of elements in the sample space that contribute to this event: namely
(7)
This formula agrees with Equation (6) of Eggenberger and Pólya [2] , where the authors multiply conditional probabilities, then permute the numerators of the fractions that are multiplied.
We now set
and take the limit as
by dropping all terms that approach 0, obtaining
which corresponds to the density function for the beta distribution with parameters 1 and 3,
(8)
4. Waiting for the Second Male Member
The probability that only females are added over a period of
weeks is simply the ratio
Suppose that the consanguinity agrees to pay a fine of 1 dollar for each week that its membership includes only one male. What is the expected amount of the fine?
Let
be the indicator function of the event “in the first
weeks, all new members are female.” The total fine is the random variable
For example, if the first male is added in week 3, the first two of these indicator functions equal 1, all the others are 0, and the fine is 2 dollars.
The expectation of the fine, by linearity of expectation, is
But the expectation of
is just the probability of the event that only females are added over a period of
weeks, so
This series is divergent, and the expected fine is infinite!
5. Martingales for General Starting Conditions
If the consanguinity begins with
members,
males and
females, the proportion of male members is still a martingale:
Furthermore, the second-degree martingale is the simplest imaginable generalization: 4 gets replaced by
.
(9)
We repeat the proof, considering
Since
Again we condition everything on
and use
By TOWIK (1),
By TOWIK (1),
Since
equals 0 or 1, its square is equal to itself, and
Combining all the terms we find
or
which establishes the martingale property for
(10).
With more than one initial male member, the calculation of variance becomes slightly more complicated, since
depends on the number of initial male members. By the Tower Law (3),
It follows that
But we already know that
and so
(10)
Thus the variance is
in agreement with the value that Eggenberger and Pólya [2] calculate from the probability mass function. Dividing by
and taking the limit as the limit as
, we find
which is indeed the variance for a beta distribution with parameters
.
6. Conclusions
The original examination question has been solved at last.
• The proportion of male members,
, is a martingale whose expectation is
(4) for all
.
• Being bounded below by 0 and above by 1, this martingale has a limit as
.
• Without working out the distribution function for
, a second martingale (5) can be used to show that the variance of the limiting distribution is
(6), which is consistent with the conjecture that this limiting distribution is a beta distribution.
• The distribution of the number of male members (7) can be determined by an elementary counting argument, and its limit is a beta distribution(8).
• The newly found second-degree martingale generalizes easily (10) to arbitrary starting conditions.
Acknowledgements
I thank the Editor and the referee for their comments. I also thank Dean Rakesh Khurana, who made me aware of the issue of fraternities and sororities at Harvard, my student Morgan Breitmeyer, with whom I had enlightening discussions about sororities on campus, and my student Rebecca Jarvis, who reads German and was able to confirm my interpretation, initially done with the aid of Google Translate, of Eggenberger and Pólya’s original article.