9
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henry Yuen Aug 17 '12 at 18:51
  • $\begingroup$ Thanks! I am looking for an epsilon that is constant, but can be arbitrarily small. $\endgroup$ – Or Meir Aug 17 '12 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.