High probability events without low probability coordinates

Question

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!

Answer 1

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 2

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.