Efficient sampling of random permutations

We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external memory. In contrast to previously known work for parallel setups, our method is able to fulfill the three criteria of uniformity, work-optimality and balance among the processors simultaneously. To guarantee the uniformity we investigate the matrix of communication requests between the processors. We show that its distribution is a generalization of the multivariate hypergeometric distribution and we give algorithms to sample it efficiently in the two settings.     

The shape of random pattern-avoiding permutations

We initiate the study of limit shapes for random permutations avoiding a given pattern. Specifically, for patterns of length 3, we obtain delicate results on the asymptotics of distributions of positions of numbers in the permutations. We view the permutations as 0–1 matrices to describe the resulting asymptotics geometrically. We then apply our results to obtain a number of results on distributions of permutation statistics.     

The cyclic structure of random permutations

Letα _r denote the number of cycles of length r in a random permutation, taking its values with equal probability from among the set S_n of all permutations of length n. In this paper we study the limiting behavior of linear combinations of random permutationsα ₁, ...,α _r having the form $$\zeta _{n, r} = c_{r1^{a_1 } } + ... + c_{rr} a_r $$ in the case when n, r→∞. We shall show that the class of limit distributions forξ _n,r as n, r→∞ and r In r/h→0 coincides with the class of unbounded divisible distributions. For the random variables η_n, r=α ₁+2α ₂+... rα _r, equal to the number of elements in the permutation contained in cycles of length not exceeding r, we find' limit distributions of the form r In r/n→0 and r=γ ⁿ, 0<γ<1.     

On random permutations of finite groups

Given a finite abelian group G,  consider a uniformly random permutation of the set of all elements of G. Compute the difference of each pair of consecutive elements along the permutation. What is the number of occurrences of \(h\in G\setminus \{0\}\) in this sequence of differences? How do these numbers of occurrences behave for several group elements simultaneously? Can we get similar results for non-abelian G? How do the answers change if differences are replaced by sums? In this paper, we answer these questions. Moreover, we formulate analogous results in a general combinatorial setting.

     

Integrals over Grassmannians and random permutations

Testing the independence of two Gaussian populations involves the distribution of the sample canonical correlation coefficients, given that the actual correlation is zero. The “Laplace transform” (as a function of x) of this distribution is not only an integral over the Grassmannian of p-dimensional planes in real, complex or quaternion n-space , but is also related to a generalized hypergeometric function. Such integrals are solutions of Painlevé-like equations; in the complex case, they are solutions to genuine Painlevé equations. These integrals over have remarkable expansions in x, related to random words of length ? formed with an alphabet of p letters 1,…,p. The coefficients of these expansions are given by the probability that a word (i) contains a subsequence of letters p,p−1,…,1 in that order and (ii) that the maximal length of the disjoint union of p−1 increasing subsequences of the word is ?k, where k refers to the power of x. Note that, if each letter appears in the word, then the maximal length of the disjoint union of p increasing subsequences of the word is automatically =? and is thus trivial.     

Spatial random permutations with small cycle weights

We consider the distribution of cycles in two models of random permutations, that are related to one another. In the first model, cycles receive a weight that depends on their length. The second model deals with permutations of points in the space and there is an additional weight that involves the length of permutation jumps. We prove the occurrence of infinite macroscopic cycles above a certain critical density.     

Coherent random permutations with biased record statistics

We consider random permutations that are defined coherently for all values of n, and for each n have a probability distribution which is conditionally uniform given the set of upper and lower record values. Our central example is a two-parameter family of random permutations that are conditionally uniform given the counts of upper and lower records. This family may be seen as an interpolation between two versions of Ewens’ distribution. We discuss characterisations of the conditionally uniform permutations, their asymptotic properties, constructions and relations to random compositions.     

On random permutations without cycles of some lenghts

We deal with random permutations of the symmetric group S_Nendowed with the Haar probability measure. The main purpose of the remark is to obtain uniform lower estimates for the probability of a permutation without cycles having lengths in some J &sub; {1, . . . . N} . ThesetJcan itself depend on N. The only information used is a bound for the sum of reciprocals of elements in J.     

Hamilton cycles in the union of random permutations

We prove that with high probability, two random permutations contain an undirected Hamilton cycle and three random permutations almost always contain a directed Hamilton cycle. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 83–94, 2001     

Kruglov operator and operators defined by random permutations

The Kruglov property and the Kruglov operator play an important role in the study of geometric properties of r. i. function spaces. We prove that the boundedness of the Kruglov operator in an r. i. space is equivalent to the uniform boundedness on this space of a sequence of operators defined by random permutations. It is also shown that there is no minimal r. i. space with the Kruglov property.     

A functional limit theorem on powers of random permutations

We prove a functional limit theorem for a process defined via partial sums of an additive function on the subset of powers of permutations in the symmetric group. It establishes necessary and sufficient conditions for the convergence to the standard Brownian motion. The main ingredient of the applied approach is estimation of the total-variation distance from the distribution of a cycle structure vector to the distribution of an appropriate random vector with independent coordinates.     

Local probabilities and total variation distance for random permutations

We are concerned with permutations taken uniformly at random from the symmetric group. Firstly, we study the probability of a permutation missing short cycles. Secondly, the result is employed to establish a formula for total variation distance between the process of multiplicities of cycle lengths in a random permutation and a process of independent Poisson random variables. We apply an analytic approach originated in number theory (K. Gyory et al. (Eds.) in Number Theory in Progress, 1999).     

On edge-weighted recursive trees and inversions in random permutations

We introduce random recursive trees, where deterministically weights are attached to the edges according to the labeling of the trees. We will give a bijection between recursive trees and permutations, which relates the arising edge-weights in recursive trees with inversions of the corresponding permutations. Using this bijection we obtain exact and limiting distribution results for the number of permutations of size n, where exactly m elements have j inversions. Furthermore we analyze the distribution of the sum of labels of the elements, which have exactly j inversions, where we can identify Dickman's infinitely divisible distribution as the limit law. Moreover we give a distributional analysis of weighted depths and weighted distances in edge-weighted recursive trees.     

Asymptotic sine laws arising from alternating random permutations and sequences

In the last century, Désiré André obtained many remarkable properties of the numbers of alternating permutations, linking them to trigonometric functions among other things. By considering the probability that a random permutation is alternating and that a random sequence (from a uniform distribution) is alternating, and by conditioning on the first element of the sequence, his results are extended and illuminated. In particular, several “asymptotic sine laws” are obtained, some with exponential rates of convergence. © 1996 John Wiley & Sons, Inc.     

An integral characterization of random permutations. A point process approach

We consider random finite permutations and prove the following version of Thoma’s theorem in [8]: Random finite permutations which are class functions satisfy a new integration by parts formula if and only if they are given by a certain Ewens-Sütö process. The main source of inspiration for the results in this note is the fundamental work of Andras Sütö [7], from which some results are reestablished here again in the present point process approach.