Chernoff-Ungleichung für Zufallsvariable mit 3 Ergebnissen

9

Angenommen, wir haben eine Zufallsvariable, die nicht numerische Werte a, b, c annimmt und quantifizieren möchte, wie die empirische Verteilung von Stichproben dieser Variablen von der tatsächlichen Verteilung abweicht. In diesem Fall gilt die folgende Ungleichung (von Cover & Thomas ).n

Satz 12.4.1 (Satz von Sanov): Sei iid . Sei eine Menge von Wahrscheinlichkeitsverteilungen. Dann ist wobei die Verteilung in E ist, die in der relativen Entropie Q am nächsten kommt .X1,X2,,XnQ(x)
EP

Qn(E)=Qn(EPn)(n+1)|X|2nD(P||Q),
E Q.
P=argminPED(P||Q),
EQ

Diese Ungleichung ist für kleine n ziemlich locker n. Für binäre Ergebnisse ist |X|=2 und die Chernoff-Hoeffding- Bindung viel enger.

Gibt es eine ähnlich enge Grenze für |X|=3 ?

Jaroslaw Bulatow
quelle
Ich glaube, Sie können | X | ändern bis | X | -1, da der "letzte Typ" in den Methoden und Typen angegeben wird, sobald Sie den Rest kennen.
Thomas Ahle

Antworten:

6

Sie können ziemlich gute Grenzen erhalten, indem Sie die Zufallsvariable berücksichtigen, die 1 ist, wenn und ansonsten Null ist (für , das sich über Versuche erstreckt, und , das sich über Kategorien erstreckt). Für jedes feste die unabhängig und daher kann unter Verwendung von Chernoff-Grenzen analysiert werden. Dann mache eine Union, die über gebunden ist . X i = j 1 i n 1 j 3 j Y i ji Y i j jYijXi=j1in1j3jYijiYijj

Wenn das oben Genannte nicht ausreicht, schlage ich vor, dass Sie sich das Modell der Kugeln und Behälter ansehen, z. B. in Upfals und Mitzenmachers Lehrbuch. Dieses Modell ist das gleiche wie Ihres, außer dass einige Ihrer Behälter mit größerer Wahrscheinlichkeit als andere Bälle in ihnen landen, oder? Es gibt einige ausgefeiltere Techniken, die Poisson-Näherungen in diesem Modell beinhalten und wahrscheinlich mit ungleichmäßigen Bin-Wahrscheinlichkeiten auf Ihre Einstellung erweiterbar sind.

Warren Schudy
quelle
3

Es gibt nichts an Chernoff Hoeffding-Grenzen, was für boolesche Variablen spezifisch ist. Wenn iid reelle Zufallsvariablen mit , können Sie eine Chernoff-Grenze anwenden. Eine gute Referenz ist "Konzentration der Maßnahmen zur Analyse randomisierter Algorithmen" ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&rep=rep1&type=pdf ). 0 X i1X1,,Xn0Xi1

Aaron Roth
quelle
Ich interessiere mich eher für kategoriale als für realwertige Variablen, fügte eine Klarstellung hinzu
Jaroslaw Bulatow