<p>Here is an example complementing Harry Yuen's answer. For a counter-example, it suffices to define appropriate $X,E$ and show that any large subset $E'\subseteq E$ must have a low probability co-ordinate of $E$ - a low probability co-ordinate of $E$ is necessarily a low probability co-ordinate of $E'$.</p>

<p>Also, I'll ignore the condition about entropy - appending $N$ independent uniformly distributed random variables to $X$ (and taking $E$ to $E\times \Sigma^N$) will increase $H(X)/(n+N)\log|\Sigma|$ to nearly $1$ without affecting whether such an $E'$ exists (I haven't though this through carefully).</p>

<p>Here's the example. Let $X$ be a random element of $\{0,1\}^n$ such that every vector with Hamming weight $1$ (i.e. vectors of the form $0\dots 010\dots 0$) have probability $(1-\epsilon)/n$ and the all-ones vector $1\dots 1$ has probability $\epsilon$. Let $E$ be the set of vectors with Hamming weight $1$.</p>

<p>Consider a subset $E'\subseteq E$. If $E'$ is not empty, it contains a vector of Hamming weight $1$, say $100\dots 0$ without loss of generality.
But $\Pr[X \in E'|X_i=1]=\frac{(1-\epsilon)/n}{(1-\epsilon)/n + \epsilon}$, which is less than $\epsilon$ if $n$ is about $2/\epsilon^2$.</p>

CC BY-SA 3.0
2012-08-19T16:55:29.383Z
2012-08-19T16:55:29.383Z
Colin McQuillan
<p>How does $\epsilon$ compare to $n$? If $\epsilon$ can be $O(1/\sqrt{n})$, then I think we can accomplish what you want. Let $B = \mbox{Supp}(X) - E$. Note that $B$ is given $\epsilon$ probability mass under $X$. Let $\lambda(i,\sigma)\epsilon$ denote the probability mass assigned to strings in $B$ such that the $i$th coordinate has symbol $\sigma$. </p>

<p>Suppose $(i,\sigma)$ were a low probability coordinate for some strings in $E$. Let $\delta(i,\sigma)$ denote the probability mass assigned to those strings. Then, by definition, $\frac{\delta(i,\sigma)}{\delta(i,\sigma) + \lambda(i,\sigma)\epsilon} \leq \epsilon$, implying that $\delta(i,\sigma) \leq 2\lambda(i,\sigma)\epsilon^2$. We can discard these low probability strings while only suffering a $\delta(i,\sigma)$ loss in prob. mass to $E$. </p>

<p>Continue doing this for all possible bad $(i,\sigma)$, and in the end we only discard at most $\sum_{i,\sigma} \delta(i,\sigma) \leq \sum_{i} \sum_{\sigma} 2\lambda(i,\sigma)\epsilon^2 \leq 2\sum_{i} \epsilon^2 = 2n\epsilon^2$. This uses the fact that for all $i$, $\sum_{\sigma} \lambda(i,\sigma) = 1$. </p>

<p>If you wanted $E'$ to have probability mass $1 -\gamma$, then $\epsilon$ needs to be such that $\epsilon + 2n\epsilon^2 \leq \gamma$, or that $\epsilon = O(\gamma/\sqrt{2n})$ suffices. </p>

<p>It's not clear to me at the moment whether this dependence on $n$ can be gotten rid of; I'll continue thinking about it.</p>

CC BY-SA 3.0
2012-08-17T18:51:00.863Z
Oh, I just realized that you're looking for a stronger requirement -- namely, that $E'$ doesn't have any low probability coordinates with respect to $E'$, not $E$. I'll come back to this later today.
Henry Yuen
CC BY-SA 3.0
2012-08-17T19:00:57.767Z
Thanks! I am looking for an epsilon that is constant, but can be arbitrarily small.
Or Meir
CC BY-SA 3.0
2012-08-17T09:38:39.347Z
2012-08-17T09:38:39.347Z
Henry Yuen
<p>Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small constant $\delta$. Let $E \subseteq \rm{Supp}(X)$ be an event in the support of $X$ such that $\Pr[X \in E] \ge 1 - \varepsilon$, where $\varepsilon$ is an arbitrarily small constant.</p>

<p>We say that a pair $(i,\sigma)$ is a <i>low probability coordinate</i> of $E$ if $\Pr[X \in E | X_i = \sigma] \le \varepsilon$. We say that a string $x \in \Sigma^n$ <i>contains a low probability coordinate of $E$</i> if $(i, x_i)$ is a low probability coordinate of $E$ for some $i$.</p>

<p>In general, some strings in $E$ may contain low probability coordinates of $E$. The question is can we always find a high probability event $E' \subseteq E$ such that no string in $E'$ contains a low probability coordinate of $E'$ (and not of $E$).</p>

<p>Thanks!</p>

<it.information-theory><pr.probability>
High probability events without low probability coordinates
Or Meir
# High probability events without low probability coordinates

(Asked by: username_0 on 2012-08-17)

Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small constant $\delta$. Let $E \subseteq \rm{Supp}(X)$ be an event in the support of $X$ such that $\Pr[X \in E] \ge 1 - \varepsilon$, where $\varepsilon$ is an arbitrarily small constant.

We say that a pair $(i,\sigma)$ is a *low probability coordinate* of $E$ if $\Pr[X \in E | X\_i = \sigma] \le \varepsilon$. We say that a string $x \in \Sigma^n$ *contains a low probability coordinate of $E$* if $(i, x\_i)$ is a low probability coordinate of $E$ for some $i$.

In general, some strings in $E$ may contain low probability coordinates of $E$. The question is can we always find a high probability event $E' \subseteq E$ such that no string in $E'$ contains a low probability coordinate of $E'$ (and not of $E$).

Thanks!

**Tags:** it.information-theory, pr.probability


---

## 2 answers

### Answer by username_1 on 2012-08-19. Score: 4 | Accepted answer

Here is an example complementing Harry Yuen's answer. For a counter-example, it suffices to define appropriate $X,E$ and show that any large subset $E'\subseteq E$ must have a low probability co-ordinate of $E$ - a low probability co-ordinate of $E$ is necessarily a low probability co-ordinate of $E'$.

Also, I'll ignore the condition about entropy - appending $N$ independent uniformly distributed random variables to $X$ (and taking $E$ to $E\times \Sigma^N$) will increase $H(X)/(n+N)\log|\Sigma|$ to nearly $1$ without affecting whether such an $E'$ exists (I haven't though this through carefully).

Here's the example. Let $X$ be a random element of $\{0,1\}^n$ such that every vector with Hamming weight $1$ (i.e. vectors of the form $0\dots 010\dots 0$) have probability $(1-\epsilon)/n$ and the all-ones vector $1\dots 1$ has probability $\epsilon$. Let $E$ be the set of vectors with Hamming weight $1$.

Consider a subset $E'\subseteq E$. If $E'$ is not empty, it contains a vector of Hamming weight $1$, say $100\dots 0$ without loss of generality.
But $\Pr[X \in E'|X\_i=1]=\frac{(1-\epsilon)/n}{(1-\epsilon)/n + \epsilon}$, which is less than $\epsilon$ if $n$ is about $2/\epsilon^2$.


---

### Answer by username_2 on 2012-08-17. Score: 6

How does $\epsilon$ compare to $n$? If $\epsilon$ can be $O(1/\sqrt{n})$, then I think we can accomplish what you want. Let $B = \mbox{Supp}(X) - E$. Note that $B$ is given $\epsilon$ probability mass under $X$. Let $\lambda(i,\sigma)\epsilon$ denote the probability mass assigned to strings in $B$ such that the $i$th coordinate has symbol $\sigma$.

Suppose $(i,\sigma)$ were a low probability coordinate for some strings in $E$. Let $\delta(i,\sigma)$ denote the probability mass assigned to those strings. Then, by definition, $\frac{\delta(i,\sigma)}{\delta(i,\sigma) + \lambda(i,\sigma)\epsilon} \leq \epsilon$, implying that $\delta(i,\sigma) \leq 2\lambda(i,\sigma)\epsilon^2$. We can discard these low probability strings while only suffering a $\delta(i,\sigma)$ loss in prob. mass to $E$.

Continue doing this for all possible bad $(i,\sigma)$, and in the end we only discard at most $\sum\_{i,\sigma} \delta(i,\sigma) \leq \sum\_{i} \sum\_{\sigma} 2\lambda(i,\sigma)\epsilon^2 \leq 2\sum\_{i} \epsilon^2 = 2n\epsilon^2$. This uses the fact that for all $i$, $\sum\_{\sigma} \lambda(i,\sigma) = 1$.

If you wanted $E'$ to have probability mass $1 -\gamma$, then $\epsilon$ needs to be such that $\epsilon + 2n\epsilon^2 \leq \gamma$, or that $\epsilon = O(\gamma/\sqrt{2n})$ suffices.

It's not clear to me at the moment whether this dependence on $n$ can be gotten rid of; I'll continue thinking about it.

> **Comments:**
> **username_2**: Oh, I just realized that you're looking for a stronger requirement -- namely, that $E'$ doesn't have any low probability coordinates with respect to $E'$, not $E$. I'll come back to this later today.  
> **username_0**: Thanks! I am looking for an epsilon that is constant, but can be arbitrarily small.  

---

