A random approach to the Lebesgue integral

We construct an integral of a measurable real function using randomly chosen Riemann sums and show that it converges in probability to the Lebesgue integral where this exists. We then prove some conditions for the almost sure convergence of this integral.     

The point process approach for fractionally differentiated random walks under heavy traffic

We prove some heavy-traffic limit theorems for some nonstationary linear processes which encompass the fractionally differentiated random walk as well as some FARIMA processes, when the innovations are in the domain of attraction of a non-Gaussian stable distribution. The results are based on an extension of the point process methodology to linear processes with nonsummable coefficients and make use of a new maximal type inequality.     

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.     

A characterization of permutations via skew-hooks

A characterization of permutations is given using skew-hooks, such that the r-descents of the permutation are reflected in the structure of the skew-hook. The characterization yields a combinatorial proof of Foulkes' skew-hook rule for computing Eulerian numbers.     

A point process approach to inventory models

The aim of the present paper is to make use of the modern theory of point processes to study optimal solutions for single‐item inventory. Demand for goods is assumed to occur according to a compound Poisson process and production occurs continuously and deterministically between times of demand, such that the inventory evolves according to a Markov process in continuous time. The aim is to propose a way of finding optimal production schemes by minimizing a certain expected loss over some finite period. There are holding/production costs depending on the stock level, and random penalty amounts will occur due to excess demand which is assumed backlogged. For simplicity we will not incorporate fixed costs. We give some numerical illustrations. Copyright © 2000 John Wiley & Sons, Ltd.     

Increasing permutations of random processes

The paper is concerned with an application of limit theorems to the study of increasing permutations of stable random processes. By the increasing permutation of a function is meant the nondecreasing function with the same distribution. The trajectories of a random process may be approximated by step-functions, and then the continuity of the increasing permutation operator permits one to apply the Skorokhod invariance principle to obtain the distribution of the random process. The distribution function and the expected value of the increasing permutation of a stable random process are given explicitly. Also the univariate distributions of the increasing permutation of the Cauchy process are obtained. In various normed spaces the images of the unit balls with respect to the operator of increasing permutation are described. A separate section is devoted to the increasing permutations of higher-dimensional processes. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 216, 1994, pp. 62–75. Translated by A. Sudakov.     

A state-space approach to quantum permutations

In this exposition of quantum permutation groups, an alternative to the ‘Gelfand picture’ of compact quantum groups is proposed. This point of view is inspired by algebraic quantum mechanics and interprets the states of an algebra of continuous functions on a quantum permutation group as quantum permutations. This interpretation allows talk of an element of a quantum permutation group, and allows a clear understanding of the difference between deterministic, random, and quantum permutations. The interpretation is illustrated by various quantum permutation group phenomena.     

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.     

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.

     

Compatible additive permutations of finite integral bases

Let be an additive permutation of a finite integral base. It is shown that ifB is symmetric, then there is a unique additive permutation ofB which is compatible with in the sense that ^–1 is also an additive permutation; and that, further, ifB is asymmetric, then there is no additive permutation ofB which is compatible with. Thus, in the symmetric case, there are no additively compatible sets (of permutations) forB of size greater than 3. This contrasts with the situation for completely compatible sets (equivalently, additive sequences of permutations) where for certainB compatible sets of size (resp. length) 4 or less are known, but where nothing is known of sets of greater size (resp. length). It is also noted how this result restricts the possibility of a useful multiplication theorem for the additive analogue of perfect systems of difference sets and graceful graphs.     

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.     

The writhe of permutations and random framed knots

We introduce and study the writhe of a permutation, a circular variant of the well‐known inversion number. This simple permutation statistics has several interpretations, which lead to some interesting properties. For a permutation sampled uniformly at random, we study the asymptotics of the writhe, and obtain a non‐Gaussian limit distribution. This work is motivated by the study of random knots. A model for random framed knots is described, which refines the Petaluma model, studied with Hass, Linial, and Nowik (Discrete Comput Geom, 2016). The distribution of the framing in this model is equivalent to the writhe of random permutations. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 121–142, 2017     

Cycle structure of random permutations with cycle weights

We investigate the typical cycle lengths, the total number of cycles, and the number of finite cycles in random permutations whose probability involves cycle weights. Typical cycle lengths and total number of cycles depend strongly on the parameters, while the distributions of finite cycles are usually independent Poisson random variables.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 109‐133, 2014     

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     

A Daniell integral approach to nonstandard Kurzweil-Henstock integral

A workable nonstandard definition of the Kurzweil-Henstock integral is given via a Daniell integral approach. This allows us to study the HL class of functions from [9]. The theory is recovered together with a few new results.     

A random clustering process

A clustering process which generates simple and uniform random partitions is studied. It has a single parameter and generates, for a special value of the parameter, the partition of a random permutation into its cycles. The limit distribution of the size index of the generated partition is the joint of the independent Poisson distributions with means determined by the size and the parameter.