Uniform Distributions Of Santa. Please excuse my ignorance about this area of combinatorics; I am curious about what is meant by a "uniform distribution to the derangements". Here is where I am confused. I have suggested here that a derangement is a directed graph of one or more cycles of two or more vertexes. Every person is assigned a vertex of the graph and we walk the cycle generating Santa's and recipients. To get a uniform distribution we then randomly choose a graph of a derangement and then randomly assign each person a vertex. For five people there are only two possible graphs, a graph of a single five cycle, and a graph consisting of a two cycle and a three cycle. Clearly if we choose one of the two graphs with any probability distribution, 1/2 - 1/2 or 1/3 - 2/3, and then assign each person to a vertex, the distribution will be even in the sense that each person has an equal chance for each vertex. The debate over how to adjust the probability of choosing one graph or another seems to me to be somewhat arbitrary. There was a suggestion her at one point that we allow only the connected cycle of all vertexes. If we generate every possible graph on N vertexes, and then choose every graph that consists only of cycles from that group and treat each one as having equal probability we get one answer. If we select only from the set of non-isomorphic graphs we get a different answer. If we count the possible permutations of assignments in each graph, so that a graph of four vertexes is four times as likely to be chosen as a graph of three vertexes, we get yet another answer. If we weight the probability by the number of vertexes in a cycle we get yet another answer. Any of these methods generates an even distribution in the sense that each person is equally likely to be chosen for any edge. The envelope flap method, IMHO the best described so far in terms of practicality, does meet the above test for uniform distribution, although it doesn't hide the conditional probabilities from the players, since one can calculate the probability that each player after a given point will be a neighbor with increasing accuracy as the game is played. That can be fixed by making the names aliases and then drawing them from a hat, but it then removes the nice feature of it being a single draw for each name and removes the feature of minimal preparation. In the real world, the envelope method would work quite well, it is a practical answer to a practical question with a mathematical flavor. I would be interested though in knowing what the probability of any particular distinguishable graph of cycles is, and how the probability of being in a particular x-cycle changes as a function of the position in the sequence at which a name is drawn. Regards Otto otto@olympus.net On Friday 09 January 2004 10:47, Fred W. Helenius wrote:
At 11:31 AM 1/9/04, Michael Kleber wrote:
I'll have to think more about whether there's an easy variant that will give uniform distribution to the derangements generated --- without giving out more information.
An observation: A large class of "hat-drawing-like" algorithms-- including most of those proposed in the past day--cannot generate derangements uniformly.
If the procedure involves a finite sequence of uniform choices, each from a set of N or fewer objects, the probability of any particular sequence of choices will be 1/K, where K contains no prime factors larger than N. A particular derangement might be generated in many ways, so its probability would be the sum of different 1/K terms, but the total probability still will have no prime factor larger than N in the denominator.
Unfortunately, the number of derangements for N = 5 is 44 = 2*2*11, and for N = 6, it's 265 = 5*53; so a prime factor larger than N is needed for the selection to be uniform.
There are three obvious ways around this limitation, although it isn't clear how to apply some of them to an algorithm that could be used at a restaurant table. First, allow an unbounded sequence of choices, as in the "select a permutation; if it isn't a derangement, start over" procedure. Second, allow non-uniform choices. Third, allow uniform choices from larger sets.