Eventos de alta probabilidade sem coordenadas de baixa probabilidade

9

XΣnΣH(X)(nδ)log|Σ|δESupp(X)XPr[XE]1εε

Dizemos que um par é uma coordenada de baixa probabilidade de se . Dizemos que uma string contém uma coordenada de baixa probabilidade de se for uma coordenada de baixa probabilidade de para alguns .(i,σ)EPr[XE|Xi=σ]εxΣn E(i,xi)Ei

Em geral, algumas cordas em pode conter baixas coordenadas de probabilidade de . A questão é: podemos sempre encontrar um evento de alta probabilidade modo que nenhuma string em contenha uma coordenada de probabilidade baixa de (e não de ).EEEEEEE

Obrigado!

Ou Meir
fonte

Respostas:

4

Aqui está um exemplo que complementa a resposta de Harry Yuen. Para um contra-exemplo, basta definir apropriado e mostrar que qualquer subconjunto grande deve ter uma coordenada de baixa probabilidade de - uma coordenada de baixa probabilidade de é necessariamente uma coordenada de baixa probabilidade -ordenado de .X,EEEEEE

Além disso, ignorarei a condição sobre entropia - anexar variáveis ​​aleatórias uniformemente distribuídas e independentes a (e levar a ) aumentarápara quase sem afetar a existência de um (ainda não pensei nisso com cuidado).NXEE×ΣNH(X)/(n+N)log|Σ|1E

Aqui está o exemplo. Deixe ser um elemento aleatório de tal que cada vector com peso de Hamming (isto é, vectores do formulário ) têm probabilidade e o o vetor all-ones tem probabilidade . Seja o conjunto de vetores com peso de Hamming .X{0,1}n100100(1ϵ)/n11ϵE1

Considere um subconjunto . Se não estiver vazio, ele conterá um vetor do peso de Hamming , digamos sem perda de generalidade. Mas , que é menor que se for cerca de .EEE11000Pr[XE|Xi=1]=(1ϵ)/n(1ϵ)/n+ϵϵn2/ϵ2

Colin McQuillan
fonte
6

Como compara a ? Se puder ser , acho que podemos realizar o que você deseja. Deixe . Note-se que é dado massa de probabilidade sob . Vamos denotar a massa de probabilidade atribuída a cordas em tal que o th coordenar tem símbolo .ϵnϵO(1/n)B=Supp(X)EBϵXλ(i,σ)ϵBiσ

Suponha foram uma probabilidade baixa de coordenadas para algumas cordas em . Let denota a massa de probabilidade atribuída a essas strings. Então, por definição, , implicando que . Podemos descartar essas seqüências de baixa probabilidade enquanto apenas sofremos uma perda no prob. massa para .(i,σ)Eδ(i,σ)δ(i,σ)δ(i,σ)+λ(i,σ)ϵϵδ(i,σ)2λ(i,σ)ϵ2δ(i,σ)E

Continue fazendo isso para todo o mal possível e, no final, apenas descartamos no máximo . Isso usa o fato de que, para todos os , .(i,σ)i,σδ(i,σ)iσ2λ(i,σ)ϵ22iϵ2=2nϵ2iσλ(i,σ)=1

Se você deseja que tenha massa de probabilidade , então precisa ser tal que ou é suficiente.E1γϵϵ+2nϵ2γϵ=O(γ/2n)

Não está claro para mim no momento se essa dependência de pode ser eliminada; Vou continuar pensando sobre isso.n

Henry Yuen
fonte
Oh, eu só percebi que você está procurando uma exigência mais forte - ou seja, que não tem nenhum coordenadas de baixa probabilidade em relação a , não . Voltarei a isso mais tarde hoje. EEE
Henry Yuen
Obrigado! Estou procurando um epsilon que seja constante, mas possa ser arbitrariamente pequeno.
Ou Meir