Séminaire Lotharingien de Combinatoire 70 (2014), Article B70b

CONDITIONED ONE-WAY SIMPLE RANDOM WALK AND COMBINATORIAL REPRESENTATION THEORY

CÉDRIC LECOUVEY, EMMANUEL LESIGNE AND MARC PEIGNÉ

Abstract. A one-way simple random walk is a random walk in the quadrant ℤ_{+}^{n} whose increments are elements of the canonical base. In relation with representation theory of Lie algebras and superalgebras, we describe the law of such a random walk conditioned to stay in a closed octant, a semi-open octant, or other types of semi-groups. The combinatorial representation theory of these algebras allows us to describe a generalized Pitman transformation which realizes the conditioning on the set of paths of the walk. We pursue here a direction initiated by O’Connell and his coauthors, and also developed by the authors.

1. Introduction

Let B = (ε_{1}, …, ε_{n}) be the standard basis of ℝ^{n}. The one-way simple walk is defined as the random walk W = (W_{ℓ} = X_{1} + ⋯ + X_{ℓ})_{ℓ≥1}, where (X_{k})_{k≥1} is a sequence of independent and identically distributed random variables with values in the base B and with common mean vector m. In this paper, we generalize some results due to O’Connell [18, 19] giving the law of the random walk W conditioned to never exit the cone C^{∅} = {x = (x_{1}, …, x_{n}) ∈ ℝ^{n} | x_{1} ≥ ⋯ ≥ x_{n} ≥ 0}^{1}. This is achieved in [18] by considering first a natural transformation 𝔓 derived from the Robinson–Schensted– Knuth correspondence which associates to any path with steps in B a path in the cone C^{∅}, next by checking that the image of the random walk W by this transformation is a Markov chain which has the same law as W conditioned to never exit C^{∅}. The entries of the transition matrix of the Markov chain so obtained can be expressed as quotients of Schur functions (the Weyl characters of 𝔰𝔩_{n}) with variables specialized to the coordinates of m.

One can introduce a similar transformation 𝔓 for a wide class of random walks (X_{1} + ⋯ + X_{ℓ})_{ℓ≥1} for which the variables X_{k} take values in the set of weights of a fixed representation V of a simple Lie algebra 𝔤 over ℂ. This was done in [2] in the case of equidistributed random variables X_{k} and in [15] in general. The transformation 𝔓 is then defined by using Kashiwara’s crystal basis theory [11] (or, equivalently, by the Littelmann path model). When V is a minuscule representation, we also obtain in [15] the law of the associated random walk conditioned to never exit the dominant Weyl chamber C of 𝔤 under the crucial assumption (also required in [18] and [19]) that m = 𝔼(X_{k}) lies in the interior of C. The transition matrix obtained has a simple expression in terms of the Weyl characters of the irreducible representations of 𝔤.

2010 Mathematics Subject Classification. 05E05, 05E10, 60G50, 60J10, 60J22.

1We will discuss the cases of the Lie algebras 𝔤𝔩(n), 𝔤𝔩(m, n) and 𝔮(n) in parallel. The exponents ∅, h or s will refer to these three cases, respectively, in this order. See § 3.2.

It is then a natural question to try to extend the results of [18] and [15] to other conditionings. In this paper, we generalize the results of [18] to the one-way simple walk conditioned to stay in some semigroups C^{h} and C^{s} which are the analogues of C^{∅} for the Lie superalgebras 𝔤𝔩(m, n) and 𝔮(n), respectively. In particular, the points with integer coordinates of C^{h} are parametrized by hook partitions and those of C^{s} by strict partitions with at most n parts. Here we must also assume that the drift m lies in the interior of the cone generated by the semigroups considered.

In both cases, this is also achieved by introducing a Pitman type transform 𝔓. There are nevertheless important differences with the Pitman transforms used in [18], [2], and [15]; indeed, these transforms can be obtained by interpreting each path as a vertex in a Kashiwara crystal and by then applying raising crystal operators until the highest weight (source) vertex is reached. A contrario, the situation is more complicated for 𝔤𝔩(m, n) and 𝔮(n), essentially because the highest weight vertices in the associated crystals are not so easily tractable. To overcome these complications, we will define the transformation 𝔓 by using analogues of the Robinson–Schensted–Knuth insertion procedure on tableaux introduced in [1] and more recently in [5].

Entries of the transition matrix of the one-way simple walk W conditioned to stay in C^{s} (respectively in C^{h}) can be expressed in terms of P -Schur functions (respectively supersymmetric functions). A key ingredient to compute this transition matrix is the asymptotic behavior of the tensor multiplicities corresponding to the vector representation. Although these limits could also be deduced from results by Kerov [13] and Nazarov [17] on asymptotic representation theory of the symmetric and spin symmetric groups, we obtain them here by different methods, probabilistic in nature, which moreover generalize to other Lie algebras (see [15]). Namely, we derive these asymptotic behaviors from an extension of a quotient local limit theorem established in [15] for random walks conditioned to stay in semigroups.

We study the three conditionings of the one-way simple walk in C^{∅}, C^{h}, and C^{s} simultaneously, by using representation theory of 𝔤𝔩(n), 𝔤𝔩(m, n), and 𝔮(n), respectively. We introduce the generalized Pitman transformations by using insertion procedures on tableaux and Robinson–Schensted–Knuth correspondences (as in [18]) rather than crystal basis theory (as in [2] and [15]). We thus avoid technical difficulties inherent to crystal basis theory of the superalgebras 𝔤𝔩(m, n) and 𝔮(n). Throughout the paper, we provide explicit examples for each situation, in order to help the reader to understand the used tools and to visualize the Pitman transform.

The paper is organized as follows. Sections 2, 3 and 4 are review sections. They are devoted to basics on Markov chains, on representation theory, and on combinatorial representation theory of the algebras 𝔤𝔩(n), 𝔤𝔩(m, n) and 𝔮(n), respectively. In particular, we completely recall the relevant notions of Robinson–Schensted–Knuth correspondences. Section 5 introduces the generalized Pitman transform. Without any hypothesis on the drift, we show that it maps the one-way simple walk onto a Markov chain whose transition matrix is computed. The main result of the paper (Theorem 6.2.3), giving the law of the conditioned one-way simple walk with suitable drift, is stated in Section 6. The appendix is devoted to the proof of Proposition 4.3.3 for which complements on crystal basis theory for superalgebras are required. In conclusion and briefly speaking, this article simultaneously revisits O’Connell’s results in the case of the Lie algebra 𝔤(n) and extends them to the super Lie algebras 𝔤𝔩(m, n) and 𝔮(n), hence to new semi-groups. As in [15] a novelty is the use of a local limit theorem for the conditioned random walk. We also put generalizations of the Robinson–Schensted– Knuth correspondence to the fore rather than Kashiwara’s crystal basis theory, which becomes far more complicated in the super Lie algebra case.

2. Markov chains

We now recall the background on Markov chains and their conditioning that we use in the sequel.

2.1. Markov chains and conditioning. Consider a probability space (Ω, T , ℙ) and a countable set M. Let Y = (Y_{ℓ})_{ℓ≥0} be a sequence of random variables defined on Ω with values in M. The sequence Y is a Markov chain when

ℙ[Y_{ℓ+1} = y_{ℓ+1} | Y_{ℓ} = y_{ℓ}, …, Y_{0} = y_{0}] = ℙ[Y_{ℓ+1} = y_{ℓ+1} | Y_{ℓ} = y_{ℓ}]

for all ℓ ≥ 0 and y_{0}, …, y_{ℓ}, y_{ℓ+1} ∈ M. The Markov chains considered in the sequel will also be assumed time homogeneous, that is,

ℙ[Y_{ℓ+1} = y | Y_{ℓ} = x] = ℙ[Y_{ℓ} = y | Y_{ℓ−1} = x]

for all ℓ ≥ 1 and x, y ∈ M; the transition probability from x to y is then defined by Π(x, y) := ℙ[Y_{1} = y | Y_{0} = x] and we refer to Π as the transition matrix of the Markov chain Y. The distribution of Y_{0} is called the initial distribution of the chain Y. It is well known that the initial distribution and the transition probability determine the law of the Markov chain and that, given a probability distribution and a transition matrix on M, there exists an associated Markov chain.

Let Y be a Markov chain on (Ω, T , ℙ) whose initial distribution has full support, i.e., ℙ[Y_{0} = x] = ℙ{ω ∈ Ω | Y_{0}(ω) = x} > 0 for all x ∈ M. Let C be a nonempty subset of M and consider the event S = {ω ∈ Ω | Y_{ℓ}(ω) ∈ C for all ℓ ≥ 0}. Assume that ℙ[S | Y_{0} = λ] > 0 for all λ ∈ C. This implies that ℙ[S] > 0, and we can consider the conditional probability ℚ relative to this event: ℚ[ ·] = ℙ[ · |S].

It is easy to verify that, under this new probability ℚ, the sequence (Y_{ℓ})_{ℓ≥0} is still a Markov chain, with values in C, and with transition probabilities given by

(2.1)  ℚ[Y_{ℓ+1} = λ | Y_{ℓ} = μ] = ℙ[Y_{ℓ+1} = λ | Y_{ℓ} = μ] \frac{ℙ[S | Y_{0} = λ]}{ℙ[S | Y_{0} = μ]}.

We will denote this Markov chain by Y^{C}, and the restriction of the transition matrix Π to the entries which are in C by Π^{C} (in other words, Π^{C} = (Π(λ, μ))_{λ,μ∈C}.)

2.2. The Doob h-transform. A substochastic matrix on the set M is a map Π : M × M → [0, 1] such that ∑_{y∈M} Π(x, y) ≤ 1 for all x ∈ M. If Π and Π′ are substochastic matrices on M, we define their product Π × Π′ as the substochastic matrix given by the ordinary product of matrices, that is, (Π × Π′)(x, y) = ∑_{z∈M} Π(x, z)Π′(z, y). The matrix Π^{C} defined in the previous subsection is an example of a substochastic matrix.

A function h : M → ℝ is harmonic for Π if ∑_{y∈M} Π(x, y)h(y) = h(x) for all x ∈ M. When h is positive, we can define the Doob transform of Π by h (also called the htransform of Π) setting Π_{h}(x, y) = \frac{h(y)}{h(x)}Π(x, y). We then have ∑_{y∈M} Π_{h}(x, y) = 1 for all x ∈ M, and Π_{h} can be interpreted as the transition matrix of a certain Markov chain. An example is given in the second part of the previous subsection (see (2.1)): the state space is C, the substochastic matrix is Π^{C}, the harmonic function is h_{C}(λ) := ℙ[S | Y_{0} = λ], and the transition matrix Π_{h_{C}}^{C} is the one of the Markov chain Y^{C}.

2.3. Green function and Martin kernel. Let Π be a substochastic matrix on the set M. Its Green function is defined as the series Γ(x, y) = ∑_{ℓ≥0} Π^{ℓ}(x, y); when Π is the transition matrix of a Markov chain, the quantity Γ(x, y) is the expected value of the number of passages of the Markov chain from x to y.

Assume that there exists x^{∗} in M such that 0 < Γ(x^{∗}, y) < ∞ for all y ∈ M. The Martin kernel associated with Π (with reference point x^{∗}) is then defined by K(x, y) = \frac{Γ(x,y)}{Γ(x^{∗},y)}. Consider a positive harmonic function h, let Π_{h} be the h-transform of Π, and consider the Markov chain Y^{h} = (Y_{ℓ}^{h})_{ℓ≥1} starting at x^{∗} and whose transition matrix is Π_{h}. The following theorem is due to Doob (see for instance [15] for a detailed proof).

Theorem 2.3.1 (Doob). Assume that there exists a function f : M → ℝ such that, for all x ∈ M, lim_{ℓ→+∞} K (x, Y_{ℓ}^{h}(ω)) = f(x) for ℙ-almost all ω ∈ Ω. Then there exists a

positive real constant c such that f = c · h.

2.4. Quotient local limit theorem for a random walk in a semigroup. We now recall some results on random walks similar to those established in [15]. However, the notion of random walk in a cone which appears in [15] will be replaced by the notion of random walk in a semigroup. For the sake of brevity, we omit the proofs: they require extensions of arguments used in [15] to the case of semigroups. We refer the reader to [16] (which is an extended version of the present paper) for a complete exposition.

Let C be a subsemigroup of (ℝ^{N}, +) whose interior C̊is non empty; we denote by C_{c} the cone of ℝ^{N} generated by C.

Here are three examples of additive subsemigroups of ℝ^{N} that will appear in the sequel:

(e1) N = n > 0 and C^{∅} = {(x_{1}, x_{2}, …, x_{n}) ∈ ℝ^{n} | x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{n} ≥ 0}, (e2) N = n > 0 and C^{s} = {(x_{1}, x_{2}, …, x_{n}) ∈ C^{∅} | x_{i+1} ≠ x_{i} if x_{i} ≠ 0} , (e3) Let m, n be two positive integers. The set

C^{h} = \{(x\overline{m}, x\overline{m−1}, …, x\overline{1}, x_{1}, x_{2}, …, x_{n}) ∈ ℝ^{n+m} |

x\overline{m} ≥ x\overline{m−1} ≥ ⋯ ≥ x\overline{1} ≥ 0, x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{n} ≥ 0 and x_{i} = 0 for all i > x\overline{1}\}

is a semigroup in ℝ^{n+m}, but is not a cone, and we have

C̊^{h} = \{x\overline{m} > x\overline{m−1} > ⋯ > x\overline{1} > m, x_{1} > x_{2} > ⋯ > x_{n} > 0\},
C_{c}^{h} ⊂ \{x\overline{m} ≥ x\overline{m−1} ≥ ⋯ ≥ x\overline{1} ≥ 0, x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{n} ≥ 0\}.

The subsemigroups C we consider are assumed to satisfy the geometric hypothesis (h1) C̊+ C_{c} ⊂ C. Observe this is in particular the case for our three examples (e1), (e2) and (e3). Now, let (X_{ℓ})_{ℓ≥1} be a sequence of independent and identically distributed random

variables defined on a probability space (Ω, T , ℙ) with values in the Euclidean space ℝ^{n}; the associated random walk is defined by S_{0} = 0 and S_{ℓ} := X_{1} + ⋯ + X_{ℓ} for ℓ ≥ 1. We assume that 𝔼|X_{ℓ}| < +∞, and we set m := 𝔼(X_{ℓ}). Consider a semigroup C in ℝ^{n}, with interior C̊≠ ∅ satisfying (h1), and introduce the following additional hypotheses:

(h2) there exists ℓ_{0} > 0 such that ℙ [S_{1} ∈ C, S_{2} ∈ C, …, S_{ℓ_{0}−1} ∈ C, S_{ℓ_{0}} ∈ C̊] > 0,

(h3) there exists t > 0 such that tm ∈ C̊.

Under hypotheses (h2) and (h3), we get ℙ [S_{ℓ} ∈ C for all ℓ ≥ 0] > 0.

The quotient local limit theorem stated in [15] can be extended to our situation. We limit our statement to random walks in the discrete lattice ℤ^{n}, and thus make an aperiodicity hypothesis, assuming that the support S_{μ} of the law μ of the random variables X_{ℓ} is a subset of ℤ^{n} which is not contained in a coset of a proper subgroup of ℤ^{n}. If this aperiodicity hypothesis is not satisfied, the problem is not well posed: by subtracting a well chosen constant vector to each X_{ℓ}, we see that the new walk lives in a proper subgroup of ℤ^{n}.

Theorem 2.4.1. Assume that the random variables X_{ℓ} are almost surely bounded. Let C be an additive subsemigroup of ℝ^{n} satisfying hypotheses (h1), (h2) and (h3). Let (g_{ℓ})_{ℓ≥1} and (h_{ℓ})_{ℓ≥1} be two sequences in ℤ^{n}, and α < 2/3 such that

lim_{ℓ→∞} ℓ^{−α}∥g_{ℓ} − ℓm∥ = 0 and lim_{ℓ→∞} ℓ^{−1/2}∥h_{ℓ}∥ = 0.

Then, as ℓ tends to infinity, we have

ℙ [S_{1} ∈ C, …, S_{ℓ} ∈ C, S_{ℓ} = g_{ℓ} + h_{ℓ}] ∼ ℙ [S_{1} ∈ C, …, S_{ℓ} ∈ C, S_{ℓ} = g_{ℓ}] .

3. Basics on representation theory

We recall in the following paragraphs some classical material on representation theory of classical Lie algebras and superalgebras. For a complete review, the reader is referred to [3], [6], and [9].

3.1. Weights and roots. The root and weight lattices of the Lie algebra 𝔤𝔩(n) over ℂ are realized in the Euclidean space ℝ^{n} with standard basis B = (ε_{1}, …, ε_{n}). The root lattice is Q = ⨁_{i=1}^{n−1} ℤα_{i}, where α_{i} = ε_{i} − ε_{i+1} for i = 1, …, n − 1. The weight lattice is P = ℤ^{n}, and we denote by P_{+} = {x = (x_{1}, …, x_{n}) ∈ ℤ^{n} | x_{1} ≥ ⋯ ≥ x_{n}} the cone of dominant positive weights.

The Weyl group of 𝔤𝔩(n) can be identified with the symmetric group S_{n} acting on ℤ^{n} by permutation of the coordinates. The Cartan Lie subalgebra 𝔥 of 𝔤𝔩(n) is the subalgebra of diagonal matrices. The triangular decomposition of

𝔤𝔩(n) = 𝔤𝔩(n)_{+} ⊕ 𝔥 ⊕ 𝔤𝔩(n)_{−}

is the usual one obtained by considering strictly upper diagonal, diagonal, and strictly lower diagonal matrices.

The Lie superalgebra 𝔤𝔩(m, n) can be regarded as the graded ℤ/2ℤ algebra of the matrices of the form

( \begin{matrix}A & C \\ D & B \end{matrix} ) , A ∈ 𝔤𝔩(m), B ∈ 𝔤𝔩(n), C ∈ M(m, n), D ∈ M(n, m),

where M(m, n) is the set of complex m × n matrices. It decomposes into the sum of its even and odd parts 𝔤𝔩(m, n) = 𝔤𝔩(m, n)_{0} ⊕ 𝔤𝔩(m, n)_{1}, the term 𝔤𝔩(m, n)_{0} being the set of matrices with C = D = 0, and the term 𝔤𝔩(m, n)_{1} being the set of matrices with A = B = 0. The ordinary Lie bracket is replaced by its super version, that is, [X, Y] = XY − (−1)^{ij}Y X for X ∈ 𝔤𝔩(n)_{i} and Y ∈ 𝔤𝔩(n)_{j}. Here i and j are regarded as elements of ℤ/2ℤ.

The Cartan subalgebra 𝔥, the Weyl group W, the weight lattice P, and the set P_{+} of positive dominant weights of 𝔤𝔩(m, n) coincide with those of the even part 𝔤𝔩(m, n)_{0}. In particular, P ≃ ℤ^{m+n} and W = S_{m} × S_{n}. Writing each weight β ∈ ℤ^{m+n} in the form β = (β\overline{m}, …, β\overline{1} | β_{1}, …, β_{n}), we have P_{+} = \{(β\overline{m}, …, β\overline{1} | β_{1}, …, β_{n}) ∈ ℤ^{n+m} with β\overline{m} ≥ ⋯ ≥ β\overline{1} and β_{1} ≥ ⋯ ≥ β_{n}\}.

The superalgebra 𝔤𝔩(m, n) admits the triangular decomposition

𝔤𝔩(m, n) = 𝔤𝔩(m, n)_{+} ⊕ 𝔥 ⊕ 𝔤𝔩(m, n)_{−},

where 𝔤𝔩(m, n)_{+} and 𝔤𝔩(m, n)_{−} are the sets of strictly upper and lower matrices in 𝔤𝔩(m, n), respectively, and 𝔥 is the subalgebra of diagonal matrices.

We denote by 𝔮(n) the Lie superalgebra of all matrices of the form

( \begin{matrix}A & A′ \\ A′ & A \end{matrix} ) , A, A′ ∈ 𝔤𝔩(n),

endowed with the previous super Lie bracket. This superalgebra decomposes into the sum 𝔮(n) = 𝔮_{0}(n) ⊕ 𝔮_{1}(n) of even (A′ = 0) and odd (A = 0) parts. We denote by e_{r,s} (respectively e′_{r,s}), 1 ≤ r, s ≤ n, the element of 𝔮_{0}(n) (respectively of 𝔮_{1}(n)) in which A (respectively A′) has (r, s)-entry equal to 1 and the other entries equal 0. Let

𝔥_{q} = ⨁_{r=1}^{n} ℂe_{r,r} ⊕ ⨁_{r=1}^{n} ℂe′_{r,r}

be the Cartan subalgebra of 𝔮(n). The superalgebra 𝔮(n) admits the triangular decomposition

𝔮(n) = 𝔮_{+}(n) ⊕ 𝔥_{q} ⊕ 𝔮_{−}(n),

where 𝔮_{+}(n) and 𝔮_{−}(n) are the subalgebras generated over ℂ by {e_{r,s}, e′_{r,s} | 1 ≤ r < s ≤ n} and {e_{r,s}, e′_{r,s} | 1 ≤ s < r ≤ n}. We also set 𝔥 = ⨁_{r=1}^{n} ℂe_{r,r}. The weight lattice P of 𝔮(n) can be identified with ℤ^{n} and its Weyl group with S_{n}. Both coincide with those of the even part 𝔮_{0}(n), and we set P_{+} = ℤ_{≥0}^{n}.

3.2. Weight spaces and characters. Assume 𝔤 = 𝔤𝔩(n), 𝔤𝔩(m, n), or 𝔮(n). For short, we set N = n when 𝔤 = 𝔤𝔩(n) or 𝔮(n) and N = m + n when 𝔤 = 𝔤𝔩(m, n). It will be convenient to associate the symbol ♢ ∈ {∅, h, s} to the objects attached to the algebras 𝔤𝔩(n), 𝔤𝔩(m, n), 𝔮(n), respectively.

In the sequel, we will only consider finite dimensional weight 𝔤-modules. Such a module M admits a decomposition in weight spaces M = ⨁_{μ∈P} M_{μ}, where M_{μ} := {v ∈ M | h · v = μ(h)v for all h ∈ 𝔥}, and P is embedded in the dual of 𝔥. The space M_{μ} is thus an 𝔥-module. If M and M′ are finite-dimensional weight 𝔤-modules and μ ∈ P, we get (M ⊕M′)_{μ} = M_{μ}⊕M′_{μ}. In particular, the weight spaces associated to any 𝔤𝔩(m, n)- (respectively 𝔮(n)-) module are defined as the weight spaces of its restriction to 𝔤𝔩(m, n)_{0} (respectively 𝔮(n)_{0}). The character of M is the Laurent polynomial in N variables char(M)(x) := ∑_{μ∈P} dim(M_{μ})x^{μ}, where dim(M_{μ}) is the dimension of the weight space M_{μ} and x^{μ} is a formal exponential such that

x^{μ} = \{ \begin{matrix}x_{1}^{μ_{1}} ⋯ x_{n}^{μ_{n}} & for & ♢ ∈ \{∅, s\}, \\ xμ\overline{m} ; \overline{m} ⋯ xμ\overline{1} ; \overline{1}x_{1}^{μ_{1}} ⋯ x_{n}^{μ_{n}} & for & ♢ = h. \end{matrix}

For any σ in the Weyl group, we have dim(M_{μ}) = dim(M_{σ(μ)}) so that char(M)(x) is a symmetric polynomial for ♢ ∈ {∅, s} and is invariant under the action of S_{m} × S_{n} for ♢ = h.

A weight 𝔤-module M is called a highest weight module with highest weight λ if M is generated by M_{λ} and 𝔤_{+} · v = 0 for all v in M_{λ}. To each dominant weight λ ∈ P_{+} corresponds a unique (up to isomorphism) irreducible finite dimensional representation of 𝔤 of highest weight λ. We denote it by V^{♢}(λ); it decomposes as ⨁_{μ∈P} V^{♢}(λ)_{μ}. Letting K_{λ,μ}^{♢} = dim(V^{♢}(λ)_{μ}), we get

(3.1)  char(V^{♢}(λ))(x) = ∑_{μ∈P} K_{λ,μ}^{♢}x^{μ}.

3.3. Partitions and Young diagrams. A partition of length k ≥ 1 is a k-tuple λ = (λ_{1}, …, λ_{k}) ∈ ℤ_{≥0}^{k} such that λ_{1} ≥ ⋯ ≥ λ_{k}; we set |λ| = λ_{1} + ⋯ + λ_{k} and denote by P_{k} the set of partitions of length k. The Young diagram Y (λ) associated with λ is the juxtaposition of rows of lengths λ_{1}, …, λ_{k}, respectively, arranged from top to bottom. For i = 1, …, k, the i-th row is divided into λ_{i} boxes, and the rows are left justified. (See the example below). The partition λ′ obtained by counting the number of boxes in each column of Y (λ) is the conjugate partition of λ.

• We let P^{∅} = P_{n}. To each partition λ ∈ P^{∅}, we associate the weight π(λ) = ∑_{i=1}^{n} λ_{i}ε_{i}

which is dominant for 𝔤 = 𝔤𝔩(n). We say that Y (λ) is a ∅-diagram for 𝔤𝔩(n).

• Let m, n be positive integers. We define the set P^{h} of hook partitions as the set of partitions λ of arbitrary length such that λ_{i} ≤ n for all i > m. For any λ ∈ P^{h}, we denote by λ^{(1)} ∈ P_{m} the partition corresponding to the Young diagram obtained by considering the m longest rows of λ. We also denote by ν_{n}(λ) the partition which remains after deleting the boxes corresponding to λ^{(1)} from the Young diagram of λ. By definition of the hook partition λ, the conjugate partition of ν_{n}(λ) is an element of P_{n}, it is denoted λ^{(2)}. In symbols, λ^{(2)} = ν_{n}(λ)′. We will write λ = (λ^{(1)} | λ^{(2)}) for short, with λ^{(1)} = (λ(1) ; \overline{m}, …, λ(1) \overline{1}) and λ^{(2)} = (λ_{1}^{(2)}, …, λ_{n}^{(2)}); note that the weight π(λ) := ∑_{i=1}^{m} λ(1) ; \overline{i}ε_{i} + ∑_{j=1}^{n} λ_{j}^{(2)}ε_{j+m} is dominant for 𝔤𝔩(m, n). We say that Y (λ) is an

h-diagram for 𝔤𝔩(m, n).

• We similarly define the set P^{s} of strict partitions as the set of partitions λ ∈ P^{∅} with the property that, if λ_{i+1} > 0, then λ_{i} > λ_{i+1}, for i = 1, …, n − 1. We then define the shifted Young diagram Y (λ) associated with λ ∈ P^{s} as the juxtaposition of rows of lengths λ_{1}, …, λ_{n} arranged from top to bottom. Each row i = 1, …, n is divided into λ_{i} boxes, but the i-th row is shifted i − 1 units to the right with respect to the top

row. We also denote by π(λ) = ∑_{i=1}^{n} λ_{i}ε_{i} the dominant weight of 𝔮(n) associated with

λ. We say that Y (λ) is an s-diagram for 𝔮(n).

Example 3.3.1. (1) The diagram is a ∅-diagram for 𝔤𝔩(4) with

λ = (3, 3, 2, 1).

(2) The diagram is an h-diagram for 𝔤𝔩(2, 2) with λ = (3, 3, 2, 2, 2, 1).

We have λ^{(1)} = (3, 3) and λ^{(2)} = (4, 3); as an element of ℤ^{4}, we thus have λ = (3, 3 | 4, 3) and π(λ) = 3ε\overline{2} + 3ε\overline{1} + 4ε_{1} + 3ε_{2}.

(3) The diagram is an s-diagram for 𝔮(3) with λ = (4, 2, 1).

Notation. To simplify notation, in the sequel we shall identify the partition λ with its associated dominant weight and simply write V^{♢}(λ) for the highest weight module with highest weight λ rather than V^{♢}(π(λ)).

Remark. For any ♢ ∈ {∅, h, s}, the set P^{♢} is naturally associated with one of the connected subsemigroups C^{♢} of § 2.4; more precisely, P^{♢} is the intersection of C^{♢} with the integral lattice and C^{♢} satisfies hypothesis (h1) of § 2.4.

Assume λ, μ are elements of P^{♢}. We write μ ⊂ λ when the Young diagram of μ is contained in the one of λ. In that case, the skew Young diagram λ/μ is obtained from λ by deleting the boxes appearing in μ.

3.4. Tensor powers of the natural representation. Each algebra 𝔤=𝔤𝔩(n), 𝔤𝔩(m, n), and 𝔮(n) can be realized as a matrix algebra. They thus admit a natural representation V^{♢} which is the vector representation of the underlying matrix algebra.

For any ℓ ≥ 0, the tensor power (V^{♢})^{⊗ℓ} is a semisimple representation of 𝔤. This means that (V^{♢})^{⊗ℓ} decomposes into a direct sum of irreducible representations

(V^{♢})^{⊗ℓ} ≃ ⨁_{λ∈P_{+}} V^{♢}(λ)^{⊕f_{λ}^{♢}},

where, for any λ ∈ P_{+}, the module V^{♢}(λ) is the irreducible module with highest weight λ and multiplicity f_{λ}^{♢} in (V^{♢})^{⊗ℓ}. In general, we cannot realize all the irreducible highest weight modules as irreducible components in a tensor product (V^{♢})^{⊗ℓ}, but we have the following statement.

Proposition 3.4.1. For any λ ∈ P_{+}, the module V^{♢}(λ) appears as an irreducible component in a tensor product (V^{♢})^{⊗ℓ} if and only if λ ∈ P^{♢} and |λ| = ℓ.

When μ ∈ P^{♢}, we define the multiplicities f_{λ/μ}^{♢} by

(3.2)  V^{♢}(μ) ⊗ (V^{♢})^{⊗ℓ} ≃ ⨁_{λ∈P_{+}} V^{♢}(λ)^{⊕f_{λ/μ}^{♢}}.

Set ℓ′ = |μ|. Since V^{♢}(μ) appears as an irreducible component of (V^{♢})^{⊗ℓ′}, we get f_{λ/μ}^{♢} ≠ 0 if and only if λ appears as an irreducible component of (V^{♢})^{⊗ℓ+ℓ′}. In this situation, λ ∈ P^{♢} and |λ| = ℓ + ℓ′. When ℓ = 1 we have

(3.3)  V^{♢}(μ) ⊗ V^{♢} ≃ ⨁_{μ⇝λ} V^{♢}(λ),

where μ ⇝ λ means that the sum is over all the partitions λ ∈ P^{♢} obtained from μ ∈ P^{♢} by adding one box. More generally, if κ ∈ P^{♢}, we set

(3.4)  V^{♢}(μ) ⊗ V^{♢}(κ) = ⨁_{λ∈P^{♢}} V^{♢}(λ)^{⊕m_{κ,μ}^{λ,♢}}.

Observe that m_{κ,μ}^{λ,♢} = m_{μ,κ}^{λ,♢} since V^{♢}(μ) ⊗ V^{♢}(κ) and V^{♢}(κ) ⊗ V^{♢}(μ) are isomorphic, and that m_{μ,(1)}^{λ,♢} = 1 if and only if μ ⇝ λ.

4. Combinatorics of tableaux

In this section, we review the different notions of tableaux which are relevant for the representation theory of 𝔤𝔩(n), 𝔤𝔩(m, n), and 𝔮(n). We also recall the associated insertion schemes which are essential to define the generalized Pitman transform in an elementary way. These notions are very classical for 𝔤𝔩(n) (see [4]); for 𝔤𝔩(m, n), they were introduced by Benkart, Kang and Kashiwara in [1]; for 𝔮(n) this has been developed very recently in [5].

4.1. Characters and tableaux.

4.1.1. Semistandard 𝔤𝔩(n)-tableaux. Consider λ ∈ P^{∅}. A (semistandard) 𝔤𝔩(n)-tableau of shape λ is a filling (let us call it T) of the Young diagram associated with λ by letters of the ordered alphabet A_{n} = {1 < 2 < ⋯ < n} such that entries along rows of T increase weakly from left to right and entries along columns increase strictly from top to bottom (see Example 4.2.1). We denote by T^{∅}(λ) the set of all 𝔤𝔩(n)-tableaux of shape λ. We define the reading of T ∈ T^{∅}(λ) as the word w(T) of A_{n}^{∗} obtained by reading the rows of T from right to left and then top to bottom.

The weight of a word w ∈ A_{n}^{∗} is the n-tuple wt(w) = (μ_{1}, …, μ_{n}), where for i = 1, …, n the nonnegative integer μ_{i} is the number of letters i in w. The weight wt(T) of T ∈ T^{∅}(λ) is then defined as the weight of its reading w(T). The Schur function s_{λ}^{∅} is the character of V^{∅}(λ). This is a symmetric polynomial in the variables x_{1}, …, x_{n} which can be expressed as a generating function over T^{∅}(λ), namely as

(4.1)  s_{λ}^{∅}(x) = ∑_{T ∈T^{∅}(λ)} x^{wt(T)}.

According to the Weyl character formula, we have (4.2)

s_{λ}^{∅}(x) = \frac{1}{∏_{1≤i<j≤n}(1 − \frac{x_{j}}{x_{i}})} ∑_{σ∈S_{n}} ε(σ)x^{σ(λ+ρ)−ρ} = \frac{1}{∏_{1≤i<j≤n}(x_{i} − x_{j})} ∑_{σ∈S_{n}} ε(σ)x^{σ(λ+ρ)},

where S_{n} is the symmetric group of rank n, ε(σ) is the sign of σ, ρ = (n − 1, n − 2, …, 0) ∈ ℤ^{n}, and S_{n} acts on ℤ^{n} by permutation of the coordinates.

4.1.2. Semistandard 𝔤𝔩(m, n)-tableaux. Consider λ ∈ P^{h}. A (semistandard) 𝔤𝔩(m, n)- tableau of shape λ is a filling T of the hook Young diagram associated with λ by letters of the ordered alphabet A_{m,n} = \{\overline{m} < \overline{m − 1} < ⋯ < \overline{1} < 1 < 2 < ⋯ < n\} such that entries along rows of T increase weakly from left to right with no repetition of unbarred letters permitted and entries along columns increase weakly from top to bottom with no repetition of barred letters permitted (see Example 4.2.2). We denote by T^{h}(λ) the set of all 𝔤𝔩(m, n)-tableaux of shape λ. We define the reading of T ∈ T^{h}(λ) as the word w(T) of A_{m,n}^{∗} obtained by reading the rows of T from right to left and top to bottom.

The weight of a word w ∈ A_{m,n} is the (m+n)-tuple wt(w) = (μ\overline{m}, …, μ\overline{1} | ν_{1}, …, ν_{n}), where, for i = 1, …, m and j = 1, …, n, the nonnegative integer μ\overline{i} is the number of letters \overline{i} in w and ν_{j} is the number of letters j in w. The weight of T ∈ T^{h}(λ) is then defined as the weight of its reading w(T). The Schur function s_{λ}^{h} is the character of the irreducible representation V^{h}(λ) of 𝔤𝔩(m, n). This is a polynomial in the variables x\overline{m}, …, x_{x\overline{1}}, x_{1}, …, x_{n}. It admits a nice expression as a generating function over T^{h}(λ), namely as

(4.3)  s_{λ}^{h}(x) = ∑_{T ∈T^{h}(λ)} x^{wt(T)}.

For a general highest weight 𝔤𝔩(m, n)-module there is no simple Weyl character formula. Nevertheless, for the irreducible modules V^{h}(λ) with λ ∈ P^{h}, such a formula exists due to Berele, Regev, and Serge’ev (see [8]). Consider λ ∈ P^{h}: the character s_{λ}^{h} of V^{h}(λ) is given by

(4.4)  s_{λ}^{h}(x) = \frac{∏_{(i,j)∈λ}(1 + \frac{x_{j}}{x\overline{i}})}{∏_{\overline{m}≤\overline{i}<\overline{j}≤\overline{1}}(1 − \frac{x\overline{j}}{x\overline{i}}) ∏_{1≤r<s≤n}(1 − \frac{x_{s}}{x_{r}})} ∑_{w∈S_{m}×S_{n}} ε(w) x^{w(λ+ρ_{+})−ρ_{+}},

where ρ_{+} = (m − 1, …, 1, 0 | n − 1, …, 1, 0), and (i, j) ∈ λ means that the hook Young diagram associated with λ has a box in the i-th row, i ∈ {1, …, m}, and the j-th column, j ∈ {1, …, n}.

4.1.3. Semistandard 𝔮(n)-tableaux. Let us first give a definition. We say that a nonempty word w = x_{1} ⋯ x_{ℓ} ∈ A_{n}^{∗} is a hook word if there exists k with 1 ≤ k ≤ ℓ such that x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{k} < x_{k+1} < ⋯ < x_{ℓ}. Each hook word can be decomposed as w = w_{↓}w_{↑}, where, by convention, the decreasing part w_{↓} = x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{k} is nonempty. The increasing part w_{↑} = x_{k+1} < ⋯ < x_{ℓ} is possibly empty. In particular, when w = x_{1} ⋯ x_{ℓ} is such that x_{1} < ⋯ < x_{ℓ}, then we have w_{↓} = x_{1} and w_{↑} = x_{2} ⋯ x_{ℓ}.

Consider a strict partition λ ∈ P^{s}. A (semistandard) 𝔮(n)-tableau of shape λ is a filling T of the shifted Young diagram associated with λ by letters of A_{n} = {1 < 2 < ⋯ < n} such that, for i = 1, …, n,

(1) the word w_{i} formed by reading the i-th row of T from left to right is a hook word (of length λ_{i},

(2) w_{i} is a hook subword of maximal length in w_{i+1}w_{i} (see Example 4.2.3).

We denote by T^{s}(λ) the set of all 𝔮(n)-tableaux of shape λ. The reading of T ∈ T^{s}(λ) is the word w(T) = w_{n} ⋯ w_{2}w_{1} of A_{n}^{∗}. We define the weight of T as the weight of its reading. The Schur function s_{λ}^{s} is defined as the generating function

(4.5)  s_{λ}^{s}(x) = ∑_{T ∈T^{s}(λ)} x^{wt(T)}.

This is not the original combinatorial definition of the Schur function given in terms of different tableaux called shifted Young tableaux. Nevertheless, according to Theorem 2.17 in [20] and Remark 2.6 in [5] there exists a weight-preserving bijection between the set of shifted Young tableaux of shape λ and the set of 𝔮(n)-tableaux with the same shape. Set d(λ) for the depth of λ, that is, for the number of nonzero coordinates in λ. The Schur function admits a Weyl type expression, namely we have.

s_{λ}^{s}(x) = ∑_{σ∈S_{n}/S_{λ}} σ (x^{λ} ∏_{1≤i≤d(λ)} ∏_{i<j≤n} (\frac{x_{i} + x_{j}}{x_{i} − x_{j}} )) ,

where S_{λ} is the stabilizer of (the vector) λ under the action of S_{n}. Thus S_{λ} is either isomorphic to S_{n−d(λ)} when d(λ) < n − 1 or it reduces to {id} otherwise.

4.2. Insertion schemes. To make our notation consistent, we set A^{∅} = A^{s} = A_{n} and A^{h} = A_{m,n}.

4.2.1. Insertion in 𝔤𝔩(n)-tableaux. Let T be a 𝔤𝔩(n)-tableau of shape λ ∈ P^{∅}. We write T = C_{1} ⋯ C_{s} as the juxtaposition of its columns. Consider x ∈ A_{n}. We denote by x → T the tableau obtained by applying the following recursive procedure:

(1) If T = ∅, then x → T is the tableau with one box filled by x.

(2) Assume C_{1} is nonempty.

(a) If all the letters of C_{1} are less than x, the tableau x → T is obtained from T by adding one box filled by x at the bottom of C_{1}.

(b) Otherwise, let y = min{t ∈ C_{1} | t ≥ x}. Write C′_{1} for the column obtained by replacing y by x in C_{1}. Then x → T = C′_{1}(y → C_{2} ⋯ C_{s}) is defined as the juxtaposition of C′_{1} with the tableau obtained by inserting y in the remaining columns.

One easily checks that x → T is a 𝔤𝔩(n)-tableau. More generally, for a word w = x_{1}x_{2} ⋯ x_{ℓ} ∈ A_{n}^{∗}, we define the 𝔤𝔩(n)-tableau P^{∅}(w) by

(4.6)  P^{∅}(w) = x_{ℓ} → (⋯ (x_{2} → (x_{1} → ∅))).

Example 4.2.1. With n ≥ 4 and w = 232143, we obtain the following sequences of tableaux:

          2 , 2 3 , 2  2 3 , 1  2  2 3 , 1  2  2 3 4 , 1  2  2 3  3 4 = P^{∅}(w).

4.2.2. Insertion in 𝔤𝔩(m, n)-tableaux. Let T = C_{1} ⋯ C_{s} be a 𝔤𝔩(m, n)-tableau of shape λ ∈ P^{h}. Consider x ∈ A_{m,n}. We denote by x → T the tableau obtained by applying the following procedure:

(1) If T = ∅, then x → T is the tableau with one box filled by x.

(2) Assume C_{1} is nonempty and x is a barred letter.

(a) If all the letters of C_{1} are less than x, the tableau x → T is obtained from T by adding one box filled by x at the bottom of C_{1}.

(b) Otherwise, let y = min{t ∈ C_{1} | t ≥ x}. Write C′_{1} for the column obtained by replacing the topmost occurrence of y in C_{1} by x. (If y is unbarred, it may happen that y appears several times in C_{1}.) The insertion x → T is then defined recursively as x → T = C′_{1}(y → C_{2} ⋯ C_{s}).

(3) Assume C_{1} is nonempty and x is an unbarred letter.

(a) If all the letters of C_{1} are less than or equal to x, the tableau x → T is obtained from T by adding one box filled by x at the bottom of C_{1}.

(b) Otherwise, let y = min{t ∈ C_{1} | t > x}. Write C′_{1} for the column obtained by replacing the topmost occurrence of y in C_{1} by x. Again, we define x → T = C′_{1}(y → C_{2} ⋯ C_{s}).

One verifies that x → T is a 𝔤𝔩(m, n)-tableau. For any word w = x_{1}x_{2} ⋯ x_{ℓ} ∈ A_{m,n}^{∗}, we define the 𝔤𝔩(m, n)-tableau P^{h}(w) recursively as in (4.6).

Example 4.2.2. With (m, n) = (2, 3) and w = ¯23¯2¯132¯12, we obtain the following sequence of tableaux:

       ¯2 , ¯2 3 , ¯2  ¯2 3 , ¯2  ¯2 ¯1  3 , ¯2  ¯2 ¯1  3 3 , ¯2  ¯2 ¯1  3 2  3 , ¯2  ¯2  3 ¯1  ¯1 2  3 , ¯2  ¯2  3 ¯1  ¯1 2  3 2 = P^{h}(w).

4.2.3. Insertion in 𝔮(n)-tableaux. Let T = L_{1} ⋯ L_{k} be a 𝔮(n)-tableau of shape λ ∈ P^{s}. Here we regard T as the juxtaposition of its rows (written by decreasing lengths) rather than as the juxtaposition of its columns. Consider x ∈ A_{n}. We denote by x → T the tableau obtained by applying the following procedure (which implies in particular that, at each step and for any row L_{i}, the word w(L_{i}) is a hook word):

(1) If T = ∅, then x → T is the tableau with one box filled by x.

(2) Assume L_{1} is nonempty and write w = w_{↓}w_{↑} for the decomposition of w(L_{1}) as decreasing and increasing subwords.

(a) If wx is a hook word, then x → T is the tableau obtained from T by adding one box filled by x at the right end of L_{1}.

(b) Otherwise, w_{↑} ≠ ∅ and y = min{t ∈ w_{↑} | t ≥ x} exists. We first replace y by x in w_{↑}. Now let z = max{t ∈ w_{↓} | t < y}. We replace z by y in w_{↓}. Write L′_{1} for the row obtained in this manner. The insertion x → T is then again defined recursively by x → T = L′_{1}(z → L_{2} ⋯ L_{k}).

One also verifies that this gives a 𝔮(n)-tableau. For any word w = x_{1}x_{2} ⋯ x_{ℓ} ∈ A_{n}^{∗}, we define the 𝔮(n)-tableau P^{s}(w) recursively as in (4.6).

Example 4.2.3. With n = 4 and w = 232145331, we obtain the following sequence of tableaux:

2 , 2 3 , 3 2 2 , 3 2 1 2 , 3 2 1 4 2 , 3 2 1 4 5 2 ,

4 2 1 3 5 2 3 , 4 3 1 3 5 3 2 2 , 4 3 3 1 5 3 2 1 2 = P^{s}(w),

where we have indicated in bold type the increasing part of each row.

4.3. Robinson–Schensted–Knuth correspondence. For any word w = x_{1} ⋯ x_{ℓ} ∈ (A^{♢})^{ℓ} and k = 1, … ℓ, let λ^{(k)} be the shape of the tableau P^{♢}(x_{1} ⋯ x_{k}); it is obtained from λ^{(k−1)} by adding one box b_{k}. The tableau Q^{♢}(w) of shape λ^{(ℓ)} is obtained by filling each box b_{k} with the letter k; observe that Q^{♢}(w) is a standard tableau: it contains exactly once all the integers 1, …, ℓ, its rows strictly increase from left to right and its columns strictly increase from top to bottom. Note also that the datum of a standard tableau with ℓ boxes is equivalent to that of a sequence of shapes (λ^{(1)}, …, λ^{(ℓ)}) ∈ (P^{♢})^{ℓ} such that λ^{(1)} = (1) and, for k = 1, …, ℓ, the shape λ^{(k)} is obtained by adding one box to λ^{(k−1)}.

Examples 4.3.1. From the previous examples, we deduce Q^{∅}(232143) = 1 3 4 2 6 5 , Q^{h}(¯23¯2¯132¯12) = 1 3 7 2 4 5 6 8

and Q^{s}(23214433) = 1 2 4 5 6 3 7 9 8 .

By a ♢-tableau, with ♢ ∈ {∅, h, s}, we mean a tableau for 𝔤𝔩(n), 𝔤𝔩(m, n), or 𝔮(n), respectively. We can now state the Robinson–Schensted–Knuth correspondence for 𝔤𝔩(n) (see [4]) and its generalizations for 𝔤𝔩(m, n) and 𝔮(n) obtained in [1] and [5], respectively. For any ℓ ≥ 0 and ♢ ∈ {∅, h, s}, let U_{ℓ}^{♢} be the set of pairs (P, Q), where P is a ♢-tableau with ℓ boxes and Q a standard tableau of the same shape as P. Given a standard tableau T of shape λ ∈ P^{♢} with |λ| = ℓ, we set B^{♢}(T) = {w ∈ (A^{♢})^{ℓ} | Q^{♢}(w) = T }. We have the following result.

Theorem 4.3.2. [5] Fix ♢ ∈ {∅, h, s}.

(1) The map

\{θ_{ℓ}^{♢} : \begin{matrix}(A^{♢})^{ℓ} & → & U_{ℓ}^{♢} \\ w & ↦ & (P^{♢}(w), Q^{♢}(w)) \end{matrix}

is a one-to-one correspondence. In particular, for any standard tableau T, the map P^{♢} restricts to a weight preserving bijection P^{♢} : B^{♢}(T) ⟷ T^{♢}(λ).

(2) For any λ ∈ P^{♢}, the multiplicity f_{λ}^{♢} is equal to the number of standard ♢- tableaux of shape λ.

Given λ, μ in P^{♢} regarded as Young diagrams such that μ_{i} ≤ λ_{i} for all i with μ_{i} > 0, we denote by λ/μ the skew Young diagram obtained by deleting in λ the boxes of μ. By a standard tableau of shape λ/μ with ℓ boxes, we mean a filling of λ/μ by the letters of {1, …, ℓ} whose rows and columns strictly increase from left to right and top to bottom, respectively. By a skew ♢-tableau of shape λ/μ, we mean a filling of λ/μ by letters of A^{♢} whose rows and columns satisfy the same conditions as for the ordinary ♢-tableaux. The next proposition will follow from the Littlewood–Richardson rules proved in [4] for 𝔤𝔩(n), in [10] for 𝔤𝔩(m, n), and in [5] for 𝔮(n). We postpone its proof to the appendix.

Proposition 4.3.3.

(1) Given λ, μ in P^{♢} such that μ ⊂ λ, the multiplicity f_{λ/μ}^{♢} defined in (3.2) is equal to the number of standard tableaux of shape λ/μ.

(2) Given λ, κ, μ in P^{♢}, we have m_{κ,μ}^{λ,♢} ≤ K_{μ,λ−κ}^{♢}, where K_{μ,λ−κ}^{♢} is the weight multiplicity defined in (3.1) and m_{κ,μ}^{λ,♢} the tensor multiplicity defined in (3.4).

Remark. Using Kashiwara crystal basis theory, we can obtain a stronger version of the previous theorem. For any ♢ ∈ {∅, h, s}, the set B^{♢}(T) has a crystal structure: namely, it can be endowed with the structure of an oriented graph (depending on ♢) with arrows colored by integers. Such a structure can also be defined on the set of words (A^{♢})^{ℓ}; one then shows that the sets B^{♢}(T), where T runs over the set of standard tableaux with ℓ boxes, are the connected components of (A^{♢})^{ℓ}. Moreover, the bijection of Assertion (1) of the theorem is a graph isomorphism that is compatible with this crystal structure. For 𝔤𝔩(n), the crystal basis theory is now a classical tool in representation theory (see [11]). For 𝔤𝔩(m, n) and 𝔮(n), it becomes more complicated. We postpone the background needed for the proof of Proposition 4.3.3 to the Appendix.

5. Pitman transform on the space of paths

5.1. Paths and random walks in ℤ^{N}. Denote by B^{♢} = {e_{i}, i ∈ A^{♢}} the standard basis of ℤ^{N} and fix a point A ∈ ℤ^{N}. We only consider paths in ℤ^{N} with steps in B^{♢}; observe that there is a straightforward bijection between the set of such paths of length ℓ starting from A and the set (A^{♢})^{ℓ} of words of length ℓ on the alphabet A^{♢}: the word x_{1} ⋯ x_{ℓ} ∈ (A^{♢})^{ℓ} of length ℓ corresponds to the path starting at A whose k-th step is the translation by e_{x_{k}}.

Fix a sequence (p_{i})_{i∈A^{♢}} of nonnegative reals such that ∑_{i∈A^{♢}} p_{i} = 1; this defines a probability measure p = (p_{i}) on A^{♢} with mean vector m := ∑_{i∈A^{♢}} p_{i}e_{i}. Let (A^{♢})^{ℕ} be the set of sequences on the alphabet A^{♢} endowed with the product σ-algebra, that is, the smallest σ-algebra containing all subsets of (A^{♢})^{ℕ} defined by a condition concerning only finitely many coordinates. We fix on this measurable space the product probability measure ℙ = p^{⊗ℕ}; by construction, the coordinates X_{ℓ} defined by

X_{ℓ} : w = (x_{i})_{i≥1} ∈ (A^{♢})^{ℕ} ↦ x_{ℓ}

for all ℓ ≥ 1, are independent and identically distributed with law p and mean vector m.

For any ℓ ≥ 1, we denote by π_{ℓ} the canonical projection from (A^{♢})^{ℕ} onto (A^{♢})^{ℓ} defined by π_{ℓ}(ω) = ω^{(ℓ)} := x_{1}x_{2} … x_{ℓ} for any ω = x_{1}x_{2} … ∈ (A^{♢})^{ℕ}, and we set

W_{ℓ}(ω) := W_{0}(ω) + wt ∘ π_{ℓ}(ω) = W_{0}(ω) + wt (ω^{(ℓ)}) ,

where W_{0} is a fixed random variable defined on (A^{♢})^{ℕ} with values in ℤ^{N}, and wt (ω^{(ℓ)}) is the weight of the word ω^{(ℓ)}. The random process W = (W_{ℓ})_{ℓ≥0} is a random walk on ℤ^{N} since W_{ℓ} = W_{0} + X_{1} + ⋯ + X_{ℓ} for all ℓ ≥ 1; this is in particular a Markov chain on ℤ^{N} with transition matrix Π_{W} given by

(5.1)  Π_{W}(α, β) = \{ \begin{matrix}p_{i} & if β − α = e_{i} with i ∈ A^{♢}, \\ 0 & otherwise, \end{matrix}  for all α, β ∈ ℤ^{N}.

5.2. Pitman transform of paths. Our aim is to define a Pitman transform 𝔓^{♢}, ♢ ∈ {∅, h, s}, on the set (A^{♢})^{ℕ} of paths we have considered in the previous section; this will be a generalization of the classical Pitman transform in the same spirit as in [2].

For any ω ∈ (A^{♢})^{ℕ}, set P^{♢}(ω) := (P^{♢}(ω^{(ℓ)}))_{ℓ}. Since we identified Young diagrams with dominant weights, the shape sh(T) of a ♢-tableau T is an element of P^{♢}; the shape of a sequence (T_{ℓ})_{ℓ} of tableaux will be the sequence (sh(T_{ℓ}))_{ℓ}, it defines a path in P^{♢}. We now set

𝔓^{♢}(ω) = sh (P^{♢}(ω)) = sh (Q^{♢}(ω)) for all ω ∈ (A^{♢})^{ℕ}.

Example 5.2.1. Consider ω = 1121231212 · · ·. The path in ℤ^{3} associated with ω remains in P^{∅}; we obtain

\begin{matrix}ℓ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & ⋯ \\ sh (P^{∅}(ω^{(ℓ)})) & (1) & (2) & (2, 1) & (3, 1) & (3, 2) & (3, 2, 1) & (4, 2, 1) & (4, 3, 1) & (5, 3, 1) & (5, 4, 1) & ⋯ \\ sh (P^{s}(ω^{(ℓ)})) & (1) & (2) & (3) & (3, 1) & (4, 1) & (5, 1) & (5, 2) & (5, 3) & (5, 3, 1) & (6, 3, 1) & ⋯ \end{matrix}

Remarks. (i) In [15], for a simple Lie algebra 𝔤, the generalized Pitman transform of ω ∈ (A^{♢})^{ℕ} was defined from the crystal structure on the set of words as the sequence of dominants weights corresponding to the highest weight vertices (source vertices) of the connected components containing the words ω^{(ℓ)}, ℓ ≥ 1. For 𝔤 = 𝔤𝔩(n) this definition agrees with the one we have just introduced in terms of the insertion algorithm on tableaux. For 𝔤𝔩(m, n) and 𝔮(n), there is also a crystal structure on the set of words, but it is more complicated to describe; in particular there may exist several highest weight vertices for a given connected component. It becomes thus easier to define the generalized Pitman transform with the help of insertion algorithms on tableaux. This is what we do here, in the spirit of [18].

(ii) In view of the previous example, we see that the Pitman transform 𝔓^{s} does not fix the paths contained in P^{s} (but 𝔓^{∅} does). This phenomenon can be explained by the special behavior of the crystal tensor product when ♢ ∈ {h, s} (see Lemma 7.1.1 and the remark following it).

We then consider the random variable H_{ℓ}^{♢}

H_{ℓ}^{♢} : \{ \begin{matrix}(A^{♢})^{ℕ} & → & P^{♢} \\ ω & ↦ & 𝔓^{♢}(ω^{(ℓ)}) \end{matrix}

This yields a stochastic process H^{♢}= (H_{ℓ}^{♢})_{ℓ≥0}.

Proposition 5.2.2. For any ♢ ∈ {∅, h, s}, any ℓ ∈ ℕ, and λ ∈ P_{+}, we get ℙ[H_{ℓ}^{♢} = λ] = f_{λ}^{♢} · s_{λ}^{♢}(p).

Proof. By definition of the random variable H_{ℓ}^{♢}, we have

ℙ[H_{ℓ}^{♢} = λ] = ∑_{T tableau of shape λ} ( ∑_{ω∈B(T)} p_{ω}) = ∑_{T tableau of shape λ} ℙ[B(T)].

By (2) of Theorem 4.3.2, we have ℙ[B(T)] = s_{λ}^{♢}(p), and, in particular, it does not depend on T but only on λ. By (3) of Theorem 4.3.2, we then deduce ℙ [H_{ℓ}^{♢} = λ] = f_{λ}^{♢} · s_{λ}^{♢}(p). □

We can now state the main result of this section. For any λ, μ ∈ P^{♢}, we write δ_{μ⇝λ}^{♢} = 1 when λ is obtained by adding one box to μ as in (3.3) and δ_{μ⇝λ}^{♢} = 0 otherwise.

Theorem 5.2.3. The stochastic process H^{♢} is a Markov chain with transition probabilities

(5.2)  Π_{H^{♢}}(μ, λ) = \frac{s_{λ}^{♢}(p)}{s_{μ}^{♢}(p)}δ_{μ⇝λ}^{♢} λ, μ ∈ P^{♢}.

Proof. Consider a sequence of dominant weights λ^{(1)}, …, λ^{(ℓ)}, λ^{(ℓ+1)} in P^{♢} such that λ^{(k)} ⇝ λ^{(k+1)} for k = 1, …, ℓ. We have seen in § 4.3 that this determines a unique standard tableau T, and we have

ℙ[H_{ℓ+1}^{♢} = λ^{ℓ+1}, H_{k}^{♢} = λ^{(k)} for k = 1, …, ℓ] = ∑_{w∈B^{♢}(T)} p_{w} = s_{λ^{(ℓ+1)}}^{♢}(p).

Similarly, we have ℙ[H_{k}^{♢} = λ^{(k)} for k = 1, …, ℓ] = s_{λ^{(ℓ)}}^{♢}(p).Hence

ℙ[H_{ℓ+1}^{♢} = λ^{(ℓ+1)} | H_{k}^{♢} = λ^{(k)} for k = 1, …, ℓ] = \frac{s_{λ^{(ℓ+1)}}^{♢}(p)}{s_{λ^{(ℓ)}}^{♢}(p)}.

In particular, ℙ[H_{ℓ+1}^{♢} = λ^{(ℓ+1)} | H_{k}^{♢} = λ^{(k)} for k = 1, …, ℓ] depends only on λ^{(ℓ+1)} and μ = λ^{(ℓ)}, this is the Markov property. □

Remarks. (i) By Proposition 4.3.3, for all λ, μ in P^{♢} with μ ⊂ λ, the multiplicity f_{λ/μ}^{♢} is equal to the number of standard tableaux of shape λ/μ. The datum of such a tableau T is equivalent to that of the sequence (μ, λ^{(1)}, …, λ^{(ℓ)}) of dominant weights in P^{♢}, where ℓ = |λ| − |μ| and λ^{(ℓ)} = λ; furthermore, for k = 1, …, ℓ, the shape of the ♢-diagram λ^{(k)} is obtained by adding to μ the boxes of T filled by the letters in {1, …, k}. Therefore there is a bijection between the standard tableaux of shape λ/μ and the paths from μ to λ which remain in P^{♢}.

(ii) Let λ ∈ P^{♢} and consider the irreducible highest weight representation V^{♢}(λ). Assume |λ| = ℓ. Let T be a standard tableau of shape λ and define B^{♢}(T) as in Theorem 4.3.2. Then, for any weight μ, the dimension K_{λ,μ} of the μ-weight space in V (λ) is equal to the number of words in B^{♢}(T) of weight μ. This follows from the bijection between B^{♢}(T) and T^{♢}(λ) obtained in Theorem 4.3.2. Since we have identified paths and words, the integer K_{λ,μ} is equal to the number of paths from 0 to μ which remain in B^{♢}(T).

Recall that m = 𝔼(X) is the drift of the random walk defined in (5.1). We have

m = ∑_{i=1}^{n} p_{i}e_{i} for ♢ = ∅, s and m = ∑_{i=1}^{m} p\overline{i}e_{i} + ∑_{j=1}^{n} p_{j}e_{j+m} for ♢ = h. In the sequel, we

will assume that the following condition is satisfied:

Condition 5.2.4. (1) For ♢ ∈ {∅, s}, there holds p_{1} > ⋯ > p_{n} > 0, (2) For ♢ = h, there hold p\overline{m} > ⋯ > p\overline{1} > 0 and p_{1} > ⋯ > p_{n} > 0.

In Section 6, we will need the following result.

Proposition 5.2.5. (1) For all λ, ν ∈ P^{♢} such that ν ⊂ λ, we have

f_{λ/ν}^{♢} = ∑_{μ∈P^{♢}} f_{μ}^{♢} · m_{μ,ν}^{λ,♢}.

(2) Assume that m satisfies Condition 5.2.4. Consider a sequence of weights (λ^{(a)})_{a∈ℕ} of the form λ^{(a)} = am+o(a) and fix a nonnegative integer ℓ. Then, for large enough a, the weight λ^{(a)} is an element of P^{♢}. Moreover, for all κ, μ ∈ P^{♢} such that |μ| = ℓ and |λ^{(a)}| = |κ| + ℓ, we have m_{κ,μ}^{λ^{(a)},♢} = K_{μ,λ^{(a)}−κ}^{♢}.

(3) For (λ^{(a)})_{a∈ℕ} as above and all μ ∈ P^{♢}, we have, for all large enough a,

(5.3)  f_{λ^{(a)}/μ}^{♢} = ∑_{κ∈P^{♢}} f_{κ}^{♢} · K_{μ,λ^{(a)}−κ}^{♢} = ∑_{γ∈P} f_{λ^{(a)}−γ}^{♢} · K_{μ,γ}^{♢}.

Proof. To prove Assertion (1), write L = |λ| − |ν|; by the definition of the Schur functions, we get, using (3.2) and (3.4),

s_{ν}^{♢} · (s_{(1)}^{♢})^{L} = ∑_{μ} f_{μ}^{♢} · s_{μ}^{♢} · s_{ν}^{♢} = ∑_{μ} ∑_{λ} f_{μ}^{♢} · m_{μ,ν}^{λ,♢} · s_{λ}^{♢} = ∑_{λ} f_{λ/ν}^{♢} · s_{λ}^{♢},

where all the sums run over P^{♢}. The assertion immediately follows by comparing the two last expressions.

To prove Assertion (2), observe first that λ^{(a)} is an element of P^{♢} for a sufficiently large because m satisfies Condition 5.2.4. For any κ ∈ P^{♢} such that |κ| = |λ^{(a)}| − ℓ, by Assertion (1) we have

f_{λ^{(a)}/κ}^{♢} = ∑_{μ∈P^{♢},|μ|=ℓ} f_{μ}^{♢} · m_{μ,κ}^{λ^{(a)},♢} = ∑_{μ∈P^{♢},|μ|=ℓ} f_{μ}^{♢} · m_{κ,μ}^{λ^{(a)},♢},

since m_{μ,κ}^{λ^{(a)},♢} = m_{κ,μ}^{λ^{(a)},♢}. Decomposing (V^{♢})^{⊗ℓ} into its irreducible components, one checks that the dimension of the weight space λ^{(a)} − κ in (V^{♢})^{⊗ℓ} is equal to

K_{⊗ℓ,λ^{(a)}−κ}^{♢} := ∑_{μ∈P^{♢},|μ|=ℓ} f_{μ}^{♢} · K_{μ,λ^{(a)}−κ}^{♢}.

By (2) of Proposition 4.3.3, we have 0 ≤ m_{κ,μ}^{λ^{(a)},♢} ≤ K_{μ,λ^{(a)}−κ}^{♢} for all μ ∈ P^{♢}. It thus suffices to show that f_{λ^{(a)}/κ}^{♢} = K_{⊗ℓ,λ^{(a)}−κ}^{♢} for a large enough. Observe that K_{⊗ℓ,λ^{(a)}−κ}^{♢} is equal to the number of words of length ℓ and weight λ^{(a)} − κ on A^{♢}. On the other hand, by the first assertion of Proposition 4.3.3, we deduce that f_{λ^{(a)}/κ}^{♢} is the number of sequences of diagrams (δ^{(0)}, …, δ^{(ℓ)}) in P^{♢} of length ℓ such that δ^{(0)} = κ, δ^{(ℓ)} = λ^{(a)} and δ^{(k+1)}/δ^{(k)} consists of a single box for k = 0, …, ℓ − 1. For 𝔤 = 𝔤𝔩(n) or 𝔮(n), we associate to (δ^{(0)}, …, δ^{(ℓ)}) the word w = x_{1} ⋯ x_{ℓ}, where x_{k} = i if the box δ^{(k)}/δ^{(k−1)} appears in row i of δ^{(k)}, i ∈ {1, …, n}, for k = 1, …, ℓ − 1. For 𝔤 = 𝔤𝔩(m, n), we associate similarly to (δ^{(0)}, …, δ^{(ℓ)}) the word w = x_{1} ⋯ x_{ℓ}, where x_{k} = \overline{i} if the box δ^{(k)}/δ^{(k−1)} appears in row i of δ^{(k)}, i ∈ {1, …, m}, and x_{k} = j if this box appears in column j of δ^{(k)}, j ∈ {1, …, n}, for k = 1, …, ℓ − 1. In both cases, this yields an injective map from the set of sequences of diagrams (δ^{(0)}, …, δ^{(ℓ)}) with δ^{(k+1)}/δ^{(k)} consisting of a single box into the set of words of length ℓ and weight λ^{(a)} − κ on A^{♢}. Moreover this map is surjective; indeed, the tableaux κ and λ^{(a)} differ by at most ℓ = |μ| boxes, and adding ℓ boxes in any order to the rows of κ thus yields a diagram in P^{♢}. Therefore f_{λ^{(a)}/κ}^{♢} = K_{⊗ℓ,λ^{(a)}−κ}^{♢}.

Assertion (3) is a direct consequence of (1) and (2). □

6. Conditioning to stay in P^{♢}

Throughout this section, we assume that Condition 5.2.4 is satisfied, and we denote by W^{♢} the random walk W conditioned to stay in P^{♢}. By Section 2.1, the process W^{♢} is a Markov chain, with transition matrix Π_{W^{♢}}.

We have explicit formulas for the transition matrices Π_{H^{♢}} and Π_{W} of the Markov chains W and H^{♢}. By (5.2) and (5.1), the transition matrix Π_{H^{♢}} of H^{♢} is the Doob ψ-transform of Π_{W}, where ψ is the harmonic function

(6.1)  ψ : \{ \begin{matrix}P^{♢} & → & ℝ_{>0} \\ λ & ↦ & p^{−λ}s_{λ}^{♢}(p) \end{matrix} .

On the other hand, setting h_{P^{♢}}(λ) := ℙ [W_{ℓ} ∈ P for all ℓ ≥ 0^{♢} | W_{0} = λ] for all λ ∈ P^{♢}, we know by § 2.2 that Π_{W^{♢}} is the Doob h_{P^{♢}}-transform of Π_{W}. We are going to prove that ψ and h_{P^{♢}} coincide.

6.1. Limit of ψ along a drift. Since Condition 5.2.4 holds, the products

∇^{∅} = \frac{1}{∏_{1≤i<j≤n}(1 − \frac{p_{j}}{p_{i}})}, ∇^{h} = \frac{∏_{i=1}^{m} ∏_{j=1}^{n}(1 + \frac{p_{j}}{p\overline{i}})}{∏_{\overline{m}≤\overline{i}<\overline{j}≤\overline{1}}(1 − \frac{p\overline{j}}{p\overline{i}}) ∏_{1≤r<s≤n}(1 − \frac{p_{s}}{p_{r}})}, (6.2)

and ∇^{s} = ∏_{1≤i<j≤n} \frac{p_{i} + p_{j}}{p_{i} − p_{j}}

are well-defined, and we have the following proposition.

Proposition 6.1.1. Assume Condition 5.2.4 is satisfied and consider a sequence (λ^{(a)})_{a∈ℕ} in P^{♢} such that λ^{(a)} = am + o(a). Then lim_{a→+∞} p^{−λ^{(a)}}s_{λ^{(a)}}^{♢}(p) = ∇^{♢}.

Proof. Assume first that ♢ = ∅. We have s_{λ^{(a)}}^{∅}(p) = ∇^{∅} ∑_{σ∈S_{n}} ε(σ)p^{σ(λ^{(a)}+ρ)−ρ} by the Weyl character formula; this gives p^{−λ^{(a)}}s_{λ^{(a)}}^{∅}(p) = ∇^{∅} ∑_{σ∈S_{n}} ε(σ)p^{σ(λ^{(a)}+ρ)−λ^{(a)}−ρ}. When σ = id, we get ε(σ)p^{σ(λ^{(a)}+ρ)−λ^{(a)}−ρ} = 1. So it suffices to prove that lim_{a→+∞} ε(σ)p^{σ(λ^{(a)}+ρ)−λ^{(a)}−ρ} = 0 for all σ ≠ id; in this case, observe that

λ^{(a)} + ρ − σ(λ^{(a)} + ρ) = λ^{(a)} − σ(λ^{(a)}) + ρ − σ(ρ) = a(m − σ(m)) + ρ − σ(ρ) + o(a).

Since m satisfies Condition 5.2.4, the coordinates of m strictly decrease and are positive; this implies that p^{m−σ(m)} > 1.

Assume ♢ = h. Since 5.2.4 is satisfied, for a large enough the Young diagram of λ^{(a)} has a box at position (i, j) for all i ∈ {1, …, m} and j ∈ {1, …, n}. For such an integer a, by (4.4) we thus have s_{λ^{(a)}}^{h}(p) = ∇^{h} ∑_{w∈S_{m}×S_{n}} ε(w)p^{w(λ^{(a)}+ρ_{+})−ρ_{+}}, and we conclude as above.

Finally, assume ♢ = s. Since λ^{(a)} has only positive coordinates, we obtain, using the case ♢ = ∅ with the sequence λ^{(a)} − ρ,

lim_{a→+∞} p^{−λ^{(a)}}s_{λ^{(a)}}^{s}(p) = lim_{a→+∞} p^{−λ^{(a)}+ρ}s_{λ^{(a)}−ρ}^{∅}(p) ( ∏_{1≤i<j≤n} p_{i} + p_{j}) p^{−ρ} = ∇^{s}.

□

6.2. The transition matrix Π_{W^{♢}}. Let Π^{♢} be the restriction of Π_{W} to P^{♢}, and denote by Γ the Green function associated with Π^{♢}. For all μ, λ ∈ P^{♢}, we have

Γ(μ, λ) = \begin{cases}(Π^{♢})^{ℓ}(μ, λ), & if ℓ = |λ| − |μ| ≥ 0, \\ 0, & if |λ| < |μ| . \end{cases}

In particular Γ(μ, λ) = 0 if λ ∉ P^{♢}. We consider the Martin kernel K(μ, λ) = \frac{Γ(μ,λ)}{Γ(0,λ)}.

In order to apply Theorem 2.3.1, we want to prove that, almost surely, K(·, W_{ℓ}) converges everywhere to the harmonic function ψ(·) defined in (6.1). By definition of Π^{♢}, we have (Π^{♢})^{ℓ}(μ, λ) = card(ST^{♢}(λ/μ))p^{λ−μ}, where ST^{♢}(λ/μ) is the set of standard ♢-tableaux of shape λ/μ (see the remark after Theorem 5.2.3). Indeed, all the paths from μ to λ have the same probability p^{λ−μ}, and we have seen that there are card(ST^{♢}(λ/μ)) such tableaux. By Proposition 4.3.3, we have card(ST^{♢}(λ/μ)) = f_{λ/μ}^{♢}. According to Proposition 5.2.5, given any sequence λ^{(a)} of weights of the form λ^{(a)} = am + o(a), for large enough a we can write

Γ(μ, λ^{(a)}) = f_{λ^{(a)}/μ}^{♢} · p^{λ^{(a)}−μ} = p^{λ^{(a)}−μ} ∑_{γ∈P} f_{λ^{(a)}−γ}^{♢} · K_{μ,γ}^{♢}.

Since Γ(0, λ^{(a)}) = f_{λ^{(a)}}^{♢}p^{λ^{(a)}}, for a large enough this yields

K(μ, λ^{(a)}) = p^{−μ} ∑_{γ∈P} K_{μ,γ}^{♢} \frac{f_{λ^{(a)}−γ}^{♢}}{f_{λ^{(a)}}^{♢}} = p^{−μ} ∑_{γ∈P} K_{μ,γ}^{♢}p^{γ} \frac{f_{λ^{(a)}−γ}^{♢} · p^{λ^{(a)}−γ}}{f_{λ^{(a)}}^{♢} · p^{λ^{(a)}}} ,

so that

(6.3)  K(μ, λ^{(a)}) = p^{−μ} ∑_{γ weight of V^{♢}(μ)} K_{μ,γ}^{♢}p^{γ} \frac{Γ(0, λ^{(a)} − γ)}{Γ(0, λ^{(a)})}.

Now we have the following proposition.

Proposition 6.2.1. Assume Condition 5.2.4 is satisfied, and consider sequences (λ^{(a)})_{a∈ℕ} and (μ^{(a)})_{a∈ℕ} in P^{♢} such that λ^{(a)} = am + o(a^{δ+ \frac{1}{2}} ) for some δ > 0 and μ^{(a)} = o(a^{1/2}). Then

lim_{a→+∞} \frac{Γ(0, λ^{(a)} − μ^{(a)})}{Γ(0, λ^{(a)})} = 1.

Proof. For ♢ = ∅, s, h, we get P^{♢} = C^{♢}∩ℤ^{N}, and the semigroup C^{♢} satisfies hypothesis (h1) of § 2.4. Moreover, the random walk W satisfies (h2) and (h3). The proposition is thus a direct consequence of Theorem 2.4.1. □

The strong law of large numbers for square integrable independent and identically distributed random variables tells us that for all δ > 0 we get W_{a} = am + o(a^{δ+ \frac{1}{2}} ) almost surely. This leads to the following corollary.

Corollary 6.2.2. Assume Condition 5.2.4 is satisfied, and fix γ ∈ P. Then

lim_{a→+∞} \frac{Γ(0, W_{a} − γ)}{Γ(0, W_{a})} = 1 (a.s.).

We now may state the main result of this section. We denote by (W_{ℓ}^{♢})_{ℓ≥0} the random walk (W_{ℓ})_{ℓ≥0} conditioned to never exit P^{♢}.

Theorem 6.2.3. Assume Condition 5.2.4 is satisfied. Then the Markov chains (H_{ℓ}^{♢})_{ℓ≥0} and (W_{ℓ}^{♢})_{ℓ≥0} have the same transition matrix.

Proof. The strong law of large numbers says that W_{a} = am + o(a) a.s. Combined with (6.3), this implies that

lim_{a→+∞} K(μ, W_{a}) = lim_{a→+∞} p^{−μ} ∑_{γ weight of V^{⋄suit}(μ)} p^{γ} · K_{μ,γ}^{♢} \frac{Γ(0, W_{a} − γ)}{Γ(0, W_{a})}  (a.s.).

The set V^{♢}(μ) being finite, by Corollary 6.2.2 we thus get

(6.4) L := lim_{a→+∞} K(μ, W_{a}) = p^{−μ} ∑_{γ weight of V^{♢}(μ)} p^{γK_{μ,γ}^{♢}} = p^{−μ}s_{μ}^{♢}(p) = ψ^{♢}(μ) (a.s.).

Hence, by Theorem 2.3.1, we obtain ψ^{♢} = ch_{P^{♢}} for some constant c > 0, where h_{P^{♢}} is the harmonic function associated with the restriction of (W_{ℓ})_{ℓ≥0} to P^{♢} and defined in Subsection 2.2. By Theorem 5.2.3, we thus deduce

Π_{h_{P^{♢}}}(μ, λ) = Π_{ψ}(μ, λ) = Π_{H^{♢}}(μ, λ) = \frac{s_{λ}^{♢}(p)}{s_{μ}^{♢}(p)}δ_{μ⇝λ}^{♢}.

□

6.3. Some consequences. As a direct consequence of Theorem 6.2.3, we obtain the following corollary.

Corollary 6.3.1. Under the assumptions of Theorem 6.2.3, for all λ ∈ P^{♢}, we have

ℙ[W_{ℓ} ∈ P^{♢} for all ℓ ≥ 0 | W_{0} = λ] = \frac{p^{−λ}s_{λ}^{♢}(p)}{∇^{♢}},

where ∇^{♢} was defined in (6.2).

Proof. Recall that the function h_{P^{♢}} : λ ⟼ ℙ [W_{ℓ} ∈ P^{♢} for all ℓ ≥ 0 | W_{0} = λ] is harmonic. By Theorem 6.2.3, there is a positive constant c such that h_{P^{♢}}(λ) = cp^{−λ}s_{λ}^{♢}(p). Now, for any sequence of dominant weights (λ^{(a)})_{a} with λ^{(a)} = am + o(a), we get

lim_{a→+∞} ℙ [W_{ℓ} ∈ P^{♢} for all ℓ ≥ 0 | W_{0} = λ^{(a)}]

= lim_{a→+∞} ℙ [λ^{(a)} + X_{1} + ⋯ + X_{ℓ} ∈ P^{♢} for all ℓ ≥ 1] = 1.

On the other hand, by Proposition 6.1.1, we get lim_{a→+∞} p^{−λ(a)}s_{λ(a)}(p) = ∇^{♢} so that

c = \frac{1}{∇^{♢}}. □

We can also recover the asymptotic behaviors of f_{λ/μ}^{∅}, f_{λ/μ}^{s} and f_{λ/μ}^{h} without using the asymptotic representation theory of the symmetric and spin symmetric groups (see [13] and [17]).

Theorem 6.3.2. Suppose that the vector m satisfies Condition 5.2.4. If λ^{(ℓ)} = ℓm + o(ℓ^{α}) with α < 2/3, then for all μ ∈ P^{♢} we have

(6.5)  lim_{ℓ→∞} \frac{f_{λ^{(ℓ)}/μ}^{♢}}{f_{λ^{(ℓ)}}^{♢}} = s_{μ}^{♢}(p).

Proof. Consider a sequence of dominant weights of the form λ^{(ℓ)} = ℓm + o(ℓ^{α}). By Proposition 5.2.5, we have

(6.6)  \frac{f_{λ^{(ℓ)}/μ}^{♢}}{f_{λ^{(ℓ)}}^{♢}} = ∑_{γ∈P} K_{μ,γ}^{♢} \frac{f_{λ^{(ℓ)}−γ}^{♢}}{f_{λ^{(ℓ)}}^{♢}} = ∑_{γ∈P} K_{μ,γ}^{♢} \frac{f_{λ^{(ℓ)}−γ}^{♢} · p^{λ^{(ℓ)}−γ}}{f_{λ^{(ℓ)}}^{♢} · p^{λ^{(ℓ)}}} p^{γ},

where the sums have finitely many terms since V^{♢}(μ) is finite. For all γ ∈ P, we have

\frac{f_{λ^{(ℓ)}−γ}^{♢} · p^{λ^{(ℓ)}−γ}}{f_{λ^{(ℓ)}}^{♢}p^{λ^{(ℓ)}}} = \frac{ℙ[W_{1} ∈ P^{♢}, …, W_{ℓ} ∈ P^{♢}, W_{ℓ} = λ^{(ℓ)} − γ]}{ℙ[W_{1} ∈ P^{♢}, …, W_{ℓ} ∈ P^{♢}, W_{ℓ} = λ^{(ℓ)}]},

and this quotient tends to 1 when ℓ → +∞, by Theorem 2.4.1. This implies

lim_{ℓ→+∞} \frac{f_{λ^{(ℓ)}/μ}^{♢}}{f_{λ^{(ℓ)}}^{♢}} = ∑_{γ∈P} K_{μ,γ}^{♢}p^{γ} = s_{μ}^{♢}(p).

□

7. Appendix: RSK correspondence and crystal basis theory

7.1. RSK correspondence. We now turn to the proof of Proposition 4.3.3. We first need to interpret the RSK correspondence in terms of crystal basis theory. We refer the reader to [11] (♢ = ∅), [1] (♢ = h), and [5] (♢ = s) for detailed expositions. With each irreducible representation V^{♢}(λ), its crystal graph B^{♢}(λ) is associated, which is an oriented graph with arrows →^{i} colored by symbols i ∈ {1, …, n − 1} for 𝔤 = 𝔤𝔩(n), i ∈ \{\overline{m − 1}, …, \overline{1}, 0, 1, …, n−1\} for 𝔤 = 𝔤𝔩(m, n) and i ∈ \{1, …, n−1, \overline{1}\} for 𝔤 = 𝔮(n).

Below we provide the crystal B^{♢} of the defining representation V^{♢}:

for 𝔤 = 𝔤𝔩(n)  B^{∅} is 1 →^{1} 2 →^{2} ⋯ →^{n−1} n,
for 𝔤 = 𝔤𝔩(m, n) B^{h} is \overline{m} →^{\overline{m−1}} \overline{m − 1} →^{\overline{m−2}} ⋯ →^{\overline{1}} \overline{1} →^{0} 1 →^{1} 2 →^{2} ⋯ →^{n−1} n,
for 𝔤 = 𝔮(n)  B^{s} is →^{1} ; −−→_{\overline{1}}2 →^{2} ⋯ →^{n−1} n.

Observe that the vertices of B^{♢} coincide with the letters of A^{♢}. The vertices of (B^{♢})^{⊗ℓ} are thus labeled by the words of (A^{♢})^{ℓ} by identifying each vertex b = x_{1} ⊗ ⋯ ⊗ x_{ℓ} of (B^{♢})^{⊗ℓ} with the word b = x_{1} ⋯ x_{ℓ}.

More generally, any representation M^{♢} (irreducible or not) appearing in a tensor product (V^{♢})^{⊗ℓ} admits a crystal B^{♢}(M). In this paper, each crystal B(M) is realized as a subcrystal of a crystal (B^{♢})^{⊗ℓ}. The crystal B^{♢}(M) is graded by the weights of 𝔤. There is a map wt : B^{♢}(M) → P. To obtain the decomposition of M^{♢} in its irreducible components, it then suffices to obtain the decomposition of B^{♢}(M) into its connected components. The crystal B^{♢}(M ⊗ N) = B^{♢}(M) ⊗ B^{♢}(N) associated with the tensor product M ⊗ N of two representations can be constructed from the crystal of M and N by simple combinatorial rules. A highest weight vertex in B^{♢}(M) is a vertex b for which no arrow b′ →^{i} b exists in B^{♢}(M); a lowest weight vertex in B^{♢}(M) is a vertex b for which no arrow b →^{i} b′ exists in B^{♢}(M).

Let σ_{0} be the element of the Weyl group of 𝔤 defined by

\{ \begin{matrix}σ_{0}(β_{1}, β_{2}, …, β_{n}) & = (β_{n}, β_{n−1}, …, β_{1}) & for all β ∈ ℤ^{n}, & if ♢ = ∅, s, \\ σ_{0}(β\overline{m}, …, β\overline{1}, β_{1}, …, β_{n}) & = (β\overline{1}, … β\overline{m}, β_{n}, …, β_{1}) & for all β ∈ ℤ^{m+n}, & if ♢ = h. \end{matrix}

For ♢ = ∅ and λ ∈ P^{∅}, the crystal B^{∅}(λ) contains a unique highest weight vertex b^{∅,λ} and a unique lowest weight vertex b_{λ}^{∅}. They have respective weights λ and σ_{0}(λ). For ♢ = s and λ ∈ P^{s}, the crystal B^{s}(λ) contains a unique highest weight vertex b^{s,λ} but may admit several lowest weight vertices. Nevertheless it admits a unique lowest weight vertex b_{λ}^{s} with weight σ_{0}(λ). For ♢ = h and λ ∈ P^{h}, the crystal B^{s}(λ) may admit several highest or lowest weight vertices, and the situation is more complicated.

By crystal basis theory, for ♢ ∈ {∅, h, s} the multiplicity of V^{♢}(λ) in M^{♢} is given by the number of highest weight vertices of weight λ in B^{♢}(M) or equivalently by the number of its lowest weight vertices of weight σ_{0}(λ).

Lemma 7.1.1. Assume that ♢ ∈ {∅, s}, and consider u ⊗ v ∈ B^{♢}(λ) ⊗ B^{♢}(μ), where λ, μ ∈ P^{♢}. Then

(1) for ♢ = ∅, the vertex u ⊗ v is a highest weight vertex only if u = b^{∅,λ},

(2) for ♢ = s, the vertex u ⊗ v is a lowest weight vertex only if v = b_{μ}^{s}.

Remark. Assertion (1) does not hold in general for ♢ ∈ {h, s}. Moreover, Assertion (2) also fails when ♢ = h, which causes some complications. The lack of Assertion (1) for ♢ ∈ {h, s} explains also why in these cases the paths which remain in P^{♢} are not fixed by the Pitman transforms we have defined.

Two crystals B and B′ are isomorphic when there exists a bijection ϕ : B → B′ which respects the graph structure, i.e., which has the property that ϕ(a) →^{i} ϕ(b) in B′ if and only if a →^{i} b in B. When B and B′ are crystals associated with irreducible representations, such a crystal isomorphism exists if and only if these representations are isomorphic, and in that case it is unique. For any w ∈ (B^{♢})^{⊗ℓ}, write B^{♢}(w) for the connected component of (B^{♢})^{⊗ℓ} containing w. We can now interpret Theorem 4.3.2 in terms of crystal basis theory.

Theorem 7.1.2. Consider two vertices w_{1} and w_{2} of (B^{♢})^{⊗ℓ}. Then

(1) P^{♢}(w_{1}) = P^{♢}(w_{2}) if and only if B^{♢}(w_{1}) is isomorphic to B^{♢}(w_{2}) and the unique associated isomorphism sends w_{1} on w_{2}.

(2) Q^{♢}(w_{1}) = Q^{♢}(w_{2}) if and only if B^{♢}(w_{1}) = B^{♢}(w_{2}).

(3) For any standard ♢-tableau T, the set of words B^{♢}(T) defined in § 4.3 has the structure of a crystal graph isomorphic to the abstract crystal B^{♢}(λ), where λ is the shape of T.

(4) If we denote by ϕ : B^{♢}(λ) → B^{♢}(T) this isomorphism, we have wt(b) = wt(ϕ(b)) for all b ∈ B^{♢}(T), that is, the weight graduation defined on the abstract crystal B^{♢}(T) is compatible with the weight graduation defined on words.

7.2. Proof of Proposition 4.3.3. We finish this section with the proof of a crucial consequence of the Robinson–Schensted–Knuth correspondence.

Consider μ ∈ P^{♢} and T a standard tableau of shape μ. Let ℓ be a nonnegative integer and U_{ℓ,T}^{♢} be the set of pairs (P, Q), where Q is a ♢-standard tableau with ℓ + |μ| boxes containing T as a subtableau (that is, T is the subtableau obtained by considering only the entries 1, …, |μ| of Q) and P a ♢-tableau with the same shape as Q. By Theorem 4.3.2, the restriction of θ_{ℓ+|μ|}^{♢} to the subset B^{♢}(T) × (A^{♢})^{ℓ} ⊂ A_{ℓ+|μ|}^{♢} yields the one to one correspondence

θ_{ℓ,T}^{♢} : \{ \begin{matrix}B^{♢}(T) ⊗ (B^{♢})^{⊗ℓ} & → & U_{ℓ,T}^{♢} \\ w_{T} ⊗ w & ↦ & (P^{♢}(w_{T} w), Q^{♢}(w_{T} w)). \end{matrix}

Indeed, for any u ∈ (B^{♢})^{⊗ℓ+|μ|}, T is a subtableau of Q^{♢}(u) if and only if u can be written in the form u = w_{T} ⊗ w, with w_{T} ∈ B^{♢}(T) and w ∈ (B^{♢})^{⊗ℓ}. By crystal basis theory, for (B^{♢})^{⊗ℓ+|μ|}, the number of connected components of B^{♢}(T) ⊗ (B^{♢})^{⊗ℓ} isomorphic to some B^{♢}(λ) is equal to f_{λ/μ}^{♢}; using Theorem 7.1.2, we see that it coincides with the number of standard ♢-tableaux of shape λ containing T as a subtableau. There is a natural bijection between the set of such tableaux and the set of skew standard ♢-tableaux of shape λ/μ: to any standard tableau Q containing T, it associates the skew tableau obtained by deleting the boxes of T in Q and subtracting |μ| from the entries of the remaining boxes. This proves Assertion (1) of Proposition 4.3.3.

Our method to prove Assertion (2) of Proposition 4.3.3 depends on ♢.

For ♢ = ∅, let b = b_{1} ⊗ b_{2} be a highest weight vertex in B^{∅}(κ) ⊗ B^{∅}(μ) of weight λ. By Lemma 7.1.1, we must have b_{1} = b^{∅,κ}. Since wt(b) = wt(b_{1}) + wt(b_{2}), this implies that b_{2} ∈ B^{♢}(μ) has weight λ − κ. Therefore m_{κ,μ}^{∅,λ} ≤ K_{μ,λ−κ}^{∅} since we can define an injective map from the set of highest weight vertices of weight λ in B^{∅}(κ) ⊗ B^{∅}(μ) to the set of vertices of weight λ − κ in B^{∅}(μ).

For ♢ = s, let b = b_{1} ⊗ b_{2} be a lowest weight vertex in B^{s}(κ) ⊗ B^{s}(μ) of weight λ. We must have b_{2} = b_{μ}^{s}, so w(b_{1}) = σ_{0}(λ) − σ_{0}(μ) = σ_{0}(λ − μ). Similarly, we deduce that m_{κ,μ}^{s,λ} = m_{μ,κ}^{s,λ} ≤ K_{κ,σ_{0}(λ−μ)}^{s}. But K_{κ,σ_{0}(λ−μ)}^{s} = K_{κ,λ−μ}^{s}, since σ_{0} is an element of the Weyl group of 𝔮(n). Thus m_{μ,κ}^{s,λ} ≤ K_{κ,λ−μ}^{s}, as desired.

It remains to consider the case where ♢ = h, i.e., the case of 𝔤𝔩(m, n). Since Lemma 7.1.1 is no longer true in this case, we shall need a different strategy. We use the Littlewood–Richardson rule established in [10]. We say that a word w = x_{1} ⋯ x_{ℓ} with letters in ℤ_{>0} is a lattice permutation if, for k = 1, …, ℓ and all positive integers i, the number of letters i in the prefix w^{(k)} = x_{1} ⋯ x_{k} is greater than or equal to the number of letters i + 1.

Consider λ, μ, κ in P^{h} such that |μ| = |λ| − |κ|. Decompose the diagram of λ into λ^{(1)} (obtained by considering its first m rows) and λ^{(2)}, as in § 3.3. We denote by LR_{μ,κ}^{λ} the set of tableaux T obtained by filling the Young diagram λ/κ with positive integers (see Example 7.2.2) such that:

(1) the rows of T weakly increase from left to right,

(2) the columns of T strictly increase from top to bottom,

(3) the word w obtained by reading first the m rows of (λ/κ)^{(1)} from right to left and top to bottom, next the n columns of (λ/κ)^{(2)} from right to left and top to bottom, is a lattice permutation such that, for all integers k ≥ 1, the number of letters k in w is equal to the length of the k-th row of the Young diagram of μ, that is the k-th coordinate of (μ^{(1)}, (μ^{(2)})′), where (μ^{(2)})′ is the conjugate partition of μ^{(2)}.

We obtain the following proposition.

Proposition 7.2.1 ([10]). With the previous notations, we have m_{μ,κ}^{h,λ} = card(LR_{μ,κ}^{λ}).

By the previous proposition, in order to prove that m_{κ,μ}^{h,λ} ≤ K_{μ,λ−κ}^{h} it suffices to construct an embedding θ from LR_{μ,κ}^{λ} into the set of h-tableaux of shape μ and weight λ − κ. We proceed as follows. Consider T ∈ LR_{μ,κ}^{λ} and write R\overline{m}, …, R\overline{1} for the rows with boxes in λ^{(1)} and C_{1}, …, C_{n} for the columns with boxes in λ^{(2)}. In particular, for i = 1, …, m and j = 1, …, n, the row R\overline{i} contains λ(1) ; \overline{i} − κ(1) ; \overline{i} letters, and the column C_{j} contains λ_{j}^{(2)} − κ_{j}^{(2)} letters.

We want to define the h-tableau θ(T). We first construct recursively a tableau T^{(1)} with λ_{k}^{(1)} − κ_{k}^{(1)} letters \overline{k} for k = 1, …, m. We begin by defining T\overline{m} as the row with λ(1) ; \overline{m} − κ(1) ; \overline{m} letters \overline{m}. Assume that T\overline{k+1}, k ∈ \{2, …, m\}, is already constructed. Then T\overline{k} is obtained by adding a letter \overline{k} in the i-th row of T\overline{k+1} for each occurrence of the integer i in R\overline{k}.

Set T^{(1)} = T\overline{1}. We construct θ(T) by adding successively letters to T^{(1)}. First define T_{1} by adding a letter 1 in the i-th row of T\overline{1} for each integer i in C_{1}. Now, if T_{k} is given, for some k ∈ {1, …, m − 1}, we construct T_{k+1} by adding a letter k in the i-th row of T_{k} for each integer i appearing in C_{k}. Finally, we set θ(T) = T_{n}. Observe that, by construction, the k-th row of θ(T) contains as many boxes as the number of letters k in the lattice permutation w associated with T by Assertion (3). Moreover, θ(T) is an h-tableau since w is a lattice permutation. It has shape μ and weight λ − κ, as desired. Moreover, the map θ is injective since θ(T) records both the number and the positions of the letters k in the skew shape λ − κ. This proves that m_{κ,μ}^{h,λ} ≤ K_{μ,λ−κ}^{h}, as desired.

Example 7.2.2. Take λ = (3, 3, 3 | 3, 3) with m = n = 3, κ = (2, 0, 0 | 0, 0), and μ = (3, 3, 2 | 3, 2) = (3, 3, 2, 2, 2, 1). For

T = 1 1 1 2 2 2 3 3 4 4 5 5 6 ,

we get

θ(T) = ¯3 ¯2 ¯2 ¯2 ¯1 ¯1 ¯1 1 1 2 1 2 2 ,

where w = 1211322456345 is a lattice permutation.

References

[1] G. Benkart, S. J. Kang and M. Kashiwara, Crystal bases for the quantum superalgebra U_{q}(gl(m, n)), J. Amer. Math. Soc. 13 (2000), 295–331.

[2] P. Biane, P. Bougerol and N. O’Connell, Littelmann paths and Brownian paths, Duke Math. J. 130 (2005), 127–167.

[3] N. Bourbaki, Groupes et algèbres de Lie, Chapitres 4, 5 et 6, Hermann, 1968.

[4] W. Fulton, Young Tableaux, London Mathematical Society, Student Text, vol. 35, 1997.

[5] D. Grantcharov, J. H. Jung, S. J. Kang, M. Kashiwara and M. Kim, Crystal bases for the quantum queer superalgebra and semistandard decomposition tableaux, Trans. Amer. Math. Soc. 366 (2014), 457–489.

[6] B. Hall, Lie Groups, Lie Algebras, and Representations: An Elementary Introduction, Springer– Verlag, 2004.

[7] J. Hong and S. J. Kang, Introduction to Quantum Groups and Crystal Bases, Graduate Studies in Mathematics, vol. 42, Amer. Math. Soc., Providence, R.I., 2002.

[8] J. Hughes, R. King, J. Thierry-Mieg and J. Van der Jeugt, Character formulas for irreducible modules of the Lie superalgebras sl(m|n), J. Math. Phys. 31 (1990), 2278–2304.

[9] V. G. Kac, A sketch of Lie superalgebra theory, Commun. Math. Phys. 64 (1977), 31–64.

[10] S. J. Kang and J. H. Kwon, Tensor product of U_{q}(gl(m, n))-modules, Commun. Math. Phys. 224 (2001), 705–732.

[11] M. Kashiwara, On crystal bases, Canadian Mathematical Society, Conference Proceedings, vol. 16, 1995, pp. 155–197.

[12] S. V. Kerov and A. M. Vershik, The characters of the infinite symmetric group and probability properties of the Robinson–Schensted–Knuth algorithm, SIAM J. Alg. Disc. Meth. 7 (1986), 116– 124.

[13] S. V. Kerov, Asymptotic Representation Theory of the Symmetric Groups and its Applications in Analysis, Translations of Mathematical Monographs, vol. 212, Amer. Math. Soc. Providence, R.I., 2003.

[14] S. V. Kerov, A. Okounkov and G. Olshanski, The boundary of Young graphs with Jack edge multiplicities, Int. Math. Res. Notices 4 (1998), 173–199.

[15] C. Lecouvey, E. Lesigne and M. Peigné, Random walks in Weyl chambers and crystals, Proc. London Math. Soc. 104 (2012), 323–358.

[16] C. Lecouvey, E. Lesigne and M. Peigné, Conditioned one-way simple random walk and combinatorial representation theory, extended version of the present paper; arχiv:1202.3604.

[17] M. L. Nazarov, Factor representation of the infinite spin-symmetric group, J. Soviet Math. 62 (1992), 2690–2698.

[18] N. O’ Connell, A path-transformation for random walks and the Robinson–Schensted correspondence, Trans. Amer. Math. Soc. 355 (2003), 3669–3697.

[19] N. O’ Connell, Conditioned random walks and the RSK correspondence, J. Phys. A 36 (2003), 3049–3066.

[20] L. Serrano, The shifted plactic monoid, Math. Zeitschr. 266 (2010), 363–392.

[21] W. Woess, Denumerable Markov Chains, Textbooks in Mathematics, Europ. Math. Soc., 2009.

Laboratoire de Mathématiques et Physique Théorique (UMR CNRS 6083), Université François-Rabelais, Tours, Fédération de Recherche Denis Poisson - CNRS, Parc de Grandmont, 37200 Tours, France.