Zdarzenia o wysokim prawdopodobieństwie bez współrzędnych o niskim prawdopodobieństwie

Pozwolić $X$ być zmienną losową przyjmującą wartości w $\Sigma^n$ (dla jakiegoś dużego alfabetu $\Sigma$), który ma bardzo wysoką entropię - powiedzmy, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ dla arbitralnie małej stałej $\delta$. Pozwolić$E \subseteq \rm{Supp}(X)$ być wydarzeniem wspierającym $X$ takie, że $\Pr[X \in E] \ge 1 - \varepsilon$, gdzie $\varepsilon$ jest dowolnie małą stałą.

Mówimy, że pary to mało prawdopodobne współrzędnych z jeśli . Mówimy, że ciąg zawiera współrzędną niskiego prawdopodobieństwa jeśli jest współrzędną niskiego prawdopodobieństwa dla niektórych .$(i,\sigma)$$E$$\Pr[X \in E | X_i = \sigma] \le \varepsilon$$x \in \Sigma^n$ $E$$(i, x_i)$$E$$i$

Zasadniczo niektóre ciągi w mogą zawierać współrzędne o niskim prawdopodobieństwie . Pytanie brzmi: czy zawsze możemy znaleźć zdarzenie o wysokim prawdopodobieństwie tak że żaden ciąg w zawiera współrzędnej małego prawdopodobieństwa (a nie ).$E$$E$$E' \subseteq E$$E'$$E'$$E$

Dzięki!

Oto przykład uzupełniający odpowiedź Harry'ego Yuena. Dla przeciwnego przykładu wystarczy zdefiniować odpowiedni i pokazać, że jakikolwiek duży podzbiór$X,E$$E'\subseteq E$ musi mieć małą współrzędną prawdopodobieństwa wynoszącą $E$ - współrzędna niskiego prawdopodobieństwa $E$ jest koniecznie współrzędną niskiego prawdopodobieństwa $E'$.

Zignoruję też warunek dotyczący entropii - dołączania $N$ niezależne, równomiernie rozmieszczone zmienne losowe na $X$ (i biorąc $E$ do $E\times \Sigma^N$) wzrośnie $H(X)/(n+N)\log|\Sigma|$ prawie $1$ bez wpływu na to, czy takie $E'$ istnieje (nie przemyślałem tego dokładnie).

Oto przykład. Pozwolić$X$ być losowym elementem $\{0,1\}^n$ tak, że każdy wektor o wadze Hamminga $1$ (tj. wektory formy $0\dots 010\dots 0$) mają prawdopodobieństwo $(1-\epsilon)/n$ i wektor wszystkich $1\dots 1$ ma prawdopodobieństwo $\epsilon$. Pozwolić$E$ być zbiorem wektorów o wadze Hamminga $1$.

Rozważ podzbiór $E'\subseteq E$. Gdyby$E'$ nie jest pusty, zawiera wektor masy Hamminga $1$, mówić $100\dots 0$bez straty ogólności. Ale$\Pr[X \in E'|X_i=1]=\frac{(1-\epsilon)/n}{(1-\epsilon)/n + \epsilon}$, który jest mniejszy niż $\epsilon$ gdyby $n$ jest o $2/\epsilon^2$.

Jak $\epsilon$ porównać do $n$? Gdyby$\epsilon$ może być $O(1/\sqrt{n})$, więc myślę, że możemy osiągnąć to, czego chcesz. Pozwolić$B = \mbox{Supp}(X) - E$. Zauważ, że$B$ jest podawany $\epsilon$ masa prawdopodobieństwa poniżej $X$. Pozwolić$\lambda(i,\sigma)\epsilon$ oznacza masę prawdopodobieństwa przypisaną do łańcuchów w $B$ takie, że $i$współrzędna ma symbol $\sigma$.

Przypuszczać $(i,\sigma)$ były współrzędnymi niskiego prawdopodobieństwa dla niektórych ciągów w $E$. Pozwolić$\delta(i,\sigma)$oznacza masę prawdopodobieństwa przypisaną do tych ciągów. Następnie z definicji$\frac{\delta(i,\sigma)}{\delta(i,\sigma) + \lambda(i,\sigma)\epsilon} \leq \epsilon$sugerując, że $\delta(i,\sigma) \leq 2\lambda(i,\sigma)\epsilon^2$. Możemy odrzucić te ciągi o niskim prawdopodobieństwie, cierpiąc tylko na$\delta(i,\sigma)$utrata w prob. masa do$E$.

Kontynuuj robienie tego dla wszystkich możliwych złych $(i,\sigma)$i ostatecznie odrzucamy tylko co najwyżej $\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$. Wykorzystuje to fakt, że dla wszystkich$i$, $\sum_{\sigma} \lambda(i,\sigma) = 1$.

Jeśli chciałeś $E'$ mieć masę prawdopodobieństwa $1 -\gamma$, następnie $\epsilon$ musi być taki, że $\epsilon + 2n\epsilon^2 \leq \gamma$, albo to $\epsilon = O(\gamma/\sqrt{2n})$ wystarczy.

W tej chwili nie jest dla mnie jasne, czy to uzależnienie $n$można się go pozbyć; Nadal będę o tym myśleć.