Counting Simsun Permutations by Descents

We count in the present work simsun permutations of length n by their number of descents. Properties studied include the recurrence relation and real-rootedness of the generating function of the number of n-simsun permutations with k descents. By means of generating function arguments, we show that the descent number is equidistributed over n-simsun permutations and n-André permutations. We also compute the mean and variance of the random variable X _n taking values the descent number of random n-simsun permutations, and deduce that the distribution of descents over random simsun permutations of length n satisfies a central and a local limit theorem as n ?? +???.     

Random doubly stochastic tridiagonal matrices

Let \begin{align*}{\mathcal T}\end{align*}n be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally in probability problems as birth and death chains with a uniform stationary distribution. We study ‘typical’ matrices T∈ \begin{align*}{\mathcal T}\end{align*}n chosen uniformly at random in the set \begin{align*}{\mathcal T}\end{align*}n. A simple algorithm is presented to allow direct sampling from the uniform distribution on \begin{align*}{\mathcal T}\end{align*}n. Using this algorithm, the elements above the diagonal in T are shown to form a Markov chain. For large n, the limiting Markov chain is reversible and explicitly diagonalizable with transformed Jacobi polynomials as eigenfunctions. These results are used to study the limiting behavior of such typical birth and death chains, including their eigenvalues and mixing times. The results on a uniform random tridiagonal doubly stochastic matrices are related to the distribution of alternating permutations chosen uniformly at random.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 403–437, 2013     

What portion of the sample makes a partial sum asymptotically stable or normal?

Summary Let a sequence of independent and identically distributed random variables with the common distribution function in the domain of attraction of a stable law of index 0<2 be given. We show that if at each stage n a number k _n depending on n of the lower and upper order statistics are removed from the n-th partial sum of the given random variables then under appropriate conditions on k _n the remaining sum can be normalized to converge in distribution to a standard normal random variable. A further analysis is given to show which ranges of the order statistics contribute to asymptotic stable law behaviour and which to normal behaviour. Our main tool is a new Brownian bridge approximation to the uniform empirical process in weighted supremum norms.Work done while visiting the Bolyai Institute, Szeged University, partially supported by a University of Delaware Research Foundation Grant     

On restricted min‐wise independence of permutations

A family of permutations ℱ ⊆ S_n with a probability distribution on it is called k-restricted min-wise independent if we have Pr[min π(X) = π(x)] = 1/|X| for every subset X ⊆ [n] with |X| ≤ k, every x ∈ X, and π ∈ ℱ chosen at random. We present a simple proof of a result of Norin: every such family has size at least Some features of our method might be of independent interest. The best available upper bound for the size of such family is 1 + ∑ (j − 1)(). We show that this bound is tight if the goal is to imitate not the uniform distribution on S_n, but a distribution given by assigning suitable priorities to the elements of [n] (the stationary distribution of the Tsetlin library, or self-organizing lists). This is analogous to a result of Karloff and Mansour for k-wise independent random variables. We also investigate the cases where the min-wise independence condition is required only for sets X of size exactly k (where we have only an Ω(log log n + k) lower bound), or for sets of size k and k − 1 (where we already obtain a lower bound of n − k + 2). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Conditioning exceedances on covariate processes

This article concerns the statistical inference for the upper tail of the conditional distribution of a response variable Y given a covariate X = x based on n random vectors within the parametric extreme value framework. Pioneering work in this field was done by Smith (Stat Sci 4:367–393, 1989) and Smith and Shively (Atmos Environ 29:3489–3499, 1995). We propose to base the inference on a conditional distribution of the point process of exceedances given the point process of covariates. It is of importance that the conditional distribution merely depends on the conditional distribution of the response variable given the covariates. In the special case of Poisson processes such a result may be found in Reiss (1993). Our results are valid within the broader model where the response variables are conditionally independent given the covariates. It is numerically exemplified that the maximum likelihood principle leads to more accurate estimators within the conditional approach than in the previous one.     

How Many Comparisons Does Quicksort Use?

We examine the probability distribution of the number of comparisons needed by the Quicksort sorting algorithm, where probability arises due to the items being in random order. We develop a general class of distributions for the permutation of the items to be sorted which includes the uniform distribution on permutations as a special case. For this general class, the distribution of the number of comparisons is given by the solution of a simple recurrence relation. We provide an exact solution of the recurrence for very small n. We show that the solution can be approximated asymptotically by the solution of a "quadratic" operator equation. We exhibit three numerical solutions to the operator equation for two different distributions on permutations from the general class. We also exhibit numerical solutions for the case in which the algorithm is modified so that arrays are partitioned by the median-of-three selected items rather than by a single selected item.     

First‐passage percolation on a ladder graph,and the path cost in a VCG auction

This paper studies the time constant for first‐passage percolation, and the Vickrey‐Clarke‐Groves (VCG) payment, for the shortest path on a ladder graph (a width‐2 strip) with random edge costs, treating both in a unified way based on recursive distributional equations. For first‐passage percolation where the edge costs are independent Bernoulli random variables we find the time constant exactly; it is a rational function of the Bernoulli parameter. For first‐passage percolation where the edge costs are uniform random variables we present a reasonably efficient means for obtaining arbitrarily close upper and lower bounds. Using properties of Harris chains we also show that the incremental cost to advance through the medium has a unique stationary distribution, and we compute stochastic lower and upper bounds. We rely on no special properties of the uniform distribution: the same methods could be applied to any well‐behaved, bounded cost distribution. For the VCG payment, with Bernoulli‐distributed costs the payment for an n‐long ladder, divided by n, tends to an explicit rational function of the Bernoulli parameter. Again, our methods apply more generally. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 350‐364, 2011     

A recursive construction of t‐wise uniform permutations

We present a recursive construction of a (2t + 1)‐wise uniform set of permutations on 2n objects using a combinatorial design, a t‐wise uniform set of permutations on n objects and a (2t + 1)‐wise uniform set of permutations on n objects. Using the complete design in this procedure gives a t‐wise uniform set of permutations on n objects whose size is at most t²ⁿ, the first non‐trivial construction of an infinite family of t‐wise uniform sets for . If a non‐trivial design with suitable parameters is found, it will imply a corresponding improvement in the construction. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 531–540, 2015     

Detection of slightly expressed changes in random environment

Consider a regular parametric family of distributions F(·, θ). The classical change point problem deals with observations corresponding to θ = 0 before a point of change, and θ = μ after that. We substitute the latter constant μ by a set of random variables θ _i,n called a random environment assuming that E[θ _i,n ] = μ _n → 0. The random environment can be independent or obtained by random permutations of a given set. We define the rates of convergence and give the conditions under which the classical parametric change point algorithms apply.     

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R d

We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in \R ^d , is Θ (n ^d-1 ) . This improves substantially the upper bound of O(n ^2d-2 ) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5]. Received September 21, 1998, and in revised form March 14, 1999.     

Local Limit Theorems for Sums of Power Series Distributed Random Variables and for the Number of Components in Labelled Relational Structures

A Local limit theorem for the distribution of the number of components in random labelled relational structures of size n (e.g., a type of random graphs on n vertices, random permutations of n elements, etc.) is proved as n→∞. The case when the corresponding exponential generating functions diverge at their radii of convergence is considered.     

Bounds for the probability of generating the symmetric and alternating groups

We give explicit, asymptotically sharp bounds for the probability that a pair of random permutations of degree n generates either S _n or A _n and also for the probability that a pair of random even permutations of degree n generates A _n . As an application we answer a question of Wiegold in the case of alternating groups.     

Refined Approximations for the Ewens Sampling Formula

The Ewens sampling formula is a family of probability distributions over the space of cycle types of permutations of n objects, indexed by a real parameter θ. In the case θ = 1, where the distribution reduces to that induced by the uniform distribution on all permutations, the joint distributions of the numbers of cycles of lengths less than b = o(n) is extremely well approximated by a product of Poisson distributions, having mean 1/j for cycle length j: the error is super-exponentially small with nb^?1. For θ ≠ 1. the analogous approximation, with means adjusted to θ/j, is good, but with error only linear in n^?1b. In this article, it is shown that, by choosing the means of the Poisson distributions more carefully, an error quadratic in n^?1b can be achieved, and that essentially nothing better is possible.     

On the distribution of binary search trees under the random permutation model

We study the distribution Q on the set B_n of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B_n when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the “shape” of the tree. We study the distribution of Q(T) for two choices of distribution for random trees T; uniform over B_n and Q. In the latter case, we obtain a limiting normal distribution for −ln Q(T). © 1996 John Wiley & Sons, Inc.     

Rapidly Mixing Random Walks and Bounds on Characters of the Symmetric Group

We investigate mixing of random walks on S _n and A _n generated by permutations of a given cycle structure. The approach follows methods developed by Diaconis, which requires certain estimates on characters of the symmetric group and uses combinatorics of Young tableaux. We conclude with conjectures and open problems.     

The bias of three pseudo-random shuffles

Three schemes for shuffling a deck ofn cards are studied, each involving a random choice from [n] ⁿ . The shuffles favor some permutations over others sincen! does not dividen ⁿ . The probabilities that the shuffles lead to some simple permutations, for instance cycles left and right and the identity, are calculated. Some inequalities are obtained which lead to information about the least and most likely permutations. Numbers of combinatorial interest occur, notably the Catalan numbers and the Bell numbers.     

Branching structure of uniform recursive trees

The branching structure of uniform recursive trees is investigated in this paper. Using the method of sums for a sequence of independent random variables, the distribution law of ηn, the number of branches of the uniform recursive tree of size n are given first. It is shown that the strong law of large numbers, the central limit theorem and the law of iterated logarithm for ηn follow easily from this method. Next it is shown that ηn and ξn, the depth of vertex n, have the same distribution, and the distribution law of ζn,m, the number of branches of size m, is also given, whose asymptotic distribution is the Poisson distribution with parameter λ= 1/m. In addition, the joint distribution and the asymptotic joint distribution of the numbers of various branches are given. Finally, it is proved that the size of the biggest branch tends to infinity almost sure as n→∞.     

Generating a Random Signed Permutation with Random Reversals

Signed permutations form a group known as the hyperoctahedral group. We bound the rate of convergence to uniformity for a certain random walk on the hyperoctahedral group that is generated by random reversals. Specifically, we determine that O(n log n) steps are both necessary and sufficient for total variation distance and ℓ² distance to become small. This random walk arose as the result of an effort in molecular biology to model certain types of genome rearrangements.     

Permutations Generated by Stacks and Deques

Lower and upper bounds are given for the the number of permutations of length n generated by two stacks in series, two stacks in parallel, and a general deque.