We study the lengths of monotone subsequences for permutations drawn from the Mallows measure. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation @math is proportional to @math where @math is a positive parameter and @math is the number of inversions in @math . In our main result we show that when @math , the limiting distribution of the longest increasing subsequence (LIS) is Gaussian, answering an open question in [Bhatnagar and Peled, PTRF, 2015]. This is in contrast to the case when @math where the limiting distribution of the LIS when scaled appropriately is the GUE Tracy-Widom distribution. We also obtain a law of large numbers for the length of the longest decreasing subsequence (LDS) and identify the precise constant in the order of the expectation, answering a further open question in [Bhatnagar and Peled, PTRF, 2015].
Subsequently, in @cite_22 , Bhatnagar and Peled established the leading order behavior of @math in the regime that @math and @math . They analyzed an insertion process which they called the Mallows process for randomly generating Mallows distributed permutations and showed that @math in @math for @math as @math . They established the order of @math and showed that it grows at different rates for different regimes of @math as a function of @math (in particular they showed @math when @math is fixed) and proved large deviation bounds for @math and @math . They also established a linear upper bound on the variance of @math and left open the questions of determining the precise variance and the distribution of @math for all regimes of @math and @math .
@cite_22
2002850151 2517585112 2798600727 1989633256
A discrete uncoupling process for finite spaces is introduced, called the Markov Cluster Process or the MCL process. The process is the engine for the graph clustering algorithm called the MCL algorithm. The MCL process takes a stochastic matrix as input, and then alternates expansion and inflation, each step defining a stochastic matrix in terms of the previous one. Expansion corresponds with taking the @math th power of a stochastic matrix, where @math . Inflation corresponds with a parametrized operator @math , @math , that maps the set of (column) stochastic matrices onto itself. The image @math is obtained by raising each entry in @math to the @math th power and rescaling each column to have sum 1 again. In practice the process converges very fast towards a limit that is invariant under both matrix multiplication and inflation, with quadratic convergence around the limit points. The heuristic behind the process is its expected behavior for (Markov) graphs possessing cluster structure. The process is typically applied to the matrix of random walks on a given graph @math , and the connected components of (the graph associated with) the process limit generically allow a clustering interpretation of @math . The limit is in general extremely sparse and iterands are sparse in a weighted sense, implying that the MCL algorithm is very fast and highly scalable. Several mathematical properties of the MCL process are established. Most notably, the process (and algorithm) iterands posses structural properties generalizing the mapping from process limits onto clusterings. The inflation operator @math maps the class of matrices that are diagonally similar to a symmetric matrix onto itself. The phrase diagonally positive semi-definite (dpsd) is used for matrices that are diagonally similar to a positive semi-definite matrix. For @math and for @math a stochastic dpsd matrix, the image @math is again dpsd. Determinantal inequalities satisfied by a dpsd matrix @math imply a natural ordering among the diagonal elements of @math , generalizing the mapping of process limits onto clusterings. The spectrum of @math is of the form @math , where @math is the number of endclasses of the ordering associated with @math , and @math is the dimension of @math . This attests to the uncoupling effect of the inflation operator. We study a noiseless broadcast link serving @math users whose requests arise from a library of @math files. Every user is equipped with a cache of size @math files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most @math file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file @math scales to infinity. The asymptotic coding gain obtained is roughly @math . In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets @math is a function of the system parameters @math , and @math . Specifically, we show that the existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of 2 even if the number of packets is exponential in the asymptotic gain @math . Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of @math is at least @math . We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters. This article offers a simplified approach to the distribution theory of randomly weighted averages or @math -means @math , for a sequence of i.i.d.random variables @math , and independent random weights @math with @math and @math . The collection of distributions of @math , indexed by distributions of @math , is shown to encode Kingman's partition structure derived from @math . For instance, if @math has Bernoulli @math distribution on @math , the @math th moment of @math is a polynomial function of @math which equals the probability generating function of the number @math of distinct values in a sample of size @math from @math : @math . This elementary identity illustrates a general moment formula for @math -means in terms of the partition structure associated with random samples from @math , first developed by Diaconis and Kemperman (1996) and Kerov (1998) in terms of random permutations. As shown by Tsilevich (1997) if the partition probabilities factorize in a way characteristic of the generalized Ewens sampling formula with two parameters @math , found by Pitman (1992), then the moment formula yields the Cauchy-Stieltjes transform of an @math mean. The analysis of these random means includes the characterization of @math -means, known as Dirichlet means, due to Von Neumann (1941), Watson (1956) and Cifarelli and Regazzini (1990) and generalizations of L 'evy's arcsine law for the time spent positive by a Brownian motion, due to Darling (1949) Lamperti (1958) and Barlow, Pitman and Yor (1989). We study the length of the longest increasing and longest decreasing subsequences of random permutations drawn from the Mallows measure. Under this measure, the probability of a permutation ( S_n ) is proportional to (q^ Inv ( ) ) where (q ) is a real parameter and ( Inv ( ) ) is the number of inversions in ( ). The case (q=1 ) corresponds to uniformly random permutations. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics. We determine the typical order of magnitude of the lengths of the longest increasing and decreasing subsequences, as well as large deviation bounds for them. We also provide a simple bound on the variance of these lengths, and prove a law of large numbers for the length of the longest increasing subsequence. Assuming without loss of generality that (q<1 ), our results apply when (q ) is a function of (n ) satisfying (n(1-q) ). The case that (n(1-q)=O(1) ) was considered previously by Mueller and Starr. In our parameter range, the typical length of the longest increasing subsequence is of order (n 1-q ), whereas the typical length of the longest decreasing subsequence has four possible behaviors according to the precise dependence of (n ) and (q ). We show also that in the graphical representation of a Mallows-distributed permutation, most points are found in a symmetric strip around the diagonal whose width is of order (1 (1-q) ). This suggests a connection between the longest increasing subsequence in the Mallows model and the model of last passage percolation in a strip.