# Young Diagrams and distinguishing between two distributions

Introduction:

The reference for everything is this paper.

The Robinson–Schensted–Knuth (RSK) algorithm is a well-known combinatorial algorithm with diverse applications throughout mathematics, computer science, and physics. Given a word $$w$$ with $$n$$ letters from the alphabet $$[d]$$, it outputs two semistandard Young tableaus $$(\text{P}, \text{Q}) = \text{RSK}(w)$$ with common shape given by some Young diagram $$\lambda \in \mathbb{N}^{d}$$ $$(\lambda_1 \geq \cdots \geq λ_d)$$. We write $$λ = \text{shRSK}(w).$$

Given a probability distribution $$\alpha = (\alpha_1,...,\alpha_d)$$ on alphabet $$[d]$$, an $$n$$-letter $$\alpha$$-random word $$w = (w_1, \cdots, w_n)$$, written as $$w \sim \alpha^{\otimes n}$$, is a random word in which each letter $$w_i$$ is independently drawn from $$[d]$$ according to $$\alpha$$. The Schur–Weyl distribution $$\text{SW}^{n}(\alpha)$$ is the distribution on Young diagrams given by $$\lambda = \text{shRSK}(w)$$.

Let the length of the $$i^{\text{th}}$$ row of a Young diagram be $$\lambda_i$$, for $$i \in [d]$$. From the paper referenced (Theorem $$1.4$$):

For $$k ∈ [d]$$, set $$ν_k = \text{min}\{1, α_k d\}$$. Then, $$α_kn−2\sqrt{ν_k n} \leq \underset{{\lambda \sim \text{SW}^{n}(\alpha)}}{\mathbb{E}}[\lambda_k]\leq α_kn +2\sqrt{ν_k n} .$$

From Proposition $$4.8$$,

Let $$\alpha \in [d]$$ be a probability distribution. Then for any $$k \in [d]$$, $$\underset{{\lambda \sim \text{SW}^{n}(\alpha)}}{\text{Var}} \left[λ_k\right] \leq16n.$$

Note that $$n$$ is the total length of all the rows of the Young diagram. That is $$\sum_{i = 1}^{d} \lambda_i = n.$$

If $$n$$ is much smaller than $$d$$, many of the rows may have a length of $$0$$.

The problem:

Let two probability distributions, on alphabet $$[2^{m}]$$, be $$\alpha$$ and $$\beta$$. Both of them are efficiently samplable.

It is known that

$$\alpha_i = \frac{1}{2^{m}},$$

for every $$i \in [2^{m}]$$, and

$$\beta_i = \frac{1}{2^{m/2}},$$ for every $$i \in [2^{m/2}]$$ and $$0$$ otherwise.

Input: For an $$n = \text{poly}(m)$$, we are either given a Young diagram $$\lambda$$ sampled from $$\text{SW}^{n}(\alpha)$$ or a Young diagram sampled from $$\text{SW}^{n}(\beta)$$.

Task: We want to distinguish between the two cases (in other words, tell which distribution the Young diagram came from.)

Is there a polynomial-time uniform classical distinguishing algorithm that distinguishes between these two cases?

My intuition is that there should exist no such distinguisher. Since $$n = \text{poly}(m)$$, the useful "signal" we get after looking at the length of each row of the Young diagram is inverse exponentially small --- whereas the "noise" is inverse polynomially large. Thus, the two cases would look exactly similar to any distinguisher.

Is there a statistical or a computational argument that makes this formal?

• 1. You have a typo in your statement of Theorem 1.4, the square roots should include the n. 2. Forget about computational efficiency, unless I am missing something the answer is "it's information theoretically impossible." You need n to be $\Omega(2^{m/2})$ to distinguish uniform from "uniform on a random half of the support" by a birthday paradox. Since the distribution of the tableau only depends on the sorted probability vector (see Definition 1.3) your setting is equivalent to getting $\lambda$ in the latter case. So for $n=$poly$(m)$, you can't information-theoretically distinguish. Nov 9, 2021 at 11:29
• @ClementC. Might you develop your comment into an answer? Nov 9, 2021 at 17:52
• @ClementC. I had a few questions. 1. $\alpha$ and $\beta$ are "uniform and uniform on a random half of the support." So, if we are given samples from $\alpha$ or $\beta$, it is true that we cannot distinguish between them without at least a sub-exponential number of samples. However, we are not sampling from $\alpha$ or $\beta$. We are sampling from $\text{SW}^{n}(\alpha)$ and $\text{SW}^{n}(\beta)$ --- $\text{SW}^{n}(\alpha)$ is the Plancherel distribution (see last line of page 1 of the paper) and I do not know what distribution $\text{SW}^{n}(\beta)$ is. Nov 9, 2021 at 17:52
• So, the two settings do not seem exactly similar Nov 9, 2021 at 17:52
• @AngryLion I expanded my comment into an answer. Nov 9, 2021 at 20:39

Even relaxing the "computationally efficient" requirement, it is information-theoretically impossible. We will use the following "folklore" fact, which can be viewed as a consequence of the birthday paradox:

Fact. Distinguishing with probability say $$2/3$$ between (1) the uniform distribution on $$[d]$$ and (2) a distribution on a subset of half the domain $$[d]$$, chosen uniformly at random, requires $$n=\Omega(\sqrt{d})$$ samples.

Let's call this problem $$(\star)$$. In our case, $$d=2^m$$, but note that the problem we want to solve is not an instance of $$(\star)$$: $$\alpha$$ is indeed the uniform distribution on $$d$$, but $$\beta$$ is a uniform distribution on a very specific, known subset of $$d/2$$ elements, and so the fact stating hardness of $$(\star)$$ does not apply directly (it's actually very easy to distinguish between the two with $$O(1)$$ samples!). But we also don't directly have access to the sequence of $$n$$ samples $$w$$, we only have access to them through $$\lambda := \mathrm{shRSK}(w)$$. So, well, it does apply. Let's see why.

From Definition 1.3 of [O'Donnell–Wright'16]:

The Schur–Weyl distribution $$\mathrm{SW}^n(\alpha)$$ is the distribution on Young diagrams given by $$\lambda := \mathrm{shRSK}(w)$$ [when $$w\sim \alpha^{\otimes n}$$]. Although it is not obvious, it is a fact that the distribution $$\mathrm{SW}^n(\alpha)$$ does not depend on the ordering of $$\alpha$$'s components.

What this means (if I am reading this correctly) is that $$\mathrm{SW}^n(\alpha)$$ only depends on the multiset of frequencies of $$\alpha$$, not on the labeling of the domain. In particular, all "uniform distributions on a subset of half the domain" lead to the same distribution $$\mathrm{SW}^n$$ over $$\lambda$$.

Which is exactly what we need to conclude. Suppose by contradiction we had an algorithm (even inefficient!) which distinguishes $$\mathrm{SW}^n(\alpha)$$ from $$\mathrm{SW}^n(\beta)$$ with probability at least $$2/3$$, given $$\lambda$$ from either of the two distributions (where $$n = o(2^{m/2})$$, i.e., $$n=o(\sqrt{d})$$). Then we could use it to solve $$(\star)$$ as follows: given $$n$$ samples (i.e., a word $$w$$) from an instance of $$(\star)$$, we compute $$\lambda = \mathrm{shRSK}(w)$$, and feed it into our purported algorithm. But the $$\lambda$$ is then either from $$\mathrm{SW}^n(\alpha)$$ or $$\mathrm{SW}^n(\beta)$$, so the algorithm can distinguish. This allows us to solve $$(\star)$$ with way too few samples, leading to a contradiction.

• If I misunderstood something (the whole argument relies on my understanding of Definition 1.3 of [OW16]), please let me know. Nov 9, 2021 at 20:36