Conjecture 1. The random variable L1 /n converges in distribution to a uniform random variable in [0, 1].
Statement
Conjecture 1. The random variable L1 /n converges in distribution to a uniform random variable in [0, 1]. We can also ask about the length Mk of the k-th largest cycle in \pi. Conjecture 2. The random variable (M1 /n, M2 /n, . . . ) converges in distribution to a the Poisson Dirichlet process of parameter 1. Informally, the two conjectures above mean that we expect \pi to behave asymp- totically as a uniform random permutation. Indeed, Conjectures 1 and 2 are well-known to hold if \pi is replaced by a uniform random permutation (in fact, in this case, the distribution of L1 is uniform on {1, . . . , n}). A stronger conjecture would be that the total variation distance dTV (\pi, Unif(Sn )) converges to 0. The counterpart for short cycles follow from a result of Kammoun and Maida [7]. Theorem 3. If Ck is the number of k-cycles in \pi, then the Ck ’s converge jointly in distribution to independent Poisson random variables of parameter 1/k. Generalization to primitive words. Of course, one can ask the question for any word w in the alphabet {\sigma, \tau }, not only for \sigma\tau \sigma 2 \tau 2 as above (we could also admit inverses, though we will not discuss this here). When \sigma and \tau are independent uniform random permutations, w can be interpreted as a random permutation. We believe that Conjectures 1 and 2 hold for w as soon as w is primitive, i.e., cannot be written as a concatenation power of a shorter word. The theorem above of Kammoun and Maida holds in this setting. thus generalizing the probability of being a tree (Cayley’s formula) by an additional factor of k. My main question is: Question: Can one do exact enumeration of w-trees? Can you conjecture, or prove, an exact formula, or even a recurrence formula or functional equation, to produce the number of w-trees of size n? I mean, even for the simplest word W = AB I can’t do anything! Remark: for any d > 0 and any function w, both w and wd have the same cyclic points, so the number of w-trees is the same as that of wd -trees. The hypothesis that W is primitive in the statement above is thus both necessary and harmless. A related question is to ask, for two different words W and W ′ , whether the associated random functions w and w′ have distributions which are very similar, or very different. Does their total variation distance go to 0, to 1, or neither, with certain conditions on W and W ′ ? First partial answers are given in [3].
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.