Statistischer Abstand zwischen einheitlicher und voreingenommener Münze

9

Lassen die gleichmäßige Verteilung über seine Bits, und lassen die Verteilung über seine Bits , wobei die Bits sind unabhängig , und jedes Bit ist mit einer Wahrscheinlichkeit . Trifft es zu, dass der statistische Abstand zwischen und ist , wenn ?UnDn11/2ϵDUΩ(ϵn)n1/ϵ2

Manu
quelle
2
Ja. Der statistische Abstand zwischen und beträgt mindestens , was ; siehe zB die Antwort von matus hier: cstheory.stackexchange.com/questions/14471/…UVPrU(xi>n/2)PrD(xi>n/2)Ω(εn)
Yury
2
Vielen Dank. Erklären Sie vielleicht, wie Sie dies aus dem erhalten, was Matus in einer Antwort geschrieben hat, die ich akzeptieren kann.
Manu
1
In Bezug auf Matus 'Antwort können Sie es besser machen als Sluds Ungleichung. siehe (2.13,2.14) in arxiv.org/abs/1606.08920
Aryeh

Antworten:

7

Bezeichne die zufälligen Bits mit . Per Definition beträgt der statistische Abstand zwischen und für jedes mindestens . Wir wählen .x1,,xnUDPrU(xit)PrD(xit)tt=n/2+n

Beachten Sie, dass für eine absolute Konstante . Wenn , beträgt der statistische Abstand mindestens , und wir sind fertig. Wir nehmen also an, dass .PrU(xit)c1c1>0PrD(xit)c1/2c1/2PrD(xit)c1/2

Sei für iid Bernoulli-Zufallsvariablen mit . Unser Ziel ist es zu beweisen, dass . Nach dem Mittelwertsatz ist für einige . Nun werden wir beweisen, dass ; Dies bedeutet, dass der gewünschte statistische Abstand je nach Bedarf mindestens beträgt .f(s)=Pr(xit)x1,,xnPr(xi=1)=1/2sf(0)f(ε)=Ω(εn)

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

Schreiben Sie, und Beachten Sie, dass Somit,

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).
Hier haben wir die Annahme verwendet, dass . Wir haben gezeigt, dass .f(ε)=PrD(x1++xnt)c1/2f(ξ)=Ω(n)
Yury
quelle
5

Ein etwas elementarerer und etwas chaotischerer Beweis (oder zumindest fühlt es sich für mich so an).

Schreiben Sie der , wobei angenommen wird.ε=γnγ[0,1)

Wir setzen den Ausdruck von explizit nach unten : 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|
wobei eine absolute Konstante ist. Wir unterbinden jeden Summanden separat unter: Fixieren von und Schreiben von , sodass jeder Summand durch eine konvergierende Größe niedriger begrenzt ist (wenn ) bisC>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γ ; was bedeutet, dass jedes . Zusammenfassend ergibt dies wie behauptet.Ω(γ)
2dTV(P,U)Cnk=n2+nn2+2nΩ(γ)=Ω(γ)=Ω(εn)
Clement C.
quelle
(Die Verwendung von Hellinger als Proxy aufgrund seiner guten Eigenschaften für Produktverteilungen ist verlockend und würde viel schneller sein, aber es würde einen Verlust durch einen quadratischen Faktor in der unteren Endgrenze geben.)
Clement C.
1
Nett! Ich mag den elementaren Ansatz. Wir sollten in der Lage sein, es auch in nicht asymptotisch zu machen. Eine Möglichkeit besteht darin, , dann benutze die schöne Ungleichung . Ein bisschen chaotischer. n(1+z1z)n(1+2z)n1+weww2/2
Usul