Eventos de alta probabilidad sin coordenadas de baja probabilidad

Supongamos que $X$ es una variable aleatoria que toma valores en $\Sigma^n$ (para un alfabeto grande $\Sigma$ ), que tiene una entropía muy alta, por ejemplo, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$para una constante arbitrariamente pequeña $\delta$ . Sea $E \subseteq \rm{Supp}(X)$ un evento en apoyo de $X$ tal que $\Pr[X \in E] \ge 1 - \varepsilon$ , donde $\varepsilon$ es una constante arbitrariamente pequeña.

Decimos que un par $(i,\sigma)$ es una coordenada de baja probabilidad de $E$ si $\Pr[X \in E | X_i = \sigma] \le \varepsilon$ . Decimos que una cadena $x \in \Sigma^n$ contiene una coordenada de baja probabilidad de $E$ si $(i, x_i)$ es una coordenada de baja probabilidad de $E$ para alguna $i$ .

En general, algunas cadenas en $E$ pueden contener coordenadas baja probabilidad de $E$ . La pregunta es si siempre podemos encontrar un evento de alta probabilidad $E' \subseteq E$ tal que ninguna cadena en $E'$ contenga una coordenada de baja probabilidad de $E'$ (y no de $E$ ).

¡Gracias!

Aquí hay un ejemplo que complementa la respuesta de Harry Yuen. Para un contraejemplo, es suficiente definir y mostrar que cualquier subconjunto grande debe tener una coordenada de baja probabilidad de - una coordenada de baja probabilidad de es necesariamente una co de baja probabilidad -ordenada de .E ′ ⊆ E E E E $X,E$$E'\subseteq E$$E$$E$$E'$

Además, ignoraré la condición sobre la entropía: agregar variables aleatorias distribuidas uniformemente independientes a (y tomar a ) aumentaráa casi sin afectar si existe tal (no lo he pensado cuidadosamente).X E E × Σ N H ( X ) / ( n + N ) log | Σ | 1 E $N$$X$$E$$E\times \Sigma^N$$H(X)/(n+N)\log|\Sigma|$$1$$E'$

Aquí está el ejemplo. Sea un elemento aleatorio de tal que cada vector con peso de Hamming (es decir, vectores de la forma ) tenga probabilidad el el vector todo en uno tiene probabilidad . Sea el conjunto de vectores con peso de Hamming .{ 0 , 1 } n 1 0 … 010 … 0 ( 1 - ϵ ) / n 1 … 1 ϵ E $X$$\{0,1\}^n$$1$$0\dots 010\dots 0$$(1-\epsilon)/n$$1\dots 1$$\epsilon$$E$$1$

Considere un subconjunto . Si no está vacío, contiene un vector de peso de Hamming , digamos sin pérdida de generalidad. Pero , que es menor que si es aproximadamente .E ′ 1 100 … 0 Pr [ X ∈ E ′ | X i = 1 ] = ( 1 - ϵ ) /$E'\subseteq E$$E'$$1$$100\dots 0$ ϵn2/ϵ$\Pr[X \in E'|X_i=1]=\frac{(1-\epsilon)/n}{(1-\epsilon)/n + \epsilon}$$\epsilon$$n$$2/\epsilon^2$

¿Cómo se compara con ? Si puede ser , entonces creo que podemos lograr lo que desea. Dejar que . Tenga en cuenta que se da masa de probabilidad bajo . Deje que denote la masa de probabilidad asignada a las cadenas en modo que la coordenada tiene el símbolo .n ϵ O ( 1 / $\epsilon$$n$$\epsilon$B=Supp(X)-EBϵXλ(i,σ)ϵBi$O(1/\sqrt{n})$$B = \mbox{Supp}(X) - E$$B$$\epsilon$$X$$\lambda(i,\sigma)\epsilon$$B$$i$$\sigma$

Supongamos que eran coordinar una probabilidad baja para algunas cadenas en . Deje que denote la masa de probabilidad asignada a esas cadenas. Entonces, por definición, , lo que implica que . Podemos descartar estas cadenas de baja probabilidad mientras solo sufrimos una pérdida en el problema. masa a .E δ ( i , σ ) δ ( i , σ $(i,\sigma)$$E$$\delta(i,\sigma)$δ(i,σ)≤2λ(i,σ)ϵ2δ(i,σ)$\frac{\delta(i,\sigma)}{\delta(i,\sigma) + \lambda(i,\sigma)\epsilon} \leq \epsilon$$\delta(i,\sigma) \leq 2\lambda(i,\sigma)\epsilon^2$$\delta(i,\sigma)$$E$

Continúe haciendo esto para todas las posibles malas , y al final solo descartamos como máximo . Esto utiliza el hecho de que para todo , .∑ i , σ δ ( i , σ ) ≤ ∑ i ∑ σ 2 λ ( i , σ ) ϵ 2 ≤ 2 ∑ i ϵ 2 = 2 n ϵ 2 i ∑ σ λ ( i , σ ) = $(i,\sigma)$$\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$$i$$\sum_{\sigma} \lambda(i,\sigma) = 1$

Si desea que tenga una masa de probabilidad , entonces debe ser tal que , o que suficiente. 1 - γ ϵ ϵ + 2 n ϵ 2 ≤ γ ϵ = O ( γ / $E'$$1 -\gamma$$\epsilon$$\epsilon + 2n\epsilon^2 \leq \gamma$$\epsilon = O(\gamma/\sqrt{2n})$

Por el momento no me queda claro si esta dependencia de puede eliminarse; Seguiré pensando en eso.$n$