Conference rusure::math

    I think you need more information.
    
    It is not enough to know the expected number of sons per father. You
    need to know something about the distribution of the different possible
    numbers of sons.
    
    For example if every father always had exactly one son then no surname
    would ever become extinct. If all fathers had 0 sons, except for one
    father who had all the sons needed for the next generation, then there
    would be only one surname. It may be sufficient to know the probability
    of a father having no sons.
    
    One of your questions can be answered. Assuming that there is a
    non-zero probability that a father will have no sons then after
    sufficient generations there will be only one surname. I think the
    probability of that surname being Robinson is R/P (where P is the size
    of the male population).
    
    Andrew

        You also have to assume that Mr. Robinson will eventually
        die if you want his surname to become extinct.
        
        Dan

    Re .2:
    
    And I'd like to point out that it is not a good assumption that Mr.
    Robinson will eventually die, since emperical data does not completely
    support it.  Estimates are that more than 2% of all people (homo
    sapiens) who have ever lived past infancy have not died.  Possibly as
    many 10 to 12% have never died.  True fact!  :-)
    
    
    				-- edp

    Re:                      <<< Note 1440.1 by PRFECT::PALKA >>>

>    It is not enough to know the expected number of sons per father. You
>    need to know something about the distribution of the different possible
>    numbers of sons.
    
    You are right, more or less.  I do need the fact that there is a
    non-zero probability that a father will have no sons.
    
>    It may be sufficient to know the probability
>    of a father having no sons.
    
    Not quite.  I really need a distribution, but there is a distribution
    implicit in .0, and I will show a way to get it out.
    
>    One of your questions can be answered. Assuming that there is a
>    non-zero probability that a father will have no sons then after
>    sufficient generations there will be only one surname. I think the
>    probability of that surname being Robinson is R/P (where P is the size
>    of the male population).
    
    Strangely enough, this is false.  Given the non-zero probability above,
    there is a non-zero probability of a generation with no sons.  So all
    surnames will become extinct in the long run, in this ideal community.
    In the real world, immigration, marriage between generations and
    correlations between number of sons and males in the community would
    solve the problem.
    
    re .2 and .3:  gimme a break!
    
    Andrew

    

    Define the random variable X as the number of sons a man has.  Define
    pk as the probability that X=k, or the probability that a man has k
    sons.  As stated in .1, the problem is uninteresting unless p0 > 0, so
    we will assume that.
    
    Feller quotes an empirical study showing that for America, pk is given
    by
    
    	p0 = 0.4825
    
    	pk = 0.2126 * 0.5893^(k-1) for k>0
    
    
    This might do for some studies, but it does not immediately apply to
    either of the communities in .0: the ideal community or humanity for
    the last 500,000 years.
    
    The question is, can we find a distribution implicit in .0?  The answer
    is yes, although our method will raise an eyebrow in many statistical
    gatherings, and would cause apoplexy in as dedicated a frequentist as
    Mr. Feller.
    
    We seek a distribution pk, defined on k=0,1,2..., with the usual
    normalizing constraint and an additional constraint that the mean is
    known:
    
    	SUM ( pk ) = 1
    
    	SUM ( k*pk ) = m
    
    We have no other information, so we want a distribution which contains
    no other information.  That is, we want a distribution which contains
    minimal information, subject to the constraints above.  The information
    content of a distribution is proportional to pk * ln pk, according to
    Mr. Boltzmann, so we want an extremum of the function
    
    	SUM ( pk * ln pk )
    
    subject to the constraints above.  The method of Lagrange Multipliers
    tells us we want an extremum of the function
    
    	SUM (pk * ln pk ) + A * ( SUM ( pk ) - 1 ) + B * ( SUM ( k*pk) -m )
    
    Differentiating by everything in sight tells us that the extremum can
    be found at 
    
    	ln pk = A + k*B + 1
    
    or
    
    	pk = exp(A+1) * exp(B)^k
    
    This is a geometric distribution, so we have found that a geometric
    distribution satisfies the constraints in .0 with the minimal
    additional information.  Note that the empirical distribution above is
    geometrical except for the p0 term.
    
    The method above is sometimes used by Bayesian statisticians to derive
    prior distributions with minimal information.  I would prefer real data
    from our paleolithic ancestors, but that is not available.  Maybe some
    reader knows some pk for modern hunter-gatherer cultures.

    Now we'll ignore the digression in .5, and solve the problem for a
    general distribution.  This is following the method of Feller.
    
    Define the random variable X as the number of sons a man has.  Define
    pk as the probability that X=k, or the probability that a man has k
    sons.  As stated in .1, the problem is uninteresting unless p0 > 0, so
    we will assume that.
    
    Define the generating function for the sequence {pk} = {p0, p1, ...}
    as
    
    	P(s) = p0 + p1 * s + p2 * s^2 ... 
    
    Note that the mean or expectation of the random variable X is given by
    the derivative of the generating function
    
    	E(X) = P'(1) = m
    
    Let Xn be a random variable describing the number of male descendants
    of a man in generation n.  Assume X0=1; then X1=X.  Then X2 is a sum of
    X1 distributions, each having the generating function given above. 
    Feller earlier proved that the generating function of a sum of random
    variables is a compound function so the generating function of X2 is
    
    	P(2;s) = P( P(s) )
    
    In general, we can define the generating function for Xn recursively:
    
    	P(1;s) = P(s)	 	P(n+1;s) = P( P(n;s) )
    
    
    We seek the probability of extinction at or before generation n, which
    is given by the probability that Xn is zero, or P(n;0).
    
    Feller then proves a number of mathematical details to show that
    P(n;0), the result of the recursion, converges to the smallest root of
    the equation
    
    	z = P(z)
    
    He also shows that if the mean is less than or equal to 1, then the
    lowest root is 1.  If the mean is greater than one, then the lowest
    root is z, given by the equation above.
    
    This gives us an answer to one question in .0: if the population is
    stable, then the mean is 1, and every surname becomes extinct with
    probability 1, that is, with certainty.  Of course, this does
    contradict our assumption that the population is stable, but that is
    just a detail.
    
    If the population is growing, however slowly, the root z above will be
    less than one, so the probability of extinction will be given by z. 
    
    If there are R bearers of the surname, each of their lines must become
    extinct for the surname to become extinct, so the probability of
    extinction of the surname is given by
    
    	P( extinction ) = z^r
    
    We can also show that the expected number of of one man's male
    descendants in generation n is given by
    
    	E(Xn) = m^n
    
    If the population is growing, the expected number of male descendants
    grows without bound.
    
    "It is easily seen", quoting Feller, that not only P(n;0) approaches z,
    but P(n;s) approaches z for 0<s<1.  This means that all coefficients of
    s, s^2, ... all approach zero.  "After a large number of generations
    the probability that no descendants exist is near z, and the
    probability that the number of descendants exceeds any preassigned
    bound is near 1-z; it is exceedingly improbable to find a moderate
    number of descendants."
    
    This is as far as Feller takes it for an arbitrary distribution.  If we
    assume a distribution, we can get more information, but I'll save that
    for another reply.

    We can show one more interesting view of the general distribution, by
    combining the previous information:
    
.6>    	P(1;s) = P(s)	 	P(n+1;s) = P( P(n;s) )
        
>    We seek the probability of extinction at or before generation n, which
>    is given by the probability that Xn is zero, or P(n;0).
    
    to give an iteration for extinction probability in generation n
    
    	P(1;0) = P(0)	 	P(n+1;0) = P( P(n;0) )
    
    If you graph this iteration, you see a pretty stair-step up and to the
    right from (0,0).  It steps up the slice between the two curves defined
    by
    
    	y = s
    
    	y = P(s)
    
    These two curves always intersect at (1,1).  When the mean is greater
    than one, they also intersect somewhere between (0,0) and (1,1)

    Now let's put some numbers into the general result of .6, using a
    geometric distribution.  If you don't like the reasoning in .5, you can
    consider this as no more than an example.
    
    The geometric distribution is defined in general by
    
    	pk = p * q^k 	where q=1-p and k=0,1,2,...
    
    It has the mean
    
    	m = q/p
    
    and generating function
    
    	P(s) = p/(1-qs)
    
    
    For a growing population, the iteration in .6 has a limit at
    
    	z = P(z) = p/(1-qz)
    
    This is a quadratic equation which has the obvious solutions
    
    	z = 1		z = p/q
    
    (Well, obvious to you, maybe.  I had to solve the quadratic and
    simplify the result.)
    
    The second solution is the interesting one.  It says that the
    probability of extinction in a growing population is 
    
    	z = p/q = 1/m
    
    For a population doubling every generation, z = 1/2.  So it takes a lot
    of population increase to avoid the extinction.
    
    
    For a population stable in the sense that m = 1, p = q = 1/2, so we
    must iterate
    
    	P(s) = 1 / ( 2 - s )
    
    This leads to a nice continued fraction
    
    	P(n;0) = 1 / ( 2 - ( 1 / ( 2 - ( ... ))))
    
    which I cannot figure out.  But looking at several specific cases, I
    get
    
    	P(1;0) = 1/2
    	P(2;0) = 2/3
    	p(3;0) = 3/4
    	...
    
    from which I guess
    
    	p(n;0) = n/(n+1) = 1 - 1/(n+1)
    
    (Can anybody prove this or solve the more general form below?)
    
    If a surname has R representatives in generation 0, all must become
    extinct.  For the interesting case where n >> r and n >> 1, we can
    approximate
    
    	P(extinction) = (1 - 1/(n+2))^R ~~ 1 - R/n
    
    So the probability that a surname survives for n generations in a
    stable population is just R/n.
    
    If we use this as a model of paleolithic humanity, we can find the 
    probability of extinction for any particular line of mitochondrial DNA.
    Using the estimate of 200,000 years, and 20 years/generation, we can
    estimate the probability of survival of the maternal line of any
    female living at that time as
    
    	P(survival) = 1/n = 1/10,000
    
    If there were around 1,000 females of Homo Sapiens Sapiens around then,
    it is likely only one line would survive.  If that subspecies mixed
    with a small (<1,000) number of other Homo Sapiens, it is likely that
    those lines would survive.  Thus we can conclude from the observed
    uniformity of mitochondrial DNA and our assumed model:
    
    	all of modern man is descended from a fairly small population
    	of Homo Sapiens Sapiens
    
    	this population did not mix extensively with other populations
    	of Homo Sapiens
    
    We cannot conclude from this that
    
    	all of modern man is descended from a single female
    
    	there was no mixing with other populations
    
    
    	
    As an example of a declining population, we may take
    
    	m = 1/2		q = 1/3		p = 2/3
    
    	P(s) = 2 / ( 3 - s )
    
    This gives another nice continued fraction which I cannot evaluate at
    all.  Falling back into calculator mode shows
    
    	P(1;0) = 0.6667
    	P(2;0) = 0.8571
    	P(3;0) = 0.9333
    	P(4;0) = 0.9677
    	...
    
    This is approaching unity much faster, from which I conclude that
    periods of declining population are much more effective at causing
    extinctions.  I suspect that human population growth rates have been
    far from the average, both in time and in space.  I also suspect that
    when we average over time and space, the declining populations will
    contribute disproportionately to extinctions.  This latter suspicion
    could probably be confirmed by simulation, or perhaps even
    analytically.
    
    So the numbers given above for a stable population are probably an
    underestimate of the size of the small population and the amount of
    mixing allowed in this model.

re .8

>    	P(s) = 1 / ( 2 - s )   
>    from which I guess
>    	p(n;0) = n/(n+1) = 1 - 1/(n+1)
>    
>    (Can anybody prove this or solve the more general form below?)

    Just use mathematical induction to prove your guess.
    
>    	P(s) = 2 / ( 3 - s )

              n+1
             2    - 2
    p(n;0) = --------
              n+1
             2    - 1

    also provable using M.I.


    No, I haven't manage to solve the recurrence for general p.

re .9 (me)
    
>No, I haven't manage to solve the recurrence for general p.
    
Define r = p/(1-p)

For p <> 1/2, so r <> 1

                r - 1
P(n;0) = 1 - -----------
             r^(n+1) - 1