Distância estatística entre moeda uniforme e polarizada

9

Deixe U ser a distribuição uniforme ao longo de n bits e deixar D ser a distribuição ao longo n bits onde os bits são independentes e cada bit é 1 com probabilidade 1/2ϵ . É verdade que a distância estatística entre D e U é Ω(ϵn), quandon1/ϵ2?

Manu
fonte
2
Sim. A distância estatística entre U e V é pelo menos PrU(xi>n/2)PrD(xi>n/2) , que é Ω(εn); veja, por exemplo, a resposta do matus aqui:cstheory.stackexchange.com/questions/14471/…
Yury
2
Obrigado. Talvez explique como obter isso do que matus escreveu em uma resposta que posso aceitar?
Manu
11
Em relação à resposta de Matus, você pode fazer melhor do que a desigualdade de Slud; veja (2.13,2.14) em arxiv.org/abs/1606.08920
Aryeh

Respostas:

7

x1,,xnUDPrU(xit)PrD(xit)tt=n/2+n

Observe que para alguma constante absoluta . Se , a distância estatística é pelo menos , e estamos prontos. Portanto, assumimos abaixo disso .PrU(xit)c1c1>0PrD(xit)c1/2c1/2PrD(xit)c1/2

Seja para as variáveis ​​aleatórias iid Bernoulli com . Nosso objetivo é provar que . Pelo teorema do valor médio, para alguns . Agora, provaremos que ; isso implica que a distância estatística desejada é pelo menos , conforme necessário.f(s)=Pr(xit)x1,,xnPr(xi=1)=1/2sf(0)f(ε)=Ω(εn)

f(0)f(ε)=εf(ξ),
ξ(0,ε)f(ξ)Ω(n)Ω(nε)

Escreva, e Observe que Portanto,

f(ξ)=kt(nk)(12ξ)k(12+ξ)nk,
f(ξ)=kt(nk)(k(12ξ)k1(12+ξ)nk+(nk)(12ξ)k(12+ξ)nk1)=kt(nk)(12ξ)k(12+ξ)nkk/2+kξ(nk)/2+(nk)ξ(1/2ξ)(1/2+ξ).
k/2+kξ(nk)/2+(nk)ξ(1/2ξ)(1/2+ξ)=(2kn)/2+nξ(1/2ξ)(1/2+ξ)2(2tn)=4n.
f(ξ)4nkt(nk)(12ξ)k(12+ξ)nk=4nf(ξ)4nf(ε)4n(c1/2).
Aqui, usamos a suposição de que . Mostramos que .f(ε)=PrD(x1++xnt)c1/2f(ξ)=Ω(n)
Yury
fonte
5

Uma prova um pouco mais elementar e um pouco mais confusa (ou pelo menos me parece).

Por conveniência, escreva , com por suposição.ε=γnγ[0,1)

Nós explicitamente limitamos a expressão : dTV(P,U)

2dTV(P,U)=x{0,1}n|(12+γn)|x|(12γn)n|x|12n|=12nk=0n(nk)|(1+2γn)k(12γn)nk1|12nk=n2+nn2+2n(nk)|(1+2γn)k(12γn)nk1|Cnk=n2+nn2+2n|(1+2γn)k(12γn)nk1|
onde é uma constante absoluta. Abaixamos cada limite de soma separadamente: fixando e escrevendo , para que cada soma seja menor delimitada por uma quantidade que converja (quando ) paraC>0k=kn2[n,2n]
(1+2γn)k(12γn)nk=(14γ2n)n/2(1+2γn12γn)(14γ2n)n/2(1+2γn12γn)nne4γ2γ2
ne4γ2γ21>4γ2γ2>2γ ; implicando que cada um é . Resumindo, isso gera conforme reivindicado.Ω(γ)
2dTV(P,U)Cnk=n2+nn2+2nΩ(γ)=Ω(γ)=Ω(εn)
Clemente C.
fonte
(Usando Hellinger como um proxy devido às suas propriedades agradáveis wrt distribuições de produtos é tentador, e seria muito mais rápido, mas não haveria uma perda de um factor quadrático na extremidade inferior ligada.)
Clement c
11
Agradável! Eu gosto da abordagem elementar. Deveríamos ser capazes de torná-lo não assintótico também em .... uma maneira é usar e use a boa desigualdade . Um pouco mais bagunçado. n(1+z1z)n(1+2z)n1+weww2/2
usul