Models for partially ranked data on S_n/S_{n-k}

Intuition [Beginner]

In many real surveys, people do not rank all items — they rank only their top 3 or top 5 choices. These are partial rankings. The question becomes: how do you do spectral analysis when the data consists of partial rankings instead of full permutations?

The answer uses cosets. A partial ranking of $k$ items out of $n$ can be viewed as a coset $S_n/S_{n-k}$: you specify the top $k$ positions, and the remaining $n-k$ items can be in any order. The subgroup $S_{n-k}$ permutes the unranked items among themselves. The pair $(S_n,S_{n-k})$ forms a Gelfand pair, meaning the harmonic analysis on this coset space is especially simple.

Why does this concept exist? Because the Gelfand pair structure guarantees that the Fourier analysis on partial rankings decomposes into one-dimensional blocks (indexed by partitions with at most $k$ parts), making every computation explicit and interpretable.

Visual [Beginner]

A diagram showing a full ranking of 5 items as a permutation in $S_5$, with a downward arrow to a partial ranking showing only the top 2 items. The partial ranking corresponds to a coset containing all permutations with the same top 2, represented as a set of 6 permutations grouped together.

The projection map from full permutations to partial rankings collapses each coset (all permutations sharing the same top-$k$) into a single point.

Worked example [Beginner]

Consider $n=4$ items with partial rankings showing only the top $k=2$ positions. The coset space $S_4/S_2$ has $4!/(4-2)!=12$ elements.

Step 1. A respondent picks item 3 as best and item 1 as second. This corresponds to the coset of all permutations $\pi$ with $\pi (1)=3$ and $\pi (2)=1$. The remaining items 2 and 4 can be in either order in positions 3 and 4, so this coset contains exactly 2 permutations: $(3,1,2,4)$ and $(3,1,4,2)$.

Step 2. There are $4\times 3=12$ possible partial rankings (top 2 out of 4). Under the uniform distribution, each has probability $1/12$.

Step 3. The first-order spectral component on this coset space is indexed by the partition $(n-1,1)=(3,1)$, just like in the full ranking case. It detects which items are disproportionately likely to appear in the top 2 positions.

What this tells us: the spectral analysis of partial rankings mirrors the full ranking analysis, with the Gelfand pair structure ensuring that only partitions with at most $k$ parts contribute nonzero spectral components.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $1\le k\le n$. The subgroup $S_{n-k}\le S_n$ is the subgroup permuting the elements $\{k+1,\dots ,n\}$ among themselves while fixing $\{1,\dots ,k\}$. A partial ranking of the top $k$ items is a coset $\pi S_{n-k}$ for some $\pi \in S_n$, where $\pi$ specifies the ordering of the top $k$ positions.

The coset space $X=S_n/S_{n-k}$ has $n!/(n-k)!$ elements. A function $f:X\to \mathbb{C}$ on partial rankings lifts to a right-$S_{n-k}$-invariant function $\tilde{f}:S_n\to \mathbb{C}$ via $\tilde{f}(\pi )=f(\pi S_{n-k})$.

Definition (Gelfand pair). The pair $(G,K)$ of a finite group $G$ and a subgroup $K$ is a Gelfand pair if the algebra of $K$-bi-invariant functions on $G$ (i.e., functions satisfying $f(k_{1}g{k}_2)=f(g)$ for all $k_1,k_2\in K$) is commutative under convolution.

Definition (Spherical function). For a Gelfand pair $(G,K)$, the zonal spherical functions ${\omega }_1,{\omega }_2,\dots ,{\omega }_r$ are the distinguished basis of the $K$-bi-invariant function algebra, one for each irreducible representation of $G$ that appears in ${\mathrm{Ind}}_K^G(1)$. They satisfy:

$${\omega }_i(g)=\frac{1}{|K|}\sum _{k\in K}{\chi }_i(gk)$$

where ${\chi }_i$ is the character of the $i$-th irreducible constituent.

For $(S_n,S_{n-k})$, the spherical functions are indexed by partitions $\lambda$ of $n$ with at most $k$ parts, and are expressible in terms of the irreducible characters of $S_n$ via the branching rule from $S_n$ to $S_{n-k}$.

Counterexamples to common slips

• Every pair $(G,K)$ is not a Gelfand pair. The Gelfand pair condition requires the double coset algebra to be commutative, which is a strong constraint. For example, $(S_n,S_{n-3})$ is a Gelfand pair but $(S_n,\{e\})$ is not (the full group algebra is not commutative for $n\ge 3$).
• Partitions with more than $k$ parts do not contribute. The spectral decomposition of $L^2(S_n/S_{n-k})$ involves only irreducible representations indexed by partitions $\lambda ⊢n$ with $\ell (\lambda )\le k$ (at most $k$ parts). This is a consequence of the Frobenius reciprocity and the branching rule.
• Spherical functions are not characters. The zonal spherical functions are averages of characters over the subgroup $K$, which produces a different set of functions with different orthogonality relations.

Key theorem with proof [Intermediate+]

Theorem (Spectral decomposition on partial rankings — Diaconis 1989). Let $(S_n,S_{n-k})$ be the Gelfand pair for partial rankings of the top $k$ out of $n$ items. Then $L^2(S_n/S_{n-k})$ decomposes as an $S_n$-module:

$$L^2(S_n/S_{n-k})\cong \underset{\begin{array}{c}\lambda ⊢n\\ \ell (\lambda )\le k\end{array}}{⨁}{V}^{\lambda },$$

and the decomposition is multiplicity-free. For a probability distribution $f$ on $S_n/S_{n-k}$, the spherical Fourier transform $\hat{f}(\lambda )=⟨f,{\omega }_{\lambda }⟩$ for each partition $\lambda$ with $\ell (\lambda )\le k$ gives a complete spectral description of $f$, and $f$ is reconstructed by:

$$f(\pi S_{n-k})=\sum _{\begin{array}{c}\lambda ⊢n\\ \ell (\lambda )\le k\end{array}}\hat{f}(\lambda ){\omega }_{\lambda }(\pi ).$$

Proof. The proof has four steps.

Step 1 (Induced representation). The space $L^2(S_n/S_{n-k})$ is isomorphic to the induced representation ${\mathrm{Ind}}_{S_{n-k}}^{S_n}(1)$, where $1$ is the identity representation of $S_{n-k}$.

Step 2 (Decomposition by Frobenius reciprocity). By Frobenius reciprocity, the multiplicity of $V^{\lambda }$ in ${\mathrm{Ind}}_{S_{n-k}}^{S_n}(1)$ equals the multiplicity of $1$ in ${\mathrm{Res}}_{S_{n-k}}^{S_n}(V^{\lambda })$. By the branching rule for restricting from $S_n$ to $S_{n-k}$, the identity representation of $S_{n-k}$ appears in $V^{\lambda }{|}_{S_{n-k}}$ if and only if $\ell (\lambda )\le k$, and in that case the multiplicity is exactly 1.

Step 3 (Multiplicity-free). Since each multiplicity is 0 or 1, the decomposition is multiplicity-free. This is exactly the Gelfand pair condition: the algebra of $S_{n-k}$-bi-invariant functions is commutative because the decomposition has no repeated irreducibles.

Step 4 (Spherical inversion). The zonal spherical functions ${\omega }_{\lambda }$ for $\ell (\lambda )\le k$ form an orthogonal basis of the $S_{n-k}$-bi-invariant function space. The Fourier coefficient $\hat{f}(\lambda )=⟨f,{\omega }_{\lambda }⟩/⟨{\omega }_{\lambda },{\omega }_{\lambda }⟩$ extracts the projection of $f$ onto ${\omega }_{\lambda }$, and the inversion formula reconstructs $f$ from these coefficients. $\square$

Bridge. The spectral decomposition on partial rankings builds toward a unified statistical framework for any level of incompleteness in the data, and appears again in 07.05.11 as the special case $k=n$ (full rankings recover $L^2(S_n)$ with all partitions). The foundational reason the Gelfand pair structure matters is that multiplicity-free decomposition guarantees unique spherical functions, which generalises the orthonormality of characters in the full group case. This is exactly the content that identifies partial ranking analysis as a clean sub-theory of the full spectral analysis; the bridge is that the branching rule for $S_n\downarrow S_{n-k}$ controls which irreducible representations survive the projection from full to partial rankings, and putting these together with the zonal spherical functions, every statistical question about partially ranked data reduces to a finite computation indexed by partitions with at most $k$ parts.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Diaconis 1989: multiplicity-free decomposition via branching). The decomposition of $L^2(S_n/S_{n-k})$ into irreducible $S_n$-modules is indexed by partitions $\lambda ⊢n$ with $\ell (\lambda )\le k$, each with multiplicity 1. The partitions are enumerated by restricting the Young diagram to at most $k$ rows.

This was proved by Diaconis 1989 using the branching rule and Frobenius reciprocity. The multiplicity-free property is equivalent to the Gelfand pair condition.

Theorem 2 (Zonal spherical functions for $(S_n,S_{n-k})$). The zonal spherical functions are given by:

$${\omega }_{\lambda }(\pi )=\frac{{\chi }_{\lambda }(\pi \cdot S_{n-k})}{d_{\lambda }}=\frac{1}{d_{\lambda }\cdot |S_{n-k}|}\sum _{\sigma \in S_{n-k}}{\chi }_{\lambda }(\pi \sigma )$$

for partitions $\lambda$ with $\ell (\lambda )\le k$. These functions form an orthogonal basis of the $S_{n-k}$-bi-invariant function space with $\Vert {\omega }_{\lambda }{\Vert }_2^2=|S_n|/(d_{\lambda }|S_{n-k}{|}^2)$.

Theorem 3 (Spectral analysis of the Mallows model on partial rankings). For the Mallows model $f(\pi S_{n-k})\propto e^{-\theta d_C(\pi S_{n-k},e{S}_{n-k})}$ with the induced Cayley distance, the spherical Fourier coefficients have closed-form expressions:

$$\hat{f}(\lambda )=\frac{1}{Z}\sum _{j=0}^k{\alpha }_j^{(\lambda )}{e}^{-\theta j}$$

where ${\alpha }_j^{(\lambda )}$ depends on the character values of $\lambda$ on permutations with $j$ cycles moved within the top-$k$ positions.

Theorem 4 (Diaconis 1988: random walks on coset spaces). A random walk on $S_n/S_{n-k}$ driven by a $K$-bi-invariant measure $Q$ mixes in time determined by the spectral gap, which is the second-largest eigenvalue of the spherical Fourier transform of $Q$. The mixing time is $O(n\log n/(1-{\beta }^{\ast }))$ where ${\beta }^{\ast }$ is the largest non-principal spherical eigenvalue.

Theorem 5 (Connection to Jack polynomials). The zonal spherical functions for $(S_n,S_{n-k})$ are expressible as specialisations of Jack polynomials with parameter $\alpha =1$, evaluated at the eigenvalues of the appropriate coset-type matrices. This connects the spectral analysis of partial rankings to the broader theory of symmetric functions and hypergeometric functions of matrix argument.

This connection was developed by James 1978 and Macdonald 1995 in Symmetric Functions and Hall Polynomials.

Theorem 6 (Ewens sampling formula and partial rankings). The Ewens sampling formula on $S_n$, which assigns probability proportional to ${\theta }^{c(\pi )}$ where $c(\pi )$ is the number of cycles, has a natural interpretation as a Mallows model with Cayley distance. The induced distribution on partial rankings $S_n/S_{n-k}$ has spherical Fourier coefficients determined by the Stirling numbers.

Synthesis. The spectral analysis of partially ranked data via Gelfand pairs provides the foundational reason that the representation-theoretic framework extends from full to partial rankings without losing its clean structure. The central insight is that the branching rule for $S_n\downarrow S_{n-k}$ selects exactly the partitions with at most $k$ parts, and the Gelfand pair condition guarantees that the selected irreducibles appear without multiplicity. Putting these together with the zonal spherical functions, every statistical procedure for full rankings (spectral decomposition, testing, estimation) has a partial-ranking analogue obtained by restricting the spectral sum to partitions with at most $k$ rows. This is exactly the content that builds toward the exchangeability framework in 07.05.14 where the symmetric group acts on sequences and the spectral decomposition detects dependence structures. The bridge is between the combinatorics of Young diagrams with bounded row count and the statistics of top-$k$ rankings; the pattern generalises from $k=n$ (full rankings, all partitions) to $k=1$ (only the identity and standard representations survive), identifying the spectral components that vanish as one passes from full to partial data.

Full proof set [Master]

Proposition 1 (Branching rule and multiplicity-free condition). The multiplicity of the identity representation of $S_{n-k}$ in $V^{\lambda }{|}_{S_{n-k}}$ equals 1 if $\ell (\lambda )\le k$ and 0 otherwise.

Proof. Apply the branching rule iteratively. The restriction $S_n\downarrow S_{n-1}$ decomposes $V^{\lambda }={⨁}_{\square }{V}^{\lambda -\square }$ where the sum is over removable corners of the Young diagram of $\lambda$. After $k$ steps, the identity representation of $S_{n-k}$ (indexed by the single-row partition $(n-k)$) appears in $V^{\lambda }{|}_{S_{n-k}}$ iff there is a path from $\lambda$ to $(n-k)$ in the branching lattice. Such a path exists iff we can remove $k$ boxes from $\lambda$ to reach a single row of length $n-k$, which requires removing at most one box from each row, hence $\ell (\lambda )\le k$. When $\ell (\lambda )\le k$, the path is unique (remove boxes from the bottom row upward), giving multiplicity 1. $\square$

Proposition 2 (Orthogonality of zonal spherical functions). The zonal spherical functions ${\omega }_{\lambda }$ for $\ell (\lambda )\le k$ satisfy:

$$⟨{\omega }_{\lambda },{\omega }_{\mu }⟩=\frac{|S_n|}{d_{\lambda }|S_{n-k}{|}^2}{\delta }_{\lambda \mu }.$$

Proof. The spherical functions are obtained from the matrix coefficients of the irreducible representations by averaging over $K=S_{n-k}$. By the Schur orthogonality relations and the fact that the decomposition is multiplicity-free, the $K$-averaged matrix coefficients for distinct irreducibles are orthogonal. The norm is computed from the inner product formula:

$$⟨{\omega }_{\lambda },{\omega }_{\mu }⟩=\frac{1}{|S_n|}\sum _{\pi \in S_n}{\omega }_{\lambda }(\pi )\overline{{\omega }_{\mu }(\pi )}=\frac{1}{d_{\lambda }^2|S_{n-k}{|}^2}\sum _{\pi }\sum _{k_1,k_2}{\chi }_{\lambda }(\pi k_1)\overline{{\chi }_{\mu }(\pi k_2)}.$$

The double sum over $K$ collapses by orthogonality to ${\delta }_{\lambda \mu }\cdot |S_n|/d_{\lambda }\cdot |S_{n-k}{|}^2/|S_{n-k}{|}^2={\delta }_{\lambda \mu }|S_n|/d_{\lambda }$. Adjusting for the normalisation gives the stated result. $\square$

Connections [Master]

• Spectral analysis of permutation data 07.05.11. The partial ranking framework is a direct extension of the full spectral analysis in 07.05.11. Setting $k=n$ recovers the full spectral decomposition of $L^2(S_n)$ with all partitions; the Gelfand pair perspective specialises to the group algebra perspective when $K=\{e\}$.

• Metrics on the symmetric group 07.05.12. The metrics on $S_n$ from 07.05.12 extend to partial rankings via the quotient metric: $d_X(\pi S_{n-k},\sigma S_{n-k})={\min }_{{\tau }_1,{\tau }_2\in S_{n-k}}d(\pi {\tau }_1,\sigma {\tau }_2)$. The character-theoretic expressions for these quotient metrics use the same spherical functions that govern the spectral decomposition.

• Random walk upper bound lemma 07.05.05. The Upper Bound Lemma generalises to coset spaces: the total variation distance between a random walk on $S_n/S_{n-k}$ and the uniform distribution is bounded by the spherical Fourier coefficients, paralleling the character-sum bound in 07.05.05 but using zonal spherical functions instead of irreducible characters.

• De Finetti and exchangeability 07.05.14. The Gelfand pair structure that makes partial ranking analysis clean is the same symmetric group action that underlies exchangeability. The exchangeability theorem of de Finetti identifies distributions invariant under $S_n$, and the partial ranking analysis identifies distributions invariant under the larger subgroup $S_n\times S_{n-k}$ acting on cosets.

Historical & philosophical context [Master]

Diaconis developed the spectral analysis of partially ranked data in his 1989 paper A Generalization of Spectral Analysis ^{[Diaconis1989]}, identifying the Gelfand pair $(S_n,S_{n-k})$ as the structural reason the analysis remains explicit. The Gelfand pair theory was developed by Gelfand in the 1950s in the context of spherical functions on Lie groups, and adapted to finite groups by Curtis and Reiner, and by Delsarte 1973 in the context of association schemes.

The connection to Jack polynomials and symmetric function theory was developed by James 1978 and Macdonald 1995 ^{[Macdonald1995]} in Symmetric Functions and Hall Polynomials, who showed that the zonal spherical functions for $(S_n,S_{n-k})$ are special cases of the more general framework of zonal polynomials. Marden 1995 ^[Marden1995] provided the comprehensive statistical treatment in Analyzing and Modeling Rank Data, covering both full and partial ranking models.

Bibliography [Master]

@article{Diaconis1989partial,
  author = {Diaconis, Persi},
  title = {A Generalization of Spectral Analysis},
  journal = {J. Amer. Statist. Assoc.},
  volume = {84},
  year = {1989},
  pages = {694--701},
}

@book{Diaconis1988partial,
  author = {Diaconis, Persi},
  title = {Group Representations in Probability and Statistics},
  publisher = {Institute of Mathematical Statistics},
  year = {1988},
  series = {IMS Lecture Notes--Monograph Series},
  volume = {11},
}

@book{Marden1995partial,
  author = {Marden, John I.},
  title = {Analyzing and Modeling Rank Data},
  publisher = {Chapman \& Hall},
  year = {1995},
}

@book{Macdonald1995,
  author = {Macdonald, I. G.},
  title = {Symmetric Functions and Hall Polynomials},
  publisher = {Oxford University Press},
  year = {1995},
  edition = {2nd},
}