Applied Mathematics
Vol.08 No.04(2017), Article ID:75858,12 pages
10.4236/am.2017.84044

On the Evolution of Consanguinities

Paul G. Bamberg

Department of Mathematics, Harvard University, Cambridge, Massachusetts, USA

Copyright © 2017 by author and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: January 29, 2017; Accepted: April 27, 2017; Published: April 30, 2017

ABSTRACT

“Consanguinity” is a gender-neutral term for “fraternity” or “sorority.” Initially a consanguinity includes M male members and F female members. Each week a member, chosen at random, selects a new member, always of the same gender as the member making the selection. This model for evolution is isomorphic to the classic Pólya’s urn. The male and female members play the same roles as the red and black balls in the urn, and the procedure for selecting a new member is equivalent to drawing a ball from the urn, then replacing it and adding a new ball of the same color. It is well known that for Pólya’s urn, the proportion of red balls in the urn is a martingale. It follows that for a consanguinity, the proportion of the membership that is male is a martingale. Furthermore, being bounded, this martingale converges to a limit. For a martingale that is the sum of independent random variables, such as a symmetric random walk, there is also a well-known second-degree martingale from which the variance of the limiting distribution can be deduced. What the author discovered, in the process of solving his own examination problem, is that a similar martingale exists also for Pólya’s urn, even though in this case the number of red balls is the sum of random variables that are not independent. This new martingale can be used to calculate the variance of the limiting distribution. Traditionally, the probability that r red balls will be drawn from Pólya’s urn in n trials is derived by a rather tricky argument involving conditional probability. This article uses an obvious but overlooked simpler approach. Pólya’s formula for the probability that m male members will be chosen in n weeks is derived, without any mention of conditional probability, by an elementary counting argument, and its limit is shown to be a beta distribution.

Keywords:

Pólya’s Urn, Martingale, Martingale Convergence, Beta Distribution

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 n (starting with week 0), there are n + 4 members, of whom M n 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

μ n = M n n + 4 ,

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 R = 1 red balls and S = 3 ( S 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 μ n that is male is a convergent martingale is reviewed in Section 2 and is supplemented by a second martingale that involves M n 2 . In Section 3, the probability distribution for M n is derived by an elemen- tary counting argument, and it is shown that for large n , the probability of adding m male members is proportional to ( 1 m / n ) 2 , consistent with the fact that a beta distribution with parameters 1 and 3 has the density function 3 ( 1 x ) 2 . 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 M male members and F 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 n weeks. An element ω of this sample space is a sequence ( ω 1 , ω 2 , , ω n ) where ω 1 specifies which of the four original members selects the member added in week 1, ω 2 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 i 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 M n denote the number of males in the cons- anguinity after n weeks. M n 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 n weeks the total membership is n + 4 . The ratio

μ n = M n n + 4

is also a random variable, the proportion of the membership that is male after n 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 A be an event (a subset of Ω ), which in our case might be “after four weeks there are three male members.” Then the conditional expectation E [ X | A ] is computed by restricting the sample space to the subset A and calculating expectation in the usual way for this restricted sample space.

The random variable M n generates a finite partition of the sample space into events of the form M n = k , i.e. “after n weeks, the consanguinity includes k 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

E [ X | M n ] ( ω ) .

Since the number of males M n and the proportional of males μ n both generate the same partition of the sample space, “conditioning on M n ” and “conditioning on μ n ” are equivalent.

This conditional expectation defines a new random variable as follows: given an element ω of the sample space, we determine the value M n ( ω ) , then compute the expectation of X 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 X is constant on each level set of μ n , then

E [ X Y | μ n ] = X E [ Y | μ n ] (1)

2) Independence drops out (IDO):

If X is independent of μ n , then

E [ X | μ n ] = E [ X ] (2)

3) Tower Law:

If m < n , then

E [ E [ X | μ n ] | μ m ] = E [ X | μ m ] (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 n plays you have k chips and bet one chip on red, you are equally likely to end up with k + 1 chips or k 1 chips, for an expectation of k chips. If random variable Y n is the size of your stack of chips after n plays, then the sequence Y n has the martingale property E [ Y n + 1 | Y n ] = Y n .

For a consanguinity, the number of male members M n , 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 μ n has the martingale property: the expectation of μ n + 1 , conditioned on μ n , is equal to μ n , or

E [ μ n + 1 | μ n ] = μ n .

First we consider the case n = 0 . The random variable μ 0 has the constant value 1 4 . For μ 1 there are two possible values. With probability 1 4 , a new male member is selected, and the proportion of males rises to 2 5 . With probability 3 4 , a new female member is selected, and the proportion of males drops to 1 5 . The expectation of μ 1 is therefore

( 1 4 ) ( 2 5 ) + ( 3 4 ) ( 1 5 ) = 2 + 3 20 = 1 4 .

The general proof is scarcely more difficult. Introduce a new random variable X n , the number of male members chosen in week n . This random variable has the value 1 with probability μ n , the value 0 with probability 1 μ n .

Clearly M n + 1 = M n + X n , and since expectation is linear,

E [ M n + 1 | μ n ] = E [ M n | μ n ] + E [ X n | μ n ]

For the first term, conditioning M n on a function of itself changes nothing (TOWIK) (1). For the second term, the expectation of X n is simply the probability that it equals 1 rather than 0, namely μ n , so

E [ M n + 1 | μ n ] = M n + μ n = ( n + 4 ) μ n + μ n

Dividing by n + 5 we find

E [ μ n + 1 | μ n ] = μ n ,

which is the martingale property.

By the Tower Law(3), we can condition μ n + 1 first on μ n , then on μ n 1 , and eventually on μ 0 and conclude that

E [ μ n + 1 | μ 0 ] = μ 0 = 1 4 , (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 X i denote the i th step in the walk: it is a random variable that has values +1 and -1, each with probability 1/2.

Let

Y n = i = 1 n X i .

Then

E [ Y n + 1 | Y n ] = E [ ( Y n + X n + 1 ) | Y n ] = E [ Y n | Y n ] + E [ X n + 1 | Y n ] .

By TOWIK (1),

E [ Y n | Y n ] = Y n .

By IDO (2),

E [ X n + 1 | Y n ] = E [ X n + 1 ] = 0 ,

and we conclude that

E [ Y n + 1 | Y n ] = Y n .

For a second-degree martingale, define a new random variable, Z n = Y n 2 n

Then

Z n + 1 2 = ( Y n + X n + 1 ) 2 ( n + 1 ) = Y n 2 + 2 Y n X n + 1 + X n + 1 2 n 1.

Again condition on Y n .

By TOWIK(1),

E [ Y n 2 | Y n ] = Y n 2 .

By IDO (2),

E [ X n + 1 Y n | Y n ] = E [ X n + 1 | Y n ] = 0.

Finally, X n + 1 2 is the constant random variable 1.

So

E [ Z n + 1 | Y n ] = Y n 2 + 1 n 1 = Z n ,

which is the martingale property.

In the case of the consanguinity we can write

M n = M 0 + i = 1 n X i ,

where X i is the number of male members (0 or 1) added in week i . However, in this case X n + 1 is no longer independent of M n ―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

Z n = 1 ( n + 4 ) ( n + 5 ) ( M n 2 + M n ) (5)

roof: consider

Z n + 1 = 1 ( n + 5 ) ( n + 6 ) ( M n + 1 2 + M n + 1 )

Since

M n + 1 = M n + X n + 1 ,

Z n + 1 = 1 ( n + 5 ) ( n + 6 ) [ M n 2 + 2 M n X n + 1 + X n + 1 2 + M n + X n + 1 ] .

This time it will be more difficult to deal with the second term, because X n + 1 is not independent of M n .

Again we condition everything on M n . The key is that

E [ X n + 1 | M n ] = μ n = M n n + 4 .

By TOWIK (1),

E [ M n 2 | M n ] = M n 2 .

By TOWIK (1),

E [ M n X n + 1 | M n ] = M n E [ X n + 1 | M n ] = M n μ n = M n 2 n + 4 .

Since X n + 1 equals 0 or 1, its square is equal to itself, and

E [ X n + 1 2 | M n ] = E [ X n + 1 | M n ] = μ n = M n n + 4 .

Combining all the terms we find

E [ Z n + 1 | M n ] = 1 ( n + 5 ) ( n + 6 ) ( M n 2 ( 1 + 2 n + 4 ) + M n ( 1 + 2 n + 4 ) )

or

E [ Z n + 1 | M n ] = 1 ( n + 5 ) ( n + 6 ) n + 6 n + 4 ( M n 2 + M n ) = Z n ,

which establishes the martingale property for the random variable Z n (5).

By the Tower Law (3), therefore,

E [ Z n ] = E [ Z n | M 0 ] = Z 0 = 1 20 ( 1 + 1 ) = 1 10

It follows that

1 ( n + 4 ) ( n + 5 ) ( E [ M n 2 ] + E [ M n ] ) = 1 10

But we already know (4) that

E [ M n ] = n + 4 4

and so

E [ M n 2 ] = ( n + 4 ) ( n + 5 ) 10 n + 4 4 .

Thus the variance is

Var M n = E [ M n 2 ] E [ M n ] 2 = 3 n ( n + 4 ) 80 , (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 μ n is uniformly integrable, it converges almost surely to a random variable μ . Since each μ n 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 μ n has

an expectation of 1 4 for all n , so does μ . From the results that we have just

obtained, combined with the fact that μ n = M n n + 4 , it follows that

Var μ = lim n 3 n 80 ( n + 4 ) = 3 80

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 α = 1 and β = 3 , for which the density function is f ( x ) = 3 ( 1 x ) 2 . Any book on mathematical statistics, e.g. [8] has the formulas for the expectation and variance of the beta distribution. The expecta- tion is

α α + β = 1 4

while the variance is

α β ( α + β ) 2 ( α + β + 1 ) = 3 80 .

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 M n 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

4 × 5 × 6 ( 3 + n ) = ( n + 3 ) ! 3 ! .

Now we must count the number of elements of the sample space whose effect is to add m males and f = n m 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 m weeks in which males are chosen, there are in all ( m 1 ) ! alternatives. Similarly, for the weeks in which females are chosen, there are 3 × 4 × 5 ( 2 + f ) alternatives for the female choosers.

There are ( n m ) ways to select the set of m weeks in which a male is chosen. So the number of elements of the sample space that contribute to the event “ m males are added” is

( n m ) ( m 1 ) ! ( f + 2 ) ! 2 !

The probability of adding m males is simply the proportion of elements in the sample space that contribute to this event: namely

n ! m ! ( n m ) ! ( m 1 ) ! ( n m + 2 ) ! 2 ! ( n + 3 ) ! 3 ! = 3 ( n m ) ( n m 1 ) n ( n + 1 ) ( n + 2 ) = 3 ( 1 m n ) ( 1 m n 1 n ) n ( 1 + 1 n ) ( 1 + 2 n ) . (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 m n = x and take the limit as n by dropping all terms that approach 0, obtaining

( μ = x ) = 3 n ( 1 x ) 2

which corresponds to the density function for the beta distribution with parameters 1 and 3,

f ( x ) = 3 ( 1 x ) 2 . (8)

4. Waiting for the Second Male Member

The probability that only females are added over a period of n weeks is simply the ratio

3 × 4 × 5 ( 2 + n ) 4 × 5 × 6 ( 3 + n ) = 3 n + 3 .

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 1 n be the indicator function of the event “in the first n weeks, all new members are female.” The total fine is the random variable

F = 1 1 + 1 2 + 1 3 + .

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

E [ F ] = E [ 1 1 ] + E [ 1 2 ] + E [ 1 3 ] + .

But the expectation of 1 n is just the probability of the event that only females are added over a period of n weeks, so

E [ F ] = n = 1 3 n + 3

This series is divergent, and the expected fine is infinite!

5. Martingales for General Starting Conditions

If the consanguinity begins with N members, M males and F females, the proportion of male members is still a martingale:

μ n = M n n + N

Furthermore, the second-degree martingale is the simplest imaginable generalization: 4 gets replaced by N .

Z n = 1 ( n + N ) ( n + N + 1 ) ( M n 2 + M n ) (9)

We repeat the proof, considering

Z n + 1 = 1 ( n + N + 1 ) ( n + N + 2 ) ( M n + 1 2 + M n + 1 )

Since

M n + 1 = M n + X n + 1 ,

Z n + 1 = 1 ( n + N + 1 ) ( n + M + 2 ) [ M n 2 + 2 M n X n + 1 + X n + 1 2 + M n + X n + 1 ] .

Again we condition everything on M n and use

E [ X n + 1 | M n ] = μ n = M n n + N .

By TOWIK (1),

E [ M n 2 | M n ] = M n 2 .

By TOWIK (1),

E [ M n X n + 1 | M n ] = M n E [ X n + 1 | M n ] = M n μ n = M n 2 n + N .

Since X n + 1 equals 0 or 1, its square is equal to itself, and

E [ X n + 1 2 | M n ] = E [ X n + 1 | M n ] = μ n = M n n + N .

Combining all the terms we find

E [ Z n + 1 | M n ] = 1 ( n + N + 1 ) ( n + N + 2 ) ( M n 2 ( 1 + 2 n + N ) + M n ( 1 + 2 n + N ) )

or

E [ Z n + 1 | M n ] = 1 ( n + N + 1 ) ( n + N + 2 ) n + N + 2 n + N ( M n 2 + M n ) = Z n ,

which establishes the martingale property for Z n (10).

With more than one initial male member, the calculation of variance becomes slightly more complicated, since Z 0 depends on the number of initial male members. By the Tower Law (3),

E [ Z n ] = E [ Z n | M 0 ] = Z 0 = 1 N ( N + 1 ) ( M 2 + M ) = M ( M + 1 ) N ( N + 1 )

It follows that

1 ( n + N ) ( n + N + 1 ) ( E [ M n 2 ] + E [ M n ] ) = M ( M + 1 ) N ( N + 1 )

But we already know that

E [ M n ] = ( n + N ) M N

and so

E [ M n 2 ] = ( n + N ) ( n + N + 1 ) M ( M + 1 ) N ( N + 1 ) ( n + N ) M N = ( n + N ) M N n ( M + 1 ) + M ( N + 1 ) N + 1 . (10)

Thus the variance is

Var M n = E [ M n 2 ] E [ M n ] 2 = ( N M ) n M ( n + N ) N 2 ( N + 1 ) .

in agreement with the value that Eggenberger and Pólya [2] calculate from the probability mass function. Dividing by n + N and taking the limit as the limit as n , we find

Var μ = ( N M ) M N 2 ( N + 1 ) ,

which is indeed the variance for a beta distribution with parameters α = M , β = F = N M .

6. Conclusions

The original examination question has been solved at last.

• The proportion of male members, μ n , is a martingale whose expectation is E ( μ n ) = 1 / 4 (4) for all n .

• Being bounded below by 0 and above by 1, this martingale has a limit as n .

• Without working out the distribution function for μ n , a second martingale (5) can be used to show that the variance of the limiting distribution is Var μ = 3 / 80 (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.

Cite this paper

Bamberg, P.G. (2017) On the Evolution of Consanguinities. Applied Mathematics, 8, 550-561. https://doi.org/10.4236/am.2017.84044

References

  1. 1. From 1854: Smith’s Prize Exam. http://www.clerkmaxwellfoundation.org/SmithsPrizeExam_Stokes.pdf.

  2. 2. Eggenberger, F. and Pólya, G. (1923) über die Statistik verketteter Vorgange. Z. Angew. Math. Mech., 3, 279-289. https://doi.org/10.1002/zamm.19230030407

  3. 3. Letter on Single-Gender Social Organizations (2016) Cambridge, Mass. http://www.harvard.edu/president/news/2016/letter-on-single-gender-social-organizations.

  4. 4. Mahmoud, H. (2008) Polya Urn Models. Chapman and Hall/CRC. https://doi.org/10.1201/9781420059847

  5. 5. Polya’s Urn Process. http://www.math.uah.edu/stat/urn/Polya.html.

  6. 6. Dineen, S. (2013) Probability Theory in Finance. Graduate Studies in Mathematics, 70, 305p.

  7. 7. Grimmett, G. and Stirzaker, D. (2011) Probability and Random Processes. Oxford University Press, New York.

  8. 8. Chirara, L. and Hesterberg, T. (2011) Mathematical Statistics with Resampling and R. Wiley, Hoboken, New Jersey.