Conference rusure::math

>>My daughter mentioned that her Secret Santa was someone she knew well out of a
>>group of 47 people.  She later found out that individual had drew her name. 
>>Since she only knew 5 other people in the group she found that rather
>>remarkable.  We calculated the probability of that and found it to be about one
>>quarter a percent - fairly unlikely!
        
        It isn't clear here what probability you were
        calculating.  If she knows 5 people (not counting
        herself) out of 47 people (including herself), then the
        probability of one of those five drawing her name is 5/46
        or 10.9%.  The probability of the one she knows best
        drawing her name is 1/46 or 2.2%.
        
>>We tried to generalize the problem to determine how likely it was that there
>>      .
>>      .
>>      .
>>What I would like to compute is the probability that after all
>>names are picked that no one will be giving a gift to the person who they will
>>be getting a gift from.
        
        How does that generalize the problem of the probability
        of getting a gift from someone that you know?
        
        Dan

    re .1
    
    The 1/4% that I mentioned was the result of both happening, i.e.
    
    	(5/46)*(1/46)=.0024
    
    My note was a bit confusing.  We weren't trying to generalize the
    problem of knowing a given number in the group.  Rather we were
    interested in the probability of a "Secret Santa" where no one in the
    group gave a gift to the SAME person they received a gift from.
    
    I still don't know how to set that up from an arbitrary number of
    people in the group.
    
    Thanks,
    
    Bob

        In 20,000 random trials for each of five different
        numbers of people, there was at least one "pairing" in
        just under 40% of the trials.
        
        	       how many had
        	n     pairs / out of    %
        	--      ----------      --
        	10	7728/20000	39%
        	20	7776/20000	39%
        	30	7912/20000	40%
        	40	7795/20000	39%
        	50	7932/20000	40%
        
        Interesting numbers ... 7776 is 6^5 ... all five
        percentages round up when rounded as shown.
        
        Dan

    This is an interesting variation on an old problem.

    I'm don't have the time (or energy) right now to think about this,
    but the problem is closely related to the "problem des recontres",
    or problem of coincidences.  The problem is to find how many
    permutations of N symbols there are with no symbol falling in its
    origional position.  For example, suppose people at a party all
    grab hats at random when they leave; what is the probablility
    that no guest grabs their own hat?

    A permutation with no coincidences is called a derangement, and your
    problem is to count those derangements that are further restricted
    to have no exchanges of any 2 symbols.

    It should be possible to derive a recurrance relation for the number
    of exchange free derangements.

    - Jim

        I think Knuth covers this in the section on testing
        random number generators.
        
        Dan

Clearly, the probability approaches

	1/e

as the number of hats approaches infinity, but the margin doesn't allow me

        re .6,
        
>>Clearly, the probability approaches
>>
>>	1/e
>>
>>as the number of hats approaches infinity,
        
        Lisp> (exp -1.0l0)
        0.367879441171442321595523770161461L0
        
        That's not so clear to me.  The random trials were
        between 39% and 40%, a little too high to be 1/e.
        
        Dan

    I've tried looking up some of the reference material mentioned earlier
    and couldn't see anything that applied-probably my own ignorance.  If
    it's too hard to get a closed form for the probability, is it possible
    to at least "prove" that the probability approaches a limit as the
    number of people goes to infinity?
    
    Thanks,
    
    Bob

	It can be shown that if everyone at a party throws their hat in the
	middle, then grabs a random hat, the probability that NO ONE gets
	their own hat approaches 1/e as the starting party increases.

	Can this santa problem be fit into that model or something close ?

        The secret santa "algorithm" selects a permutation in
        which no one is assigned to hirself.  But does it do so
        in such a way that every such "acceptable" permutation is
        equally likely to be generated?  The details were in an
        earlier note but I'll repeat them.  Each person in turn
        selects a name not yet chosen but not hir own.  The last
        person swaps with the next-to-last if stuck with hir own
        name.  This ensures (insures? assures?) everyone gets
        someone else's name, but does it do so with equal
        probability of all such outcomes?
        
        Dan

    re .10
    
    I was worried about distribution function as well.  I first ran a
    simulation where I generated a permutation at random and then checked
    if anyone had picked their own name.  If someone had picked their own
    name I "threw out" the sample.  The algorithm was slow running and so I
    never ran very large runs.  The probability seemed to converge to about
    36% or so-I don't remember the exact number; but perhaps closer to the
    1/e speculation mentioned earlier.
    
    I changes the selection criteria to what you reposted, basically to
    make the algorithm run faster.  I thought that the permutations would
    be equally likey.  But the new simulations did converge closer to 39%
    or 40% as I think you also found.
    
    The intent of the problem was to solve the problem for equally likely
    permutations.  Inuitively both above selection algorithms appear to
    accomplish this, but I'm guilty of carelessness (or more likely like of
    mathematical sophistication) in assuming without proof that they are
    the same.

        Selecting from all permutations, with equal probability,
        and then rejecting those with any fixed points, DOES
        select from the remaining permutations with equal
        probability.  But as you found you accept only 1/e of the
        time (less than half).  The only question is whether the
        specific "secret santa" selection process chooses with
        equal probability.  A simulation suggests that it doesn't
        (I expected to see each permutation come up 1000 times):
        
((4 3 0 1 2) 575)
((4 3 0 2 1) 593)
((3 4 1 2 0) 605)
((3 4 0 2 1) 607)
((4 3 1 0 2) 607)
((4 3 1 2 0) 608)
((4 2 0 1 3) 620)
((3 4 0 1 2) 625)
((3 4 1 0 2) 645)
((4 2 1 0 3) 669)
((2 4 0 1 3) 679)
((2 4 1 0 3) 692)
((3 2 4 1 0) 879)
((3 2 0 4 1) 883)
((4 2 3 0 1) 893)
((2 4 3 0 1) 895)
((2 3 0 4 1) 900)
((2 3 4 0 1) 902)
((4 0 1 2 3) 905)
((2 3 1 4 0) 906)
((1 4 0 2 3) 908)
((2 4 3 1 0) 912)
((2 3 4 1 0) 924)
((1 0 4 2 3) 942)
((4 2 3 1 0) 949)
((3 2 1 4 0) 958)
((3 2 4 0 1) 968)
((3 0 4 2 1) 1156)
((1 0 3 4 2) 1173)
((1 3 0 4 2) 1181)
((4 0 3 1 2) 1186)
((1 3 4 0 2) 1214)
((3 0 1 4 2) 1220)
((1 4 3 2 0) 1248)
((1 4 3 0 2) 1249)
((3 0 4 1 2) 1255)
((4 0 3 2 1) 1281)
((1 3 4 2 0) 1290)
((2 0 1 4 3) 1361)
((2 0 4 1 3) 1386)
((1 2 4 0 3) 1394)
((1 2 0 4 3) 1414)
((2 0 3 4 1) 1813)
((1 2 3 4 0) 1930)
	
        Can someone else run the selection algorithm a few
        thousand times and report the results?
        
        Dan

	What is the probability, P(n) that a permutation of n symbols is a
derangement?

	The probability that a given symbol is in a cycle of length j
is:
	for j = 1, 1/n
	for j = 2, (n-1)/n * 1/(n-1) = 1/n
	for j = 3, (n-1)/n * (n-2)/(n-1) * 1/(n-2) = 1/n
	...

i.e. the probability is 1/n.

	So P(n) = sum(j=0,..n-2)P(j) / n

P(0) = 1
P(1) = 0
P(2) = 1/2
P(3) = 1/3
P(4) = 3/8
P(5) = 11/30
P(6) = 53/144

	n*P(n) = (n-1)*P(n-1) + P(n-2)

	Let Q(n) = P(n)-P(n-1)

	n*Q(n) = -Q(n-1)

	Q(n) = (-1)^n * 1/n!

	P(n) = sum(j=0..n)Q(n), which is simply the Taylor series expansion
to n terms of the function e^x at the point x = -1.   Thus, as n zooms to
infinity, we converge to 1/e.

	Now can we try the same approach for exchanges.   Let R(n) be the
probability that a permutation is a derangement with no exchanges.

	R(n) = sum(j=0,..,n-3)R(j) / n

R(0) = 1
R(1) = 0
R(2) = 0
R(3) = 1/3
R(4) = 1/4
R(5) = 1/5
R(6) = 2/9

	n*R(n) = (n-1)*R(n-1) + R(n-3)

	Let T(n) = R(n)-R(n-1)

	n*T(n) = -T(n-1) -T(n-2)

???????

>	n*T(n) = -T(n-1) -T(n-2)
>	T(1) = -1, T(2) = 0

	Well, n!*T(n) is clearly an integer, and for all non-tiny
values of n, n!*T(n) is a multiple of 2(n-2).   But beyond those obvious
factors, I can't see how to solve the recurrence, and neither can MAPLE.

	Any ideas, folks?

Regards,
Andrew.

        Is there a simple recurrence for S(n) = nT(n)?
        
        Dan

>        Is there a simple recurrence for S(n) = nT(n)?
        
	You tell me;  I don't see it.   Clearly there are large numbers
of possible variations on T(n) that one can explore.   The advantage of
defining:
		S'(n) = n!*T(n)/2*(n-2)

is that it is always an integer (as long as we aren't dealing with tiny n)
and yet has no consistent factors < n.   However the recurrence for S'
is not promising.

	Two other approaches might be:

	(i) sod the details, see what R(n) must converge towards in the end.
	(ii) prove there is no closed form expression for T(n), using
what I fancy would be quite sophisticated arguments.

Andrew.

    Well, R(n) seems to approach 0.22313 as (n -> oo).
    
    I do not know what the significance of .22313 is, however we should be
    able to demonstrate its truth:
    
    
.13>	n*R(n) = (n-1)*R(n-1) + R(n-3)
    
    
    OK, so lets assume the R(n) will eventually stabilize.  If so then:
    
    	R(n) = R(n-1)  +/- epsilon 
    
    for some sufficiently large (n), where epsilon is small enough to be
    inconsequential.  Hence, above some value of (n):   all R(n) = K.
    
    Sustituting into the equation copied from .13:
    
    
    	n*K = (n-1)*K + K
    
    Now reducing:
    
    	0 = n*K - (n-1)*K - K
    
    	0 = K * (n - (n-1) - 1)
    
    	0 = K * (n - n + 1 - 1)
    
    	0 = K * ( 0 + 0 )
    
    	0 = K * 0
    
    Hmmm.  That works for any K.
    
    I interpret this to mean that whenever 3 R(i) in a row are sufficiently
    close together, the series will rapidly converge around that point,
    wherever it is.  This seems a little chaotic to me, ie. "Sensitive
    dependency on initial conditions" and all that.  Playing around with a
    spreadsheet seems to confirm this.
    
    --  Barry

    In fact playing around with my spread sheet I noticed that given
    and 3 values in sequence in an R(n)-type series, then all subsequent
    values will be within the range defined by those three values.
    
    --  Barry

	re .17,
        
>>    Well, R(n) seems to approach 0.22313 as (n -> oo).
        
        That is as a proportion of all n! permutations.  When you
        consider that asymptotically only 1/e of those n! are
        derangements, that leaves 0.22313 e or 0.60653 as the
        proportion of derangements with no 2-cycles.  That
        matches what I posted in reply .3, that approx. 39%-40%
        of all random "secret santa" trials had at least one
        2-cycle.
        
        Dan