<p>Even relaxing the &quot;computationally efficient&quot; requirement, it is information-theoretically impossible. We will use the following &quot;folklore&quot; fact, which can be viewed as a consequence of the birthday paradox:</p>
<p><strong>Fact.</strong> Distinguishing with probability say <span class="math-container">$2/3$</span> between (1) the uniform distribution on <span class="math-container">$[d]$</span> and (2) a distribution on a subset of half the domain <span class="math-container">$[d]$</span>, chosen uniformly at random, requires <span class="math-container">$n=\Omega(\sqrt{d})$</span> samples.</p>
<p>Let's call this problem <span class="math-container">$(\star)$</span>. In our case, <span class="math-container">$d=2^m$</span>, but note that the problem we want to solve is <em>not</em> an instance of <span class="math-container">$(\star)$</span>: <span class="math-container">$\alpha$</span> is indeed the uniform distribution on <span class="math-container">$d$</span>, but <span class="math-container">$\beta$</span> is a uniform distribution on a very specific, known subset of <span class="math-container">$d/2$</span> elements, and so the fact stating hardness of <span class="math-container">$(\star)$</span> does not apply directly <em>(it's actually very easy to distinguish between the two with <span class="math-container">$O(1)$</span> samples!)</em>. But we also don't directly have access to the sequence of <span class="math-container">$n$</span> samples <span class="math-container">$w$</span>, we only have access to them through <span class="math-container">$\lambda := \mathrm{shRSK}(w)$</span>. So, well, it <em>does</em> apply. Let's see why.</p>
<p>From Definition 1.3 of <a href="https://arxiv.org/abs/1612.00034" rel="nofollow noreferrer">[O'Donnell–Wright'16]</a>:</p>
<blockquote>
<p>The Schur–Weyl distribution <span class="math-container">$\mathrm{SW}^n(\alpha)$</span> is the distribution on Young diagrams given by <span class="math-container">$\lambda := \mathrm{shRSK}(w)$</span> [when <span class="math-container">$w\sim \alpha^{\otimes n}$</span>]. Although it is not obvious, it is a fact
that the distribution <span class="math-container">$\mathrm{SW}^n(\alpha)$</span> does not depend on the ordering of <span class="math-container">$\alpha$</span>'s components.</p>
</blockquote>
<p>What this means (if I am reading this correctly) is that <span class="math-container">$\mathrm{SW}^n(\alpha)$</span> only depends on the multiset of frequencies of <span class="math-container">$\alpha$</span>, not on the labeling of the domain. In particular, all &quot;uniform distributions on a subset of half the domain&quot; lead  to the same distribution <span class="math-container">$\mathrm{SW}^n$</span> over <span class="math-container">$\lambda$</span>.</p>
<p>Which is exactly what we need to conclude. Suppose by contradiction we had an algorithm (even inefficient!) which distinguishes <span class="math-container">$\mathrm{SW}^n(\alpha)$</span> from <span class="math-container">$\mathrm{SW}^n(\beta)$</span> with probability at least <span class="math-container">$2/3$</span>, given <span class="math-container">$\lambda$</span> from either of the two distributions (where <span class="math-container">$n = o(2^{m/2})$</span>, i.e., <span class="math-container">$n=o(\sqrt{d})$</span>). Then we could use it to solve <span class="math-container">$(\star)$</span> as follows: given <span class="math-container">$n$</span> samples (i.e., a word <span class="math-container">$w$</span>) from an instance of <span class="math-container">$(\star)$</span>, we compute <span class="math-container">$\lambda = \mathrm{shRSK}(w)$</span>, and feed it into our purported algorithm. But the <span class="math-container">$\lambda$</span> is then either from <span class="math-container">$\mathrm{SW}^n(\alpha)$</span> or <span class="math-container">$\mathrm{SW}^n(\beta)$</span>, so the algorithm can distinguish. This allows us to solve <span class="math-container">$(\star)$</span> with way too few samples, leading to a contradiction.</p>

CC BY-SA 4.0
2021-11-09T20:36:25.080Z
If I misunderstood something (the whole argument relies on my understanding of Definition 1.3 of [OW16]), please let me know.
Clement C.
CC BY-SA 4.0
2021-11-09T20:35:45.093Z
2021-11-13T07:55:31.643Z
2021-11-13T07:55:31.643Z
Clement C.
<p><strong>Introduction</strong>:</p>
<p>The reference for everything is <a href="https://arxiv.org/pdf/1612.00034.pdf" rel="nofollow noreferrer">this</a> paper.</p>
<blockquote>
<p>The Robinson–Schensted–Knuth (RSK) algorithm is a well-known
combinatorial algorithm with diverse applications throughout
mathematics, computer science, and physics. Given a word <span class="math-container">$w$</span> with <span class="math-container">$n$</span>
letters from the alphabet <span class="math-container">$[d]$</span>, it outputs two semistandard Young
tableaus <span class="math-container">$(\text{P}, \text{Q}) = \text{RSK}(w)$</span> with common shape
given by some Young diagram <span class="math-container">$\lambda \in \mathbb{N}^{d}$</span> <span class="math-container">$(\lambda_1
 \geq \cdots \geq λ_d)$</span>. We write <span class="math-container">$λ = \text{shRSK}(w).$</span></p>
<p>Given a probability distribution <span class="math-container">$\alpha = (\alpha_1,...,\alpha_d)$</span> on
alphabet <span class="math-container">$[d]$</span>, an <span class="math-container">$n$</span>-letter <span class="math-container">$\alpha$</span>-random word <span class="math-container">$w = (w_1, \cdots, 
 w_n)$</span>, written as <span class="math-container">$w \sim \alpha^{\otimes n}$</span>, is a random word in
which each letter <span class="math-container">$w_i$</span> is independently drawn from <span class="math-container">$[d]$</span> according to
<span class="math-container">$\alpha$</span>. The Schur–Weyl distribution <span class="math-container">$\text{SW}^{n}(\alpha)$</span> is the
distribution on Young diagrams given by <span class="math-container">$\lambda = \text{shRSK}(w)$</span>.</p>
</blockquote>
<p>Let the length of the <span class="math-container">$i^{\text{th}}$</span> row of a Young diagram be <span class="math-container">$\lambda_i$</span>, for <span class="math-container">$i \in [d]$</span>. From the paper referenced (Theorem <span class="math-container">$1.4$</span>):</p>
<blockquote>
<p>For <span class="math-container">$k ∈ [d]$</span>, set <span class="math-container">$ν_k = \text{min}\{1, α_k d\}$</span>. Then,
<span class="math-container">$$α_kn−2\sqrt{ν_k n}  \leq \underset{{\lambda \sim
 \text{SW}^{n}(\alpha)}}{\mathbb{E}}[\lambda_k]\leq α_kn +2\sqrt{ν_k n} 
 .$$</span></p>
</blockquote>
<p>From Proposition <span class="math-container">$4.8$</span>,</p>
<blockquote>
<p>Let <span class="math-container">$\alpha \in [d]$</span> be a probability distribution. Then for any <span class="math-container">$k \in
 [d]$</span>, <span class="math-container">$$\underset{{\lambda \sim
 \text{SW}^{n}(\alpha)}}{\text{Var}} \left[λ_k\right] \leq16n.$$</span></p>
</blockquote>
<p>Note that <span class="math-container">$n$</span> is the total length of all the rows of the Young diagram. That is
<span class="math-container">$$ \sum_{i = 1}^{d} \lambda_i = n.$$</span></p>
<p>If <span class="math-container">$n$</span> is much smaller than <span class="math-container">$d$</span>, many of the rows may have a length of <span class="math-container">$0$</span>.</p>
<hr />
<p><strong>The problem</strong>:</p>
<p>Let two probability distributions, on alphabet <span class="math-container">$[2^{m}]$</span>, be <span class="math-container">$\alpha$</span> and <span class="math-container">$\beta$</span>. Both of them are efficiently samplable.</p>
<p>It is known that</p>
<p><span class="math-container">$$\alpha_i = \frac{1}{2^{m}},$$</span></p>
<p>for every <span class="math-container">$i \in [2^{m}]$</span>, and</p>
<p><span class="math-container">$$\beta_i = \frac{1}{2^{m/2}},$$</span>
for every <span class="math-container">$i \in [2^{m/2}]$</span> and <span class="math-container">$0$</span> otherwise.</p>
<p><strong>Input</strong>: For an <span class="math-container">$n = \text{poly}(m)$</span>, we are either given a Young diagram <span class="math-container">$\lambda$</span> sampled from <span class="math-container">$\text{SW}^{n}(\alpha)$</span> or a Young diagram sampled from <span class="math-container">$\text{SW}^{n}(\beta)$</span>.</p>
<p><strong>Task</strong>: We want to distinguish between the two cases (in other words, tell which distribution the Young diagram came from.)</p>
<p>Is there a polynomial-time uniform classical distinguishing algorithm that distinguishes between these two cases?</p>
<hr />
<p>My intuition is that there should exist no such distinguisher. Since <span class="math-container">$n = \text{poly}(m)$</span>, the useful &quot;signal&quot; we get after looking at the length of each row of the Young diagram is inverse exponentially small --- whereas the &quot;noise&quot; is inverse polynomially large. Thus, the two cases would look exactly similar to any distinguisher.</p>
<p>Is there a statistical or a computational argument that makes this formal?</p>

CC BY-SA 4.0
2021-11-09T11:29:52.110Z
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.
Clement C.
CC BY-SA 4.0
2021-11-09T17:52:04.060Z
@ClementC. Might you develop your comment into an answer?
AngryLion
CC BY-SA 4.0
2021-11-09T17:52:35.237Z
@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.
AngryLion
CC BY-SA 4.0
2021-11-09T17:52:48.623Z
So, the two settings do not seem exactly similar
AngryLion
CC BY-SA 4.0
2021-11-09T17:59:45.033Z
@ClementC. Also, the Young diagram encodes not just a value but also a particular shape (looking at the length of its rows allows us to calculate the $n$ largest $\alpha_i$s or $\beta_i$s to very bad accuracy). That is, not only are we given samples from $\text{SW}^{n}(\alpha)$ and  $\text{SW}^{n}(\beta)$, we also are given $n = \text{poly}(m)$ largest probability values (upto a very bad accuracy) from either $\alpha$ or  $\beta$. In light of all this additional information, I am not sure how to directly port the bounds from traditional distribution testing settings.
AngryLion
CC BY-SA 4.0
2021-11-09T20:39:37.170Z
@AngryLion I expanded my comment into an answer.
Clement C.
<ds.algorithms><pr.probability><polynomial-time><oracles>
Young Diagrams and distinguishing between two distributions
AngryLion
# Young Diagrams and distinguishing between two distributions

(Asked by: username_0 on 2021-11-07)

**Introduction**:

The reference for everything is [this](https://arxiv.org/pdf/1612.00034.pdf) 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?

**Tags:** ds.algorithms, pr.probability, polynomial-time, oracles
> **Comments:**
> **username_1**: 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.  
> **username_0**: @ClementC. Might you develop your comment into an answer?  
> **username_0**: @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.  
> **username_0**: So, the two settings do not seem exactly similar  
> **username_0**: @ClementC. Also, the Young diagram encodes not just a value but also a particular shape (looking at the length of its rows allows us to calculate the $n$ largest $\alpha_i$s or $\beta_i$s to very bad accuracy). That is, not only are we given samples from $\text{SW}^{n}(\alpha)$ and  $\text{SW}^{n}(\beta)$, we also are given $n = \text{poly}(m)$ largest probability values (upto a very bad accuracy) from either $\alpha$ or  $\beta$. In light of all this additional information, I am not sure how to directly port the bounds from traditional distribution testing settings.  
> **username_1**: @AngryLion I expanded my comment into an answer.  

---

## 1 answers

### Answer by username_1 on 2021-11-09. Score: 3 | Accepted answer

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]](https://arxiv.org/abs/1612.00034):

> 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.

> **Comments:**
> **username_1**: If I misunderstood something (the whole argument relies on my understanding of Definition 1.3 of [OW16]), please let me know.  

---

