A Problem in Permutations: the Game of 'Mousetrap'

The game of 'Mousetrap, a problem in permutations, first introduced by Arthur Cayley in 1857 and independently addressed by Cayley and Adolph Steen in 1878, has been largely unexamined since. The game involves permutations of n cards numbered consecutively from 1 to n. The cards are laid out face up in some order and the game is played by counting on the cards, beginning the count with 1. If at any time the number of the count matches the number on the card, this is called a hit and the card is thrown out. The counting begins again with 1 on the next card and returns to the first card when the nth card is reached. Each time a card is hit, that card is removed and the counting starts over at 1. The game continues until all the cards have been hit and thrown out (the player wins) or until the counting reaches n with no cards having been hit (the cards win). The game is re-introduced here and a summary of both Cayley's and Steen's work is presented. Computer programs, written to generate the types of permutations dealt with by Steen, uncovered discrepancies in his work. Further examination of these discrepancies lead to the discovery of a combinatorial pattern of coefficients which Steen was unable to recognize because of his computational errors. Corrected versions of Steen's erroneous formulas are presented.     

Limsup results and LIL for partial sum processes of a Gaussian random field

Let {ξ _j ; j ∈ ℤ₊ ^d be a centered stationary Gaussian random field, where ℤ₊ ^d is the d-dimensional lattice of all points in d-dimensional Euclidean space ℝ^d, having nonnegative integer coordinates. For each j = (j ₁ , ..., jd) in ℤ₊ ^d , we denote |j| = j ₁ ... j _d and for m, n ∈ ℤ₊ ^d , define S(m, n] = Σ _m<j≤n ζ _j , σ²(|n−m|) = ES ² (m, n], S _n = S(0, n] and S ₀ = 0. Assume that σ(|n|) can be extended to a continuous function σ(t) of t > 0, which is nondecreasing and regularly varying with exponent α at b ≥ 0 for some 0 < α < 1. Under some additional conditions, we study limsup results for increments of partial sum processes and prove as well the law of the iterated logarithm for such partial sum processes. Research supported by NSERC Canada grants at Carleton University, Ottawa     

Continuum limits for classical sequential growth models

A random graph order, also known as a transitive percolation process, is defined by taking a random graph on the vertex set {0,…,n ? 1} and putting i below j if there is a path i = i₁…i_k = j in the graph with i₁ < … < i_k. Rideout and Sorkin 14 provide computational evidence that suitably normalized sequences of random graph orders have a “continuum limit.” We confirm that this is the case and show that the continuum limit is always a semiorder. Transitive percolation processes are a special case of a more general class called classical sequential growth models. We give a number of results describing the large‐scale structure of a general classical sequential growth model. We show that for any sufficiently large n, and any classical sequential growth model, there is a semiorder S on {0,…,n ‐ 1} such that the random partial order on {0,…,n ‐ 1} generated according to the model differs from S on an arbitrarily small proportion of pairs. We also show that, if any sequence of classical sequential growth models has a continuum limit, then this limit is (essentially) a semiorder. We give some examples of continuum limits that can occur. Classical sequential growth models were introduced as the only models satisfying certain properties making them suitable as discrete models for spacetime. Our results indicate that this class of models does not contain any that are good approximations to Minkowski space in any dimension ≥ 2. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

The mathematics of perfect shuffles

There are two ways to perfectly shuffle a deck of 2n cards. Both methods cut the deck in half and interlace perfectly. The out shuffle O leaves the original top card on top. The in shuffle I leaves the original top card second from the top. Applications to the design of computer networks and card tricks are reviewed. The main result is the determination of the group 〈 I, O 〉 generated by the two shuffles, for all n. If 2n is not a power of 2, and if 2n ≠ 12,24, then 〈 I, O 〉 has index 1, 2, or 4 in the Weyl group B_n (the group of all 2ⁿn! signed n × n permutation matrices). If 2n = 2^k, then 〈 I, O 〉 is isomorphic to a semi-direct product of Z₂^k and Z_k. When 2n = 24, 〈 I, O 〉 is isomorphic to a semi-direct product of Z₂¹¹ and M₁₂, the Mathieu group of degree 12. When 2n = 12, 〈 I, O 〉 is isomorphic to a semi-direct product of Z₂⁶ and the group PGL(2,5) of all linear fractional transformations over GF(5).     

Disjoint skolem sequences and related disjoint structures

A Skolem sequence of order n is a sequence S = (s₁, s₂…, s²ⁿ) of 2n integers satisfying the following conditions: (1) for every k ∈ {1, 2,… n} there exist exactly two elements s_i,S_j such that S_i = S_j = k; (2) If s_i = s_j = k,i < j then j ? i = k. In this article we show the existence of disjoint Skolem, disjoint hooked Skolem, and disjoint near-Skolem sequences. Then we apply these concepts to the existence problems of disjoint cyclic Steiner and Mendelsohn triple systems and the existence of disjoint 1-covering designs. © 1993 John Wiley & Sons, Inc.     

The Advanced Australian Shuffle

The “classical” Australian under-down shuffle starts with a deck of n cards. Then one proceeds as follows: one card under the deck, one on the table, one under the deck, one on the table, etc. One continues until only one card remains. There is an explicit formula to calculate the number of the card in the original deck that survives, and this is the basis of several mathematical magic tricks.     

Trace formulas for a class of subnormal tuples of operators

Trace formulas are established for the product of commutators related to subnormal tuple of operators (S ₁,...,S _n ) with minimal normal extension (N ₁,...,N _n ) satisfying conditions that sp(S _j )/sp(N _j ) is simply-connected with smooth boundary Jordan curve sp(N _i ) and [S _j ^* ,S _j ]^1/2 L ¹,j=1, 2,...,n.Some complete unitary invariants related to the trace formulas are found.This work is supported in part by NSF Grant no. DMS-9101268.     

Precise asymptotics in self-normalized sums of iterated logarithm for multidimensionally indexed random variables

In the case of Zd (d ≥ 2)-the positive d-dimensional lattice points with partial ordering ≤, {Xk,k ∈ Zd } i.i.d. random variables with mean 0, Sn = ∑k≤nXk and Vn2 = ∑j≤nX2j, the precise asymptotics for ∑n1/|n|(log|n|)dP(|Sn/vn|≥ ε√loglog|n|) and ∑n(logn|)δ/|n|(log|n|)d-1 P(|Sn/Vn| ≥ ε√log n), as ε ↘ 0, is established.     

Limiting distribution of sums of nonnegative stationary random variables

Summary Let {X _n,j,−∞<j<∞∼,n≧1, be a sequence of stationary sequences on some probability space, with nonnegative random variables. Under appropriate mixing conditions, it is shown thatS _n=X_n,1+…+X _n,n has a limiting distribution of a general infinitely divisible form. The result is applied to sequences of functions {f _n(x)∼ defined on a stationary sequence {X _j∼, whereX _n.f=f_n(X_j). The results are illustrated by applications to Gaussian processes, Markov processes and some autoregressive processes of a general type. This paper represents results obtained at the Courant Institute of Mathematical Sciences, New York University, under the sponsorship of the National Sciences Foundation, Grant MCS 82-01119.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

The Weak Convergence for Functions of Negatively Associated Random Variables

Let {X_n, n1} be a sequence of stationary negatively associated random variables, S_j(l)=∑^l_i=1 X_j+i, S_n=∑ⁿ_i=1 X_i. Suppose that f(x) is a real function. Under some suitable conditions, the central limit theorem and the weak convergence for sums are investigated. Applications to limiting distributions of estimators of Var S_n are also discussed.     

On Selfsimilar Jordan Curves on the Plane

We study the attractors of a finite system of planar contraction similarities S _j (j=1,...,n) satisfying the coupling condition: for a set {x ₀,...,x _n} of points and a binary vector (s ₁,...,s _n ), called the signature, the mapping S _j takes the pair {x ₀,x _n} either into the pair {x _j-1,x _j } (if s _j =0) or into the pair {x _j , x _j-1} (if s _j =1). We describe the situations in which the Jordan property of such attractor implies that the attractor has bounded turning, i.e., is a quasiconformal image of an interval of the real axis.     

A determinantal description of GCD-closed sets and k-sets

Let S={x ₁,x ₂,…,x_n } be a naturally ordered set of distinct positive integers. S is called a k-set if k= gcd(x_i ,x_j ) for x_i ≠x_j any in S. In this paper k-sets are characterized by certain conditions on the determinants of some matrices associated with S.     

Stable Laws and Products of Positive Random Matrices

Let S be the multiplicative semigroup of q×q matrices with positive entries such that every row and every column contains a strictly positive element. Denote by (X _n ) _n≥1 a sequence of independent identically distributed random variables in S and by X ⁽ⁿ⁾=X _n ⋅⋅⋅ X ₁,  n≥1, the associated left random walk on S. We assume that (X _n ) _n≥1 satisfies the contraction property

多背包问题的半定松驰算法

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3.     

Conditional negative association for competing urns

We prove conditional negative association for random variables x _j = 1 (j∈[n]:= {1…n}) , where σ(1)…σ(m) are i.i.d. from [n]. (The σ(i) 's are thought of as the locations of balls dropped independently into urns 1…n according to some common distribution, so that, for some threshold t_j, x _j is the indicator of the event that at least t_j balls land in urn j.) We mostly deal with the more general situation in which the σ(i) 's need not be identically distributed, proving results which imply conditional negative association in the i.i.d. case. Some of the results—particularly Lemma 8 on graph orientations—are thought to be of independent interest. We also give a counterexample to a negative correlation conjecture of D. Welsh, a strong version of a (still open) conjecture of G. Farr. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Card shuffling and a transformation on S n

Summary We consider two card shuffling schemes. The first, which has appeared in the literature previously ([G], [RB], [T]), is as follows: start with a deck ofn cards, and pick a random tuplet { 1, 2, , n} ⁿ ; interchange cards 1 andt ₁, then interchange cards 2 andt ₂, etc. The second scheme, which can be viewed as a transformation on the symmetric groupS _n , is given by the restriction of the former shuffling scheme to tuplest which form a permutation of {1, 2,,n}.We determine the bias of each of these shuffling schemes with respect to the sets of transpositions and derangements, and the expected number of fixed points of a permutation generated by each of these shuffling schemes. For the latter scheme we prove combinatorially that the permutation which arises with the highest probability is the identity. The same question is open for the former scheme. We refute a candidate answer suggested by numerical evidence [RB].This work was carried out in part while R.S. was visiting the Institute for Mathematics and its Applications and was partly supported through NSF Grant CCR-8707539.     

Convergence of Point Processes with Weakly Dependent Points

For each n≥1, let {X _j,n }_1≤j≤n be a sequence of strictly stationary random variables. In this article, we give some asymptotic weak dependence conditions for the convergence in distribution of the point process $N_{n}=\sum_{j=1}^{n}\delta_{X_{j,n}}For each n≥1, let {X _j,n }_1≤j≤n be a sequence of strictly stationary random variables. In this article, we give some asymptotic weak dependence conditions for the convergence in distribution of the point process N_n=?_j=1ⁿd_Xj,nN_{n}=\sum_{j=1}^{n}\delta_{X_{j,n}} to an infinitely divisible point process. From the point process convergence we obtain the convergence in distribution of the partial sum sequence S _n =∑ _j=1 ⁿ X _j,n to an infinitely divisible random variable whose Lévy measure is related to the canonical measure of the limiting point process. As examples, we discuss the case of triangular arrays which possess known (row-wise) dependence structures, like the strong mixing property, the association, or the dependence structure of a stochastic volatility model.     

A weak law for normed weighted sums of random elements in rademacher type p banach spaces

For weighted sums Σ_{j = 1}ⁿa_jV_j of independent random elements {V_n, n ≥ 1} in real separable, Rademacher type p (1 ≤ p ≤ 2) Banach spaces, a general weak law of large numbers of the form (Σ_{j = 1}ⁿa_jV_j − v_n)/b_n →^p 0 is established, where {v_n, n ≥ 1} and b_n → ∞ are suitable sequences. It is assumed that {V_n, n ≥ 1} is stochastically dominated by a random element V, and the hypotheses involve both the behavior of the tail of the distribution of |V| and the growth behaviors of the constants {a_n, n ≥ 1} and {b_n, n ≥ 1}. No assumption is made concerning the existence of expected values or absolute moments of the {V_n, n >- 1}.     

The mean number of sites visited by a pinned random walk

This paper concerns the number Z _n of sites visited up to time n by a random walk S _n having zero mean and moving on the d-dimensional square lattice Z ^d . Asymptotic evaluation of the conditional expectation of Z _n given that S ₀ = 0 and S _n = x is carried out under 2 + δ moment conditions (0 ≤ δ ≤ 2) in the cases d = 2, 3. It gives an explicit form of the leading term and reasonable estimates of the remainder term (depending on δ) valid uniformly in each parabolic region of (x, n). In the case x = 0 the problem has been studied for the simple random walk and its analogue for Brownian motion; the estimates obtained here are finer than or comparable to those found in previous works. Supported in part by Monbukagakusho grand-in-aid no. 15540109.