A RANDOM WALK ON THE ROOK PLACEMENTS ON A FERRERS BOARD

by Phil Hanlon^{1}

Department of Mathematics University of Michigan Ann Arbor, MI 48109–1003

There are many positive ways in which Dominique Foata has impacted our Combinatorics community. Foremost are his fundamental scholarly contributions, many of them breaking new ground or setting directions for the future. Just as important has been his support of students and colleagues. I’ve had the pleasure of visiting Dominique twice in Strasbourg and each time have been struck by his enthusiasm for, and interest in the work of others. I’m pleased to have the opportunity to contribute to this special issue in his honor.

\underline{Abstract}: Let B be a Ferrers board, i.e., the board obtained by removing the Ferrers diagram of a partition from the top right corner of an n × n chessboard. We consider a Markov chain on the set R of rook placements on B in which you can move from one placement to any other legal placement obtained by switching the columns in which two rooks sit. We give sharp estimates for the rate of convergence of this Markov chain using spectral methods. As part of this analysis we give a complete combinatorial description of the eigenvalues of the transition matrix for this chain. We show that two extremes cases of this Markov chain correspond to random walks on groups which are analyzed in the literature. Our estimates for rates of convergence interpolate between those two results.

1 Work partially supported by the National Science Foundation, the University of Strasbourg and a Guggenheim Fellowship.

\underline{Section 1}: Background

In a 1970 paper, Foata and Schützenberger [FS] consider rook polynomials of Ferrers boards. A Ferrers board is an n×n board with the Ferrers diagram of a partition removed from the Northeast corner. In that paper they show that a minimal set of representatives of Ferrers boards up to rook equivalence is given by those where the partition removed has distinct parts.

In a series of papers [GJW 1-4], Goldman, Joichi and White establish elegant enumerative results concerning rook polynomials of Ferrers boards. We recall some of these results in Section 2.

In this paper we study a Markov chain whose states correspond to rook placements on a fixed Ferrers board B. A step in this Markov chain is taken as follows. Suppose we are at a state α corresponding to a placement of rooks on B. Let S_{α} be the multiset consisting of all placements of rooks on B that are obtained from α by switching the columns in which two rooks are contained. We allow a column to switch with itself so α occurs in S_{α} with multiplicity n. In our Markov chain we move from α to each state in S_{α} with probability |S_{α}|^{−1}.

We give a combinatorial description of the eigenvalues (and their multiplicities) of the transition matrix of this Markov chain. A special case of this result agrees with a special case of an interesting recent result of Hozo [H] on the spectrum of the Laplacian of the Koszul complex for certain nilpotent Lie algebras. We use this information to give sharp estimates for the rate of convergence of this Markov chain to its stationary distribution in some cases.

The analysis of this Markov chain is related to recent results concerning random walks on groups (see [D] for an overview). Perhaps the earliest sharp rates of convergence for such random walks were given by Diaconis and Shahshahani [DS1] in 1981 who studied the walk by random transpositions on the symmetric group. They show that this walk converges to its stationary distribution after \frac{1}{2}n log n steps (a precise statement of their result appears in Section 5).

Diaconis and Shahshahani have applied a similar analysis to the natural random walk on the hypercube ℤ_{2}^{n−1}. In a 1987 paper [DS2], they show that \frac{1}{4}n log n steps are necessary and sufficient for convergence to the uniform distribution. The exact asymptotics of the total variation distance was worked out in a 1991 paper of Diaconis, Graham, and Morisson [DGM].

The main result in this paper interpolates between the two cases S_{n} and ℤ_{2}^{n−1} described above. But unlike these two extreme cases, the author knows of no group structure (or association scheme structure,) that can be used to analyze the spectrum of the transition matrix. Nevertheless, the final results give a characterization of the spectrum of the transition matrix which neatly interpolates between the representation-theoretic characterizations in the two extreme cases.

Some comments on notation. All tensor products are over the complex numbers unless otherwise specified. At various times, when considering the permutation representation of a group G on a set S, we will sometimes abuse notation by letting S also denote the vector space with basis consisting of the elements of S. Lastly, there will be cases in this work when we consider left-modules, other times when we consider right-modules and still other times when we consider two-sided modules. The situation will be clear in every case from context. We will leave it to the reader to determine in each instance which sort of module is being discussed.

This work was carried out when the author was a Visiting Professor at the Université de Strasbourg. The author wishes to thank Dominique Foata, Persi Diaconis, Volker Strehl and Chuck Weibel for helpful conversations during the preparation of this manuscript.

\underline{Section 2}: \underline{b}-Regular Permutations

Let \underline{b}=(b_{1}, …, b_{n}) be a sequence of positive integers each taken from \{1, 2, …, n\}. A permutation α=a_{1}a_{2} … a_{n} is \underline{b}-regular if a_{i} ≥ b_{i} for all i. We let R_{n}(\underline{b}) denote the set of \underline{b}-regular permutations in S_{n}. Usually we will think of n as having a fixed value and we will write R(\underline{b}) instead of R_{n}(\underline{b}).

We say that α and γ in R(\underline{b}) are neighbors if they differ by a transposition. Of course this is a reflexive relation on R(\underline{b}) and so determines a graph G(\underline{b}) whose vertices are the elements of R(\underline{b}) with two vertices adjacent if they are neighbors. We are going to consider the random walk on this graph (in the usual sense).

Note that (b_{1}, …, b_{n}) simply restricts the positions in which a given number can be placed. So if \underline{b} = (b_{1}, …, b_{n}) and \underline{b}′ = (b_{α1}, …, b_{αn}) differ by a permutation then G(\underline{b}) and G(\underline{b}′) are isomorphic as graphs. From the point of view of the random walk on G(\underline{b}) the order of the numbers b_{1}, …, b_{n} is unimportant.

We will henceforth assume that the numbers b_{1}, …, b_{n} are written in weakly increasing order.

We now catalogue some combinatorial properties of the sets R(\underline{b}) and the graphs G(\underline{b}). It is straightforward to see that R(\underline{b}) is empty if b_{i} > i for any i. So in the next theorem we will assume that 1 ≤ b_{1} ≤ b_{2} ≤ … ≤ b_{n} ≤ n and that b_{i} ≤ i for all i.

\underline{Proposition 2 .1}: Let \underline{b} = (b_{1}, …, b_{n}) be as above. For π a permutation, let c(π) and i(π) denote the number of cycles and inversions of π respectively. Then

(a) |R(\underline{b})|= ∏_{i=1}^{n}(1 + (i − b_{i}))

(b) ∑_{π∈R(\underline{b})} q^{c(π)}= ∏_{i=1}^{n}(q + (i − b_{i}))

(c) ∑_{π∈R(\underline{b})} q^{i(π)}= ∏_{i=1}^{n} \frac{(1−q^{i+1−b_{i}})}{(1−q)}

(d) The graph G(\underline{b}) is regular of degree ∑_{i=1}^{n} (i − b_{i})= \binom{n}{2} − ∑_{i=1}^{n}(b_{i} − 1).

\underline{Proof}:

Part (a) follows immediately from either (b) or (c). Both (b) and (c) are proved in various places in the literature (for example [GJW1-4]). We will prove (d).

Fix α = a_{1} … a_{n} in R(\underline{b}). We will count the neighbors of α in G(\underline{b}). Let N_{i} denote the set of neighbors obtained from α by interchanging a_{i} with some a_{j} where j < i. There are (n + 1) − b_{i} numbers x in the set {a_{1}, …, a_{n}} which satisfy x ≥ b_{i}. Since b_{i} ≤ b_{i+1} ≤ … ≤ b_{n}, each of a_{i}, a_{i+1}, …, a_{n} are greater than or equal to b_{i}. So there are (n + 1) − b_{i} − (n − i + 1) = i − b_{i} numbers a_{j} with j < i and a_{j} ≥ b_{i}. This shows that |N_{i}| = i − b_{i} which completes the proof.

\underline{Section 3}: Examples In this section we will discuss some special cases that arise by varying the sequence \underline{b}.

\underline{Example 1}: Suppose first that b_{i} = i for some i ≥ 2. Since the sequence \underline{b} weakly increases this implies that b_{j} ≥ i for all j ≥ i. So, if α = a_{1}a_{2} … a_{n} is in R_{n}(\underline{b}) then

{a_{1}, …, a_{i−1}} = {1, 2, …, i − 1} and {a_{i}, …, a_{n}} = {i, i + 1, …, n}.

There is a natural bijection φ between R_{n}(\underline{b}) and R_{i−1}(\underline{c}) × R_{n−i+1}(\underline{d}) where \underline{c}=(b_{1}, …, b_{i−1}) and \underline{d}=(b_{i} − (i − 1), …, b_{n} − (i − 1)).

Our goal in this paper is to study the Markov chain on G_{n}(\underline{b}) described earlier. In the case where b_{i} = i, the transition matrix for this Markov chain is easily seen to be the tensor product of the transition matrices for the corresponding chains on G_{i−1}(\underline{c}) × G_{n−i+1}(\underline{d}). So the random walk on R_{n}(\underline{b}) is put together in a simple way from two smaller random walks.

Amongst sequences \underline{b} with b_{i} < i for all i ≥ 2 there are two extreme cases - one where the numbers in the sequence \underline{b} are as large as possible and one where the numbers in \underline{b} are as small as possible.

\underline{Example 2}: Suppose (b_{1}, …, b_{n}) = (1, 1, …, 1).

This case is very familiar. The set R_{n}(\underline{b}) is all of S_{n} and the Markov chain on G_{n}(\underline{b}) is the well-studied random transposition walk on the symmetric group (see [DS1]).

\underline{Example 3}: Suppose (b_{1}, …, b_{n}) = (1, 1, 2, …, n − 1).

Again this case is very familiar, although it takes some work to recognize it given its present formulation. For α = a_{1}a_{2} … a_{n} in R_{n}(\underline{b}) let E(α) denote the set of indices i such that a_{i} = i − 1. So E(α) ⊆ {2, 3, …, n}.

\underline{Claim 1}: Given a subset S ⊆ \{2, 3, …, n\}, there is exactly one α = a_{1}a_{2} … a_{n} in R_{n}(\underline{b}) satisfying E(α) = S.

\underline{Proof}: We prove this by induction on n, the result being easy to check in the base case n = 2.

Assume the result holds for n − 1 and consider a set S ⊆ {2, 3, …, n}.

\underline{Case 1}: n ∉ S.

By our induction hypothesis, there is a unique α′ = a_{1}a_{2} … a_{n−1} in R_{n−1}(b_{1}, …, b_{n−1}) satisfying E(α′) = S. Let α = a_{1}a_{2} … a_{n−1}n. Clearly E(α) = S. Moreover, if γ = c_{1}c_{2} … c_{n} satisfies E(γ) = S then c_{n} = n (since n ∉ E(γ)), and E(c_{1}c_{2} … c_{n−1}) = S. The uniqueness of α′ implies that γ = α and this completes the induction step in this case.

\underline{Case 2}: n ∈ S.

Let S′ = S\n so S′ ⊆ {2, 3, …, n − 1}. By our induction hypothesis there exists exactly one α′ in R_{n−1}(b_{1}, …, b_{n−1}) satisfying E(α′) = S′. Let \overline{α′} be identical to α′ except that n − 1 is replaced by n. Note that E(\overline{α′}) = E(α′) = S′. Now define α to be α = \overline{α′}(n − 1) (in other words append n − 1 to the end of \overline{α′}). Clearly α ∈ R_{n}(\underline{b}) and E(α) = S. This shows existence.

For uniqueness, suppose γ = c_{1} … c_{n} is in R_{n}(\underline{b}) with E(γ) = S. Then c_{n} = n − 1 and \overline{γ′} = c_{1} … c_{n−1} satisfies E(\overline{γ′}) = S\\{n\}. Let γ′ be \overline{γ′} but with n replaced by n − 1. Then E(γ′) = E(\overline{γ′}) = S′ and by the uniqueness of α′ we have γ′ = α′. So γ = α which completes the induction step.

This shows that the elements of R_{n}(\underline{b}) are naturally identified with the subsets of {2, 3, …, n}. We will further identify the subsets of {2, 3, …, n} with the vertices of the (n − 1) dimensional hypercube C_{n−1} = {0, 1}^{n−1} in the obvious way. S ⊆ {2, 3, …, n} is identified with the vector (ε_{1}, …, ε_{n−1}) given by ε_{i} = \{ \begin{matrix}1 & if i + 1 ∈ S \\ 0 & if i + 1 ∉ S \end{matrix} \underline{Claim 2}: Let α and γ be in R_{n}(\underline{b}) and let ε and ρ be the corresponding vertices in C_{n−1}. Then α and γ are adjacent in G_{n}(\underline{b}) if and only if ε and ρ are adjacent in C_{n−1}.

\underline{Proof}: The proof is by induction on n. The result is easy to check in the base case n = 2. Assume the result is true for n−1 and let α and γ be elements of R_{n}(\underline{b}) with α = a_{1}a_{2}...a_{n} and γ = c_{1}c_{2}...c_{n}.

\underline{Case 1}: a_{n} = c_{n} = n.

Let α′ = a_{1}...a_{n−1} and γ′ = c_{1}...c_{n−1}. Note that ε = (ε′, 0) and ρ = (ρ′, 0) where ε′ and ρ′ are the elements in H_{n−2} corresponding to α′ and γ′ respectively.

Note that α and γ are adjacent in G_{n}(\underline{b}) if and only if α′ and γ′ are adjacent in G_{n−1}(\underline{b}). By our induction hypothesis, α′ and γ′ are adjacent if and only if ε′ and ρ′ are adjacent in H_{n−2} which happens if and only if ε and ρ are adjacent in H_{n−1}.

\underline{Case 2}: a_{n} = c_{n} = n − 1.

This is a similar argument to Case 1.

\underline{Case 3}: a_{n} = n − 1 and c_{n} = n.

Let α′ = a_{1}a_{2} … a_{n−1} and let \overline{α′} be α′ but with n replaced by n − 1. Let γ′ = c_{1} … c_{n−1}. Note that α and γ are adjacent in G_{n}(\underline{b}) if and only if γ is obtained from α by interchanging the numbers n and n − 1 if and only if \overline{α′} = γ′.

Also note that ε ends in 1 and ρ ends in 0. So ε and ρ are adjacent in H_{n−1} if and only if their first n − 2 coordinates are identical, if and only if \overline{α′} = γ′.

\underline{Case 4}: a_{n} = n and c_{n} = n − 1.

This is identical to Case 3. This completes the induction step.

This shows that the graph G_{n}(\underline{b}) has the structure of the (n − 1)-cube.

\underline{Section 4}: The Random Walk on G_{n}(\underline{b})

In this section we will begin the study of the random walks on G_{n}(\underline{b}). This random walk is described by a Markov chain whose states are R_{n}(\underline{b}). Roughly speaking, to take a step in this Markov chain you do the following. You are at a state α = a_{1}...a_{n} which you think of as being the cards a_{1}...a_{n} laid out in front of you from left to right. Put your left hand down on a card a_{i} chosen at random. Put your right hand down on a card a_{j} (perhaps the same card a_{i}) chosen at random. If you can switch the two cards a_{i} and a_{j} and remain in the set R_{n}(\underline{b}) then do so. That is your step in the Markov chain. However, if you leave the set R_{n}(\underline{b}) by switching a_{i} and a_{j} then go back and pick two new cards. Continue this until you finally pick a pair that you can switch.

Let △ = ∑_{i}(i − b_{i}). We know that G_{n}(\underline{b}) is regular of degree △. Suppose you are at a

vertex α in the Markov chain described above. If γ is a neighbor of α in G_{n}(\underline{b}) then there are two ways to pick the pair whose interchange takes you from α to γ. There are n ways to remain at α. So the transition matrix for our Markov chain is

< 4.1 >  \frac{1}{n + 2△}(n I + 2 U) = T

where U is the adjacency matrix of G_{n}(\underline{b}).

In this section we will determine the spectrum of U hence (by < 4.1 >) the eigenvalues of T and their multiplicities.

It is worth pointing out that our Markov chain is primitive because there is a nontrivial probability of remaining at each state. Without a non-zero staying probability, the Markov chain would have period two. You would be in states which are indexed by permutations with the same sign as your starting state after an even number of steps and opposite sign after an odd number of steps.

\underline{Definition 4.2}: Let \underline{b} = (b_{1}, b_{2}, … b_{n}) be a sequence with 1 ≤ b_{1} ≤ b_{2} ≤ … ≤ b_{n} ≤ n and b_{i} ≤ i for all i, and let \underline{n} denote the set \{1, 2, …, n\}. We say that u, v ∈ \underline{n} are left-equivalent if b_{u} = b_{v}. Let L_{1}, …, L_{s} denote the left-equivalence classes of \underline{n} ordered so that the numbers in L_{i} are less than the numbers in L_{j} whenever i is less than j.

We say that u, v ∈ \underline{n} are right-equivalent if for some i, b_{i} ≤ u ≤ v < b_{i+1}(where b_{n+1} is defined to be n + 1). Let R_{1}, …, R_{s} be the right-equivalence classes ordered so that the numbers in R_{i} are less than the numbers in R_{j} whenever i is less than j.

It is straightforward to check that the number of left-equivalence classes is the same as the number of right-equivalence classes. Also the right-equivalence classes are described easily in terms of the sequence of \underline{b} by: R_{i} = \{b_{i}, b_{i} + 1, …, b_{i+1} − 1\}.

For A a subset of \underline{n} we let Sym(A) denote the group of all permutations of \underline{n} which fix every number outside A. So, Sym(A) ≅ S_{|A|}. In terms of this notation, define the groups L and R by:

\begin{aligned}L & = Sym(L_{1}) × Sym(L_{2}) × … × Sym(L_{s}) ≤ S_{n} \\ R & = Sym(R_{1}) × Sym(R_{2}) × … × Sym(R_{s}) ≤ S_{n}. \end{aligned}

We will think of L and R as acting on ℂS_{n} by the left-regular representation and the right-regular representation respectively.

From the definitions of L and R, it is straightforward to verify that they each preserve the set R_{n}(\underline{b}) and that the linear transformation U commutes with the actions of L and R. Since the actions of L and R commute, we have an action of the group G

G = L × R

on the set R_{n}(\underline{b}) which commutes with the action of U. The main theorem in this section will describe the eigenvalues of U and the G-module structure of the corresponding eigenspaces.

\underline{Definition 4.3}: A \underline{b}-partition β = (λ_{1}, μ_{1}, λ_{2}, μ_{2}, …, λ_{s}) is a sequence of partitions such that:

1) λ_{i} ⊇ μ_{i} ⊆ λ_{i+1} for all i = 1, 2, …, s − 1

2) |λ_{i}/μ_{i}| = |R_{i}| for all i = 1, 2, …, s (where μ_{s} = ∅)

3) |λ_{i+1}/μ_{i}| = |L_{i+1}| for all i = 0, 1, …, s − 1 (where μ_{0} = ∅).

Given a \underline{b}-partition β, a an up-down tableau of type \underline{b} and shape β (or \underline{b}-tableau of shape β, for short) is a sequence of partitions (Ferrers diagrams) τ = (∅ = τ_{0}, τ_{1}, τ_{2}, τ_{3}, ..., τ_{2n} = ∅) such that each τ_{i} is obtained from τ_{i−1} by either adding or subtracting a box and such that the τ_{i}’s initially increase in size until they reach λ_{1}, then decrease in size until they reach μ_{1}, then increase in size until they reach λ_{2}, etc. Let P (\underline{b}) denote the collection of \underline{b}-partitions.

We now pause to do some examples.

\underline{Example 4.4}: Let \underline{b} = (1, 1, 1, 2, 4). The sets R_{i} and L_{i} are given below:

L_{1} = {1, 2, 3}  R_{1} = {1}
L_{2} = {4}  R_{2} = {2, 3}
L_{3} = {5}  R_{3} = {4, 5}

A typical \underline{b}-partition β is: β = (21, 1^{2}, 1^{3}, 1, 2)

A \underline{b}-tableau of shape β is given by τ = (∅, 1, 1^{2}, 21, 1^{2}, 1^{3}, 1^{2}, 1, 2, 1, ∅)

\underline{Example 4.5}: Let \underline{b} = (1, 1, 2, 2). In this case

L_{1} = {1, 2}  R_{1} = {1}
L_{2} = {3, 4}  R_{2} = {2, 3, 4}

There are 6 \underline{b}-partitions which are listed below. To the right of each β ∈ P (\underline{b}) we see a listing of the \underline{b}-tableaux of shape β.

β_{1} = (2, 1, 3)  τ^{(1)} = (∅, 1, 2, 1, 2, 3, 2, 1, ∅)
β_{2} = (2, 1, 21)  τ^{(1)} = (∅, 1, 2, 1, 2, 21, 2, 1, ∅)

τ^{(2)} = (∅, 1, 2, 1, 2, 21, 1^{2}, 1, ∅)
τ^{(3)} = (∅, 1, 2, 1, 1^{2}, 21, 2, 1, ∅)
τ^{(4)} = (∅, 1, 2, 1, 1^{2}, 21, 1^{2}, 1, ∅)
β_{3} = (2, 1, 1^{3})  τ^{(1)} = (∅, 1, 2, 1, 1^{2}, 1^{3}, 1^{2}, 1, ∅)
β_{4} = (1^{2}, 1, 3)  τ^{(1)} = (∅, 1, 1^{2}, 1, 2, 3, 2, 1, ∅)
β_{5} = (1^{2}, 1, 21)  τ^{(1)} = (∅, 1, 1^{2}, 1, 2, 21, 2, 1, ∅)
τ^{(2)} = (∅, 1, 1^{2}, 1, 2, 21, 1^{2}, 1, ∅)
τ^{(3)} = (∅, 1, 1^{2}, 1, 1^{2}, 21, 2, 1, ∅)
τ^{(4)} = (∅, 1, 1^{2}, 1, 1^{2}, 21, 1^{2}, 1, ∅)
β_{6} = (1^{2}, 1, 1^{3})  τ^{(1)} = (∅, 1, 1^{2}, 1, 1^{3}, 1^{2}, 1, ∅)

Note that the total number of \underline{b}-tableaux is 12 which is the size of R_{4}(1, 1, 2, 2).

\underline{Example 4.6}: Suppose \underline{b} = (1, 1, …, 1).

Then L_{1} = R_{1} = \{1, 2, …, n\} so G = S_{n} × S_{n}. Each β ∈ P (\underline{b}) consists just of a partition (λ) of n. There are f_{λ}^{2} \underline{b}-tableaux of shape λ (where f_{λ} is the number of standard Young tableaux of shape λ) and so n! \underline{b}-tableaux in total.

\underline{Example 4.7}: Suppose \underline{b} = (1, 1, 2, …, n − 1). In this case

L_{1} = {1, 2}  R_{1} = {1}
L_{2} = {3}  R_{2} = {2}
L_{3} = {4}  R_{3} = {3}
⋮  ⋮
L_{n−1} = {n}  R_{n−1} = {n − 1, n}

A \underline{b}-partition β is a sequence β = (λ_{1}, , λ_{2}, , ..., , λ_{n−1}) where each λ_{i} is either or . Thus the number of \underline{b}-partitions is 2^{n−1}. Given a \underline{b}-partition β, there is a unique \underline{b}-tableau τ of shape β which is obtained from β by adding ∅, at the beginning and , ∅ at the end. So the total number of \underline{b}-tableaux is 2^{n−1} which once again agrees with the size of R_{n}(\underline{b}).

We will need a fact from the representation theory of the symmetric groups which is a slight generalization of a well-known result. For the moment let W = ℂS_{n}. Then W can be considered as a right S_{n}-module via the right-regular representation and as a left S_{n}-module via the left-regular representation. Moreover these two actions of S_{n} commute so we get an action of the direct product S_{n} × S_{n}. A well-known result (see [F]) gives a decomposition of W into S_{n} × S_{n} irreducibles:

< 4.8 >  ℂS_{n} ≅ ⨁ ; λ ⊢ nV [λ] ⊗ V [λ]

where V [λ] is the irreducible for S_{n} indexed by λ.

We consider a more general situation. Let 0 ≤ m ≤ n and let μ be a partition of m. Consider the vector space Ŵ = V [μ] ⊗_{ℂ} ℂS_{n}. Let H denote the symmetric group on the letters [m + 1, ..., n]. If v ∈ V [μ], π ∈ S_{m}, α ∈ S_{n} and σ ∈ H then

v ⊗ σ(πα) = v ⊗ π(σα).

So there is a well-defined left-action of H on the induction

W = V [μ] ⊗_{ℂS_{m}} ℂS_{n}.

Of course W is also a right S_{n}-module and the actions of H and S_{n} commute. We need the following statement about the decomposition of W as an (H × S_{n})-module.

\underline{Proposition 4.9}: As an (H × S_{n})-module, W is isomophic to

W ≅ ⊕_{{λ⊢n \atop μ⊆λ}} V [λ/μ] ⊗ V [λ].

\underline{Proof}: Let λ be a partition of n. If we restrict V [λ] to S_{m} × H and apply Frobenius Reciprocity we have

V [λ] ↓_{S_{m}×H}^{S_{n}}= ⨁_{α,β} g_{αβλ}V [α] ⊗ V [β]

So as a left H-module,

V [μ] ⊗_{ℂS_{m}} V [λ] = ⨁_{β} g_{μβλ}V [β] = V [λ/μ].

The result now follows from equation 4.8.

We are ready now to state our first main theorem which gives a decomposition of R_{n}(\underline{b}) as a G-module.

\underline{Theorem 4.10}: The vector space R_{n}(\underline{b}) is isomorphic to a direct sum of G-invariant subspaces R_{n}(β) for β ∈ P (\underline{b}). Given β = (λ_{1}, μ_{1}, λ_{2}, μ_{2}, ..., μ_{s−1}, λ_{s}):

(1) As a module for G = Sym(L_{1}) × ... × Sym(L_{s}) × Sym(R_{1}) × ... × Sym(R_{s})

R_{n}(β) ≅ V_{1} ⊗ ⋯ ⊗ V_{s} ⊗ W_{1} ⊗ ⋯ ⊗ W_{s}

where V_{i} is the skew Specht module V [λ_{i}/μ_{i−1}] for Sym(L_{i}) and W_{i} is the skew Specht module V [λ_{i}/μ_{i}] for Sym(R_{i}). As usual we are using the convention μ_{o} = μ_{s} = ∅.

(2) The dimension of R_{n}(β) is equal to the number of \underline{b}-tableaux of shape β.

\underline{Proof}: The proof will be by induction on s. We consider a sequence \underline{b} = (b_{1}, …, b_{n}) with s L_{i} and R_{i}-sets.

\underline{Case 1}: s = 1

In this case, b_{i} = 1 for all i ≤ n, so R_{n}(\underline{b}) = ℂS_{n} and G = S_{n}×S_{n}. The decomposition of ℂS_{n} as a G-module is given by < 4.8 >

R_{n}(\underline{b}) = ⨁_{λ⊢n} V [λ] ⊗ V [λ].

In this case the \underline{b}-partitions consist just of a partition of n, and so we take R_{n}(β) for β = (λ) to be the summand V [λ] ⊗ V [λ]. This proves (1).

The dimension of V [λ] is the number of standard Young tableaux of shape λ. There is a simple bijection between standard Young tableaux of shape λ and sequences of partitions which begin with the empty partition and increase by one square at each step until λ is reached. So f_{λ}^{2}, the dimension of R_{n}(β), is the number of \underline{b}-tableaux of shape β = (λ). This proves (2).

\underline{Case 2}: s > 1.

In this case b_{n} > 1 and we can write L_{s} and R_{s} as L_{s} = {a, a + 1, …, n} and R_{s} = {b_{n}, b_{n+1}, …, n} for some a > 1. By the definitions of the L_{i} and R_{i} we see that

b_{a−1} < b_{a} = b_{a+1} = … = b_{n}.

Since b_{n} = b_{a} ≤ a this implies that L_{s} ⊆ R_{s}.

Let \underline{b}′ = (b_{1}, …, b_{a−1}), let L′_{i} and R′_{i} be the corresponding L and R sets for \underline{b}′ and let s′ be the number of L′_{i}. Note that

< 4.11 >  s′ = s − 1
L′_{i} = L_{i} for 1 ≤ i ≤ s − 1
R′_{i} = R_{i} for 1 ≤ i ≤ s − 2
R′_{s−1} = R_{s−1} ∪ (R_{s} \ L_{s}).

In keeping with this notation we will let G′ be the automorphism group associated with \underline{b}′, i. e.,

G′ = Sym(L′_{1}) × … × Sym(L′_{s−1}) × Sym(R′_{1}) × … × Sym(R′_{s−1}).

We will also need to consider a subgroup Ĝ of G′ namely

Ĝ = Sym(L′_{1}) × … × Sym(L′_{s−1}) × Sym(R′_{1}) × … × (Sym(R_{s−1}) × Sym(R_{s} \ L_{s})).

(recall from < 4.11 > that R′_{s−1} = R_{s−1} ∪ (R_{s} \ L_{s})).

Let Z denote the collection of injective mappings from {1, 2, …, n − a + 1} into {b_{n}, b_{n} + 1, …, n} (which is nonempty sice b_{n} ≤ a), written as sequences. For each Z = (Z_{1}, …, Z_{n−a+1}) ∈ Z let R_{n}(\underline{b}; Z) be the subspace of R_{n}(\underline{b}) spanned by all permutations that have the sequence Z in their last n − a + 1 positions. Since b_{a} = b_{a+1} = … = b_{n}, every permutation must end with some element of Z, i. e.,

R_{n}(\underline{b}) = ⨁_{Z∈Z} R_{n}(\underline{b}; Z)

Fix a sequence Z ∈ Z and let \overline{Z} denote the set of numbers that appear in Z. Then |\overline{Z}| = |L_{s}| = n − a + 1 so there is a permutation π_{Z} ∈ S_{n} which sends the set R_{s} \ L_{s} to the set R_{s} \ \overline{Z} and keeps the relative order of the numbers intact.

Define f_{Z} to be the linear map from R_{a−1}(\underline{b}′) to R_{n}(\underline{b}; Z) which sends a permutation σ to the permutation obtained by first right-multiplying σ by π_{Z} then adding the sequence Z on the right. Notationally we will represent this as:

f_{Z}(σ) = (σπ_{Z})Z.

As an example, suppose that \underline{b} = (1, 1, 3, 3, 3, 4, 4). Then s = 3, L_{3} = \{6, 7\} and R_{3} = \{4, 5, 6, 7\}. Thus a = 6, b_{n} = 4, and \underline{b}′ = (1, 1, 3, 3, 3). Let Z = (6, 4). The permutation π_{Z} must send R_{3} \ L_{3} to R_{3} \ \overline{Z} in an order-preserving way so we can choose π_{Z} = (4, 5, 7)(6).

There are four permutations in R_{s}(b′). We see these below along with their images under f_{Z}:

\begin{matrix}σ ∈ R_{a−1}(\underline{b}′) & σπ_{Z} & f_{Z}(σ) = (σπ_{Z})Z \\ 1 2 3 4 5 & 1 2 3 5 7 & 1 2 3 5 7 6 4 \\ 2 1 3 4 5 & 2 1 3 5 7 & 2 1 3 5 7 6 4 \\ 1 2 3 5 4 & 1 2 3 7 5 & 1 2 3 7 5 6 4 \\ 2 1 3 5 4 & 2 1 3 7 5 & 2 1 3 7 5 6 4 \end{matrix}

\underline{Claim 1}: The linear map f_{Z} is an isomorphism between R_{a−1}(\underline{b}′) and R_{n}(\underline{b}; Z).

\underline{Proof}: The map σ → (σπ_{Z})Z is one-to one as a function from ℂS_{a−1} to ℂS_{n}. So it is enough to show that f_{Z}(R_{a−1}(\underline{b}′)) ⊆ R_{n}(\underline{b}; Z) and that f_{Z} maps R_{a−1}(\underline{b}′) onto R_{n}(\underline{b}; Z).

Let σ = c_{1}c_{2} ⋯ c_{a−1} be in R_{a−1}(\underline{b}′). Write (σπ_{Z})Z = d_{1}d_{2} ⋯ d_{n}. For 1 ≤ i ≤ a − 1 we have

b_{i} = b′_{i} ≤ c_{i} ≤ c_{i}π_{Z} = d_{i}.

For a ≤ i ≤ n we have d_{i} ∈ {b_{n}, …, n} so b_{i} = b_{n} ≤ d_{i}. Thus f_{Z}(σ) ∈ R_{n}(b′).

Now let τ = d_{1} … d_{a−1}Z be in R_{n}(\underline{b}; Z). Then τ = f_{Z}(σ) where σ = (d_{1} … d_{a−1})π_{Z}^{−1}. Either d_{i}π_{Z}^{−1} = d_{i} in which case b′_{i} = b_{i} ≤ d_{i} or d_{i}π_{Z}^{−1} ∈ R_{s} \ L_{s} and in this case b′_{i} = b_{i} ≤ b_{a} ≤ d_{i}π_{Z}^{−1}. So σ ∈ R_{a−1}(\underline{b}′) which shows that f_{Z} is onto. This proves Claim 1.

\underline{Claim 2}: As a module for Sym(R_{s}), R_{n}(\underline{b}) is isomorphic to the induction of R_{a−1}(\underline{b}′) from Sym(R_{s} \ L_{s}) to Sym(R_{s}).

\underline{Proof}: Let A denote Sym(R_{s} \ L_{s}) and B denote Sym(R_{s}). Note that the collection {π_{Z} : Z ∈ Z} is a set of coset representatives for A in B. So there is a vector space isomorphism between R_{a−1}(\underline{b}′) ⨂_{A} B and R_{n}(\underline{b}) given by:

ψ(σ ⊗ π_{Z}) = (σπ_{Z})Z.

Let g ∈ B and let Zg = Y. Then g acts on (σπ_{Z})Z by

< 4.12 >  (σπ_{Z})Z · g = ((σπ_{Z})g)Y = (σ · π_{Z}gπ_{Z}^{−1})π_{Y} Y.

From < 4.12 > and the usual construction of induced modules (see [F]) one sees that ψ is a B-equivariant isomorphism which proves Claim 2.

We are now in a position to finish part (1) of Theorem 4.10. By our induction hypothesis, R_{a−1}(\underline{b}′) is isomorphic, as a G′-module, to the direct sum of modules R_{a−1}(β′) for β′ ∈ P (\underline{b}′). Each β′ has the form

β′ = (λ_{1}, μ_{1}, λ_{2}, μ_{2}, …, μ_{s−2}, λ_{s−1})

and the corresponding module R_{a−1}(β′) is isomorphic to the tensor product

V_{1} ⊗ … ⊗ V_{s−1} ⊗ W_{1} ⊗ … ⊗ W_{s−1}

where V_{i} ≅ V [λ_{i}/μ_{i−1}] and W_{i} ≅ V [λ_{i}/μ_{i}]. When we restrict R_{a−1}(β′) to Ĝ we obtain a similar direct sum but this time indexed by sequences

β̂ = (λ_{1}, μ_{1}, …, μ_{s−2}, λ_{s−1}, μ_{s−1})

where μ_{s} ⊆ λ_{s−1} and |λ_{s−1}/μ_{s−1}| = |R_{s−1}| (or equivalently |μ_{s−1}| = |R_{s} \ L_{s}|). The representation of Ĝ on this R_{n}(β̂) is

V_{1} ⊗ … ⊗ V_{s−1} ⊗ W_{1} ⊗ … ⊗ W_{s−2} ⊗ (V [λ_{s}/μ_{s−1}] ⊗ V [μ_{s−1}]).

By Claim 2, R_{n}(β̂) indexes a G-invariant subspace of R_{n}(\underline{b}) which as a G-module is isomorphic to

< 4.13 > V_{1} ⊗ … ⊗ V_{s−1} ⊗ W_{1} ⊗ … ⊗ W_{s−2} ⊗ W_{s−1} ⊗ ind _{Sym(R_{s}\L_{s})}^{Sym(R_{s})}(V [μ_{s−1}]).

But in order to regard < 4.13 > as a G-module it is important to view the right-most tensor factor as a module over Sym(L_{s}) × Sym(R_{s}) where Sym(L_{s}) acts from the left and Sym(R_{s}) acts from the right.

Now applying Proposition 4.9 gives us part (1) of Theorem 4.10.

Part (2) of Theorem 4.10 follows easily from part (1) and the fact that the dimension of V [λ/μ] is the number of standard Young tableaux of shape λ/μ.

We now return to the transition matrix U encountered in our random walk on R_{n}(\underline{b}).

\underline{Definition 4.14}: Let β = (λ_{1}, μ_{1}, …, μ_{s−1}, λ_{s}) be in P (\underline{b}). Define the indicator tableau T (β) to be the tableau whose entry in a square x is the number of skew shapes λ_{i}/μ_{i−1} that contain x. We denote this entry by T_{x}(β).

\underline{Theorem 4.15}: The matrix U preserves the space R_{n}(β). Moreover, U restricted to R_{n}(β) is the scalar

Λ(β) = ∑_{x} T_{x}(β)c_{x}

where c_{x} is the content of x.

\underline{Proof}: The proof will proceed by induction on n. The cases n = 1, 2 are straightforward to verify. Assume the result is true for n − 1 and consider a sequence \underline{b} = (b_{1}, …, b_{n}).

From this point on, our proof will proceed in a series of steps. This argument depends on appropriately ordering our basis for R_{n}(\underline{b}). So we begin with a discussion of this ordering. Whenever we have an N and a sequence γ = (γ_{1}, …, γ_{N}) we will assume that the set R_{N}(γ) is ordered in reverse lexicographic order reading permutations from left to right. In other words, to decide whether α = a_{1}a_{2} … a_{N} comes before δ = d_{1}d_{2} … d_{N} first compare a_{N} to d_{N}. If a_{N} is bigger then α comes first. If a_{N} is smaller then δ comes first. If a_{N} = d_{N} then move on and compare a_{N−1} to d_{N−1}, etc... For example, if \underline{b} = (1, 1, 2) then the appropriate ordering of R_{3}(\underline{b}) is

1 2 3
2 1 3
1 3 2
3 1 2

\underline{STEP 1}: Split the ordered basis R_{n}(\underline{b}) as the disjoint union of R_{n}^{(n)}(\underline{b}) ∪ R_{n}^{(n−1)}(\underline{b}) ∪ … ∪ R_{n}^{(b_{n})}(\underline{b}) where R_{n}^{(i)}(\underline{b}) consists of all permutations in R_{n}(\underline{b}) that have i in their final position. Note that each set R_{n}^{(i)}(\underline{b}) is identical (as an ordered set) to a copy of R_{n−1}(\underline{b}′) where \underline{b}′ = (b_{1}, …, b_{n−1}).

\underline{STEP 2}: Write the linear transformation U as L + M where L_{α,γ} = 0 unless the last positions of α and γ are identical and where M_{α,γ} = 0 if the last positions of α and γ are identical. To put this another way, L represents all switches in which neither occurs in the last position and M represents all switches in which one of the two elements occurs in the last position.

It is easy to see that L, in terms of the decomposition of the ordered basis R_{n}(\underline{b}) given in STEP 1, is block diagonal with all blocks equal to the matrix U′, the matrix corresponding to U in the case \underline{b}′ = (b_{1}, …, b_{n−1}).

\underline{STEP 3}: L and M commute.

We will compare M · L(α) to L · M(α). M · L(α) is a sum of permutations obtained by first switching a_{i} and a_{j} where i < j < n and then switching a_{ℓ} and a_{n} where ℓ < n. If ℓ is distinct from i and j then the same term occurs in L · M(α). Suppose now that ℓ = j. Then the resulting permutation looks like

i  j  n
↓  ↓  ↓
a_{1} … a_{n} … a_{i} … a_{j}

The same term occurs in L · M(α) when we first switch a_{j} with a_{n} then we switch a_{i} with a_{n} (this second switch is included in L because a_{n} is in position j after the first switch).

The only subtlety is when ℓ = i. The permutation in M · L(α) which results from switching a_{i} with a_{j} then a_{i} with a_{n} is

i  j  n
↓  ↓  ↓
a_{1} … a_{j} … a_{n} … a_{i}

The corresponding term in L · M(α) is where we first switch a_{i} with a_{n} then switch a_{n} with a_{j}. But we need to be sure that the first switch can be made, i. e. , that a_{n} ≥ b_{i}. However this is clear since a_{n} started in position n so a_{n} ≥ b_{n} ≥ b_{i}.

This shows that every term which occurs in M · L(α) also occurs in L · M(α). A similar argument shows that every term occuring in L · M(α) also occurs in M · L(α) which completes STEP 3.

\underline{STEP 4}: We now apply our induction hypothesis to the sequence \underline{b}′ = (b_{1}, …, b_{n−1}). Let β′ be a \underline{b}′-partition which ends in some partition λ′ of n − b_{n−1}. Let τ′ = (∅, τ_{1}, τ_{2}, …, λ′) be an up-down tableau of type \underline{b}′ and shape β′, but truncated at the (last) position where λ′ occurs. Let W be the corresponding subspace of ℂR_{n−1}(\underline{b}′) which is isomorphic to S^{λ′} as an S_{n−b_{n−1}}-module and on which U′ acts as the scalar Λ(β′). Recall that S_{n−b_{n−1}} acts on R_{n−1}(\underline{b}′) by permuting the numbers b_{n−1}, b_{n−1} + 1, …, n − 1. Let S_{n−b_{n}} denote the subgroup which permutes b_{n}, b_{n} + 1, …, n − 1.

Restrict W to S_{n−b_{n}} and let μ be a partition of n − b_{n} contained in λ′. The number of occurrences of S^{μ} in W is exactly the number of chains of partitions which begin at λ′ and end at μ in which each partition is obtained from the previous one by removing a square. So we can think of the S^{μ}-isotypic component of W as being the direct sum of copies of S^{μ}, each copy indexed by such a chain from λ′ down to μ. Let V be the copy of S^{μ} in W indexed by one such chain.

(\overbrace{∅, τ_{1}, τ_{2}, …, λ′}^{τ′}, μ_{1}, …, μ = μ_{b_{n}−b_{n−1}})
↕ ↕
ℂR_{n−1}(\underline{b}′) ≥ W ≥ V

\underline{STEP 5}: Recall that V is a subspace of ℂR_{n−1}(\underline{b}′). For each i = b_{n}, b_{n} + 1, …, n, let V^{(i)} denote the copy of V obtained from the identification of R_{n}^{(i)}(\underline{b}) with R_{n−1}(\underline{b}′).

From our choice of V in STEP 4 we have that U′ acts like the scalar Λ(β′) on V. Hence L acts like the scalar Λ(β′) on each V^{(i)}.

\underline{STEP 6}: Let X = V^{(b_{n})} ⊕ V^{(b_{n}+1)} ⊕ … ⊕ V^{(n)}. One important observation about X is that it is isomorphic as an S_{n+1−b_{n}}-module (where S_{n+1−b_{n}} permutes b_{n}, b_{n} + 1, …, n) to the induction from S_{n−b_{n}} to S_{n+1−b_{n}} of V. This follows easily by the construction of the sets R_{n}^{(i)}(\underline{b}). It follows that X is isomorphic as an S_{n+1−b_{n}}-module to the direct sum of irreducibles S^{λ} where λ contains μ, each S^{λ} occurring with multiplicity 1.

Next we examine the transformation M. Recall that M accounts for all possible switches which involve the entry in the n^{th} position. So M is left multiplication by the Murphy element \underline{m} in S_{n+1−b_{n}},

\underline{m} = (b_{n}, n) + (b_{n} + 1, n) + … + (n − 1, n).

It is well-known that the Murphy element acts like a scalar on each irreducible S^{λ} occurring in ind_{S_{n−bn}}^{S_{n+1−bn}} (S^{μ}) and that scalar is just the content of the square λ/μ. So M acts like the scalar on j − i on S^{λ} where λ/μ is the square in row i and column j. Also L acts like the scalar Λ(β′) on each V^{(i)} hence on X, so L+M = U acts like the scalar Λ(β) = Λ(β′)+j−i on S^{λ} where this action is being parametrized by the truncated up-down tableau τ of type \underline{b} and shape β given by

τ = (\overbrace{∅, τ_{1}, τ_{2}, …, λ′}^{τ′}, μ_{1}, …, \overbrace{μ_{b_{n}−b_{n−1}}}^{μ}, λ).

This completes the proof of the theorem.

Before listing corollaries of this theorem we do an example. Let \underline{b} = (1, 1, 2, 2). The permutations in R_{n}(\underline{b}) listed according to our canonical ordering are:

1 2 3 4
2 1 3 4
1 3 2 4
3 1 2 4
1 2 4 3
2 1 4 3
1 4 2 3
4 1 2 3
1 3 4 2
3 1 4 2
1 4 3 2
4 1 3 2

The matrix U written with respect to that ordered basis is:

[ \begin{matrix}0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \end{matrix} ]

The symmetric group S_{3} (permuting the numbers 2, 3, 4) acts on R_{4}(\underline{b}) and the matrix U commutes with this action. Theorem 4.13 gives the eigenvalues of U and the decomposition of the corresponding eigenspaces as S_{3}-modules.

The \underline{b}-partitions, the truncated up-down tableaux of type \underline{b}, the indicator tableaux and the eigenvalues in this case are:

β  τ  T (β)  Λ(β)
(2, 1, 3)  (∅, 1, 2, 1, 2, 3)  121  4
(1^{2}, 1, 3)  (∅, 1, 1^{2}, 1, 2, 3)  {111 \atop 1}  2
(2, 1, 21)  (∅, 1, 2, 1, 2, 21)  {12 \atop 1}  1
(1^{2}, 1, 21)  (∅, 1, 1^{2}, 1, 2, 21)  {11 \atop 2}  −1
(2, 1, 21)  (∅, 1, 2, 1, 1^{2}, 21)  {12 \atop 1}  1
(1^{2}, 1, 21)  (∅, 1, 1^{2}, 1, 1^{2}, 21)  {11 \atop 2}  −1
(2, 1, 1^{3})  (∅, 1, 2, 1, 1^{2}, 1^{3})  11 1 1  −2

(1^{2}, 1, 1^{3})  (∅, 1, 1^{2}, 1, 1^{2}, 1^{3})  1 2 1  −4

Reading from this chart we obtain the following list of eigenvalues and S_{3}-decompositions of the corresponding eigenspaces:

eigenvalueΛ  multiplicity  S_{3} − decomposition of the eigenspace
4  1  3
2  1  3
1  4  21 ⊕ 21
−1  4  21 ⊕ 21
−2  1  1^{3}
−4  1  1^{3}

Theorem 4.15 has some interesting corollaries:

\underline{Corollary 4.16}: 1) The eigenvalues of U are integers.

2) The multiplicity of Λ as an eigenvalue is the same as the multiplicity of −Λ, but the S_{n+1−b_{n}} structure of their corresponding eigenspaces differ by tensoring with the sign representation.

\underline{Corollary 4.17}: The cardinality of R_{n}(\underline{b}) is equal to the number of up-down tableaux of type \underline{b}. The multiplicity of Λ as an eigenvalue of U is equal to the number of up-down tableaux τ of type \underline{b} with Λ(τ) = Λ.

\underline{Section 5:} Applications

We can use the spectral information from Section 4 to obtain sharp estimates for the rate of convergence of our Markov chain to the uniform distribution. We will consider two cases and in each one sketch how the results from the previous section apply.

We model our analysis after that given in [D] for the case \underline{b} = (1, 1, …, 1). However several of the bounds given in [D] do not apply directly and must be modified to handle our general case. Details will appear in a subsequent paper containing work which is joint with Persi Diaconis.

The general method goes as follows. First establish that the G_{n}(\underline{b}) has a transitive automorphism group (this makes the starting point of your Markov chain irrelevant). Given that, you have the following upper bound for the total variation distance (see [DS] for a derivation of this bound).

\underline{Lemma 5.1} For α ∈ R_{n}(\underline{b}) let ρ_{α}^{k}(σ) be probability that you are in state σ after k steps in the Markov chain on the graph G_{n}(\underline{b}) from starting state α. Let U be the uniform distribution on R_{n}(\underline{b}). Then ||ρ_{α}^{k} − U|| does not depend on α and an upper bound is given by

||ρ_{α}^{k} − U|| ≤ \frac{1}{2} \{∑_{Λ≠1} Λ^{2k}\}^{\frac{1}{2}}

where the sum over Λ ≠ 1 is over eigenvalues of the transition matrix U.

The results of Section 4 tell us all the eigenvalues that appear in the sum

< 5.2 >  ∑_{Λ≠1} Λ^{2k}

The idea is to carefully analyze the contribution made by a few Λ that dominate the sum and to bound the contribution made by the others. Certainly the second largest eigenvalue will be amongst those that dominate the sum.

The last step is to find a lower bound to ||ρ_{α}^{k} − U|| that agrees with our upper bound. This is accomplished by using an alternative definition of total variation distance, namely

< 5.3 >  ||ρ_{α}^{k} − U|| = max_{A⊆R_{n}(\underline{b})} ∑_{x∈A} |ρ_{α}^{k}(x) − U(x)|.

where the sum is over all subsets A in R_{n}(\underline{b}). If we choose a subset A so that its indicator function has a significant projection onto the eigenspace of some Λ which dominates the sum < 5.2 > then ∑_{x∈A} |ρ_{α}^{k}(x) − U(x)| will be of the same order of magnitude as the upper

bound < 5.2 >. By < 5.3 > this gives a lower bound to total variation distance.

As mentioned above, most of this work will appear in an upcoming paper. Here we will first indicate how to find the second largest eigenvalue and show how that leads to a cut-off value of k in two interesting special cases.

We begin by restating the main result from Section 4 in a friendlier way. Visualize the Ferrers board B from Sec.1 as the n × n grid whose southwest corner is at (0, 0). Hence the northwest corner is at (0, n) and the southeast corner is at (n, 0). In column j of this grid, shade in the top b_{j} − 1 squares. Let P be the path from the northwest corner to the southeast corner which runs along the top of B until the shaded portion is reached, then runs along the southern boundary of the shaded portion and finally along the eastern boundary of B. We view P as a path consisting of 2n steps, each one going one unit to the right or one unit down. The normalization factor n + 2△ is equal to n^{2} minus twice the shaded area.

Theorem 4 states that the eigenvalues of U are indexed by sequences of tableaux, one labelling each point of P, where the tableaux τ_{1} and τ_{2} indexing consecutive points differ by adding a square or subtracting a square depending on whether the corresponding step in P goes to the right or down. The eigenvalues associated to such a sequence is the sum of the contents of the squares added at the right-hand steps.

The eigenvalues associated to a sequence of tableaux depends only on the particular tableaux which occur at the corners of the path P. Let 2s−1 denote the number of corners of P, let γ_{1}, …, γ_{2s−1} be the corners of P and let (u_{i}, v_{i}) denote the coordinates of the corner γ_{i}. It is easy to see that the odd corners γ_{2i−1} point to the northeast whereas the even corners γ_{2i} point to the southwest.

If τ = (∅, τ_{1}, τ_{2}, …, τ_{2n−1}, ∅) is a sequence of tableaux labelling P then the size of the tableau labelling the corner γ_{i} is (u_{i} + v_{i} − n). The eigenvalue of U associated to τ depends only on the subsequence (λ_{1}, μ_{1}, λ_{2}, …, μ_{s−1}, λ_{s}) of τ (following the notation of Sec. 4). Here λ_{i} (μ_{i} resp.) is the element of τ corresponding to the corner γ_{2i−1} (γ_{2i} resp.). According to Theorem 4.15 this eigenvalue is the sum over i of the sum of the contents in λ_{i}/μ_{i−1}. Here i ranges from 1 to s, where μ_{0} is defined to be ∅. The multiplicity of this eigenvalue is a product over i of deg(χ_{λ_{i}/μ_{i−1}}) deg(χ_{λ_{i}/μ_{i}}). The maximum eigenvalue of U is △ and this corresponds to π_{i} being a single row for all i. The second largest eigenvalue occurs when exactly one of the λ_{i} is (u_{2i+1} + v_{2i+1} − n − 1, 1). This eigenvalue is △ − (u_{2i+1} +v_{2i+1} −n) and the corresponding multiplicity is (v_{2i+1} −v_{2i} −1)(u_{2i+1} −u_{2i+2} −1).

We now see how this works in two special cases.

\underline{Case 1}: Let \underline{b} = (1, 1, …, 1, 2, …, 2) where there are n^{α} 1‘s and (n − n^{α}) 2’s. Here α is a fixed element of (0, 1]. In terms of permutations, σ = a_{1} ⋯ a_{n} is in R_{n}(\underline{b}) if and only if 1 occurs in one of the first n^{α} positions. It is straightforward to check that G_{n}(\underline{b}) has a transitive automorphism group and so Lemma 5.1 applies.

There are three corners in the path P, one at (n^{α}, n) the next at (n^{α}, n − 1) and the last at (n, n−1). So P starts at (0, n), goes to the right n^{α} steps, goes down 1, goes to right another n − n^{α} steps and then down n − 1. In this case we have n + 2△ = n^{2} − 2(n − n^{α}). There are two candidates for second largest eigenvalue.

\underline{Eigenvalue} Λ_{1}: This eigenvalue corresponds to (π_{1}, π_{2}, π_{3}) = ((n^{α} −1, 1), (n^{α} −1), (n−1)). The eigenvalue Λ_{1} of T is

1 − \frac{2n^{α}}{n^{2} − 2n + 2n^{α}}

and the multiplicity is n^{α} − 1.

\underline{Eigenvalue} Λ_{2}: This eigenvalue corresponds to (π_{1}, π_{2}, π_{3}) = ((n^{α}), (n^{α} − 1), (n − 2, 1)). This eigenvalue Λ_{2} of T is

1 − \frac{2(n − 1)}{n^{2} − 2n + 2n^{α}}

and the multiplicity is (n − n^{α})(n − 2).

In order to get ∑_{Λ≠1} Λ^{2k} close to 0 we must choose k so that both

< 5.4 >  (n^{α} − 1) (1 − \frac{2n^{α}}{n^{2} − 2n + 2n^{α}} )^{2k} ∼ e^{log(n^{α})+2k log (1− \frac{2n^{α}}{n^{2}} )}
< 5.5 >  (n − n^{α})(n − 2) (1 − \frac{2(n − 1)}{n^{2} − 2n + 2n^{α}} )^{2k} ∼ e^{log(n^{2})+2k log(1− \frac{2}{n})}

both approach 0. To bound < 5.4 > we must have α log(n) = 2k(n^{α−2}), i. e. , k = (\frac{α}{2})n^{2−α} log n. To bound the second sum we require 2 log n = 2k (\frac{2}{n}) , i. e. , k = \frac{1}{2}n log n. For α < 1, the first condition is more restrictive. In our upcoming paper, we will prove the following result:

\underline{Theorem 5.6}: Let \underline{b} = (1^{n^{α}}, 2^{n−n^{α}}) where α is fixed. Let k = (\frac{α}{2}) n^{2−α} log n + cn^{2}. For c > 0 we have

||P^{k} − U|| ≤ \frac{1}{2}e^{−c}

For c < 0, ||P^{k} − U|| is bounded away from 0 by a function of c which is independent of n.

Notice that this matches the result obtained by Diaconis and Shahshahani in the case α = 1. The case α = 0 merits some discussion. As this is set up, the case α = 0 would be \underline{b} = (1, 2, 2, …, 2) which requires 1 to always remain in position 1. So this is the usual random transposition walk on S_{n−1}. The eigenvalue < 5.4 > does not occur and < 5.5 > gives the cut-off k = \frac{1}{2}n log n as follows from the work in [DS]. A more interesting interpolation of the α = 0 case is to consider (1^{ℓ}, 2^{n−ℓ}) where ℓ is bounded. In this case the eigenvalue < 5.4 > does occur with multiplicity (ℓ − 1) and we obtain cut-off at k = 0(n^{2}) which agrees with the statement in Theorem 5.6 up to the constant.

\underline{Case 2}: Let \underline{b} = (1, 1, …, 1, 2, 3, 4, …, n − t + 1) where this sequence begins with t ones. The path up P takes t steps to the right then alternately steps down and to the right until the line x = n is reached and finishes with t steps down. Equivalently, the sequences of tableaux labelling P are obtained by adding t squares, then alternately subtracting and adding a square n − t times, and then subtracting t squares. The second largest eigenvalue of T can be determined using the ideas described earlier in this section. It is 2nt−n−t−t^{2} with multiplicity (n + t − 3). The dominant term in ∑_{Λ≠1} Λ^{2k} is

< 5.7 >  (n + t − 3) (1 − \frac{2t}{n(2t − 1) − t^{2} + t})^{2k}

If t is fixed (relative to n) this gives a cut-off at k = (\frac{2t−1}{4t}) n log n. A special case of this is when t = 2. We have seen that G_{n}(\underline{b}) is the hypercube of dimension n − 1. In this case, the cut-off occurs at \frac{3}{8}n log n. This differs from the \frac{1}{4}n log n derived in [DS]. The difference results from a difference in “staying probabilities”. In our case there is a \frac{1}{3} probability of staying in each state as opposed to a probability of 1/(n + 1) in the case analyzed by Diaconis and Shashahani.

REFERENCES

[D] P.Diaconis, Group Representations in Probability and Statistics, Institute of Math. Statistics - Lecture Notes, Shanti S. Gupta, ed., vol. 11 (1988).

[DGM] P.Diaconis, R.L.Graham, and J.Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions, Random Structures and Algorithms 1 (1989), 21-37.

[DS] P.Diaconis and L.Saloff-Coste, Comparison theorems for reversible Markov chains, Stanford Technical Report (1992).

[DS1] P.Diaconis and M.Shahshahani, Generating a random permutation with random transpositions, Z. Wahr. Verw. Gebiete, vol. 57 (1981), 159-179.

[DS2] P.Diaconis and M.Shahshahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal., vol. 18 (1987), 208-218.

[F] W.Feit, Characters of Finite Groups, W.A.Benjamin (1967).

[FS] D.Foata and M.P.Schützenberger, On the rook polynomials of Ferrers relations, Combinatorial Theory and its Applications II, P.Erdös, A.Renyi, V.Sos, ed., North Holland (1970).

[GJW1] J.R.Goldman, J.T.Joichi and D.E.White Rook theory I - Rook equivalence of Ferrers boards, Proc. AMS 50 (1975), 485-492.

[GJW2] J.R.Goldman, J.T.Joichi, D.L.Reiner and D.E.White, Rook theory II - Boards of binomial type, SIAM J. Appl. Math., vol. 31, no. 4 (1976), 618-633.

[GJW3] J.R.Goldman, J.T.Joichi and D.E.White, Rook theory III - Rook polynomials and the chromatic structure of graphs, J. Comb. Th. B, vol. 25, no. 2 (1978), 135-142.

[GJW4] J.R.Goldman, J.T.Joichi and D.E.White, Rook theory IV - Orthogonal sequences of Rook polynomials, Studies in Appl. Math, vol. 56, no. 3 (1976/77), 267-272.

[H] I.Hozo, The eigenvalues of the Laplacian for the homology of the Lie algebra corresponding to a poset, (preprint).