ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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? 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 ′ ? 5. Words in random permutations (problem of Valentin Féray) Setting. Consider two independent uniform random permutations \sigma, \tau , and set \pi = \sigma\tau \sigma 2 \tau 2 . As \pi is conjugacy invariant, we are interested in its cycle structure. The first conjecture deals with the length L1 of the cycle containing 1 in \pi. 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

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.