Summe der Produkte von Rademacher-Zufallsvariablen

Sei unabhängige Zufallsvariablen, die Werte oder mit einer Wahrscheinlichkeit von jeweils 0,5 . Betrachten Sie die Summe . Ich möchte die Wahrscheinlichkeit nach oben begrenzen . Die beste Grenze, die ich ist wobei c eine universelle Konstante ist. Dies wird erreicht, indem die Wahrscheinlichkeit Pr (| x_1 + \ Punkte + x_n | <\ sqrt {t}) und Pr (| y_1 + \ Punkte + y_n | <\ sqrt {t}) durch Anwendung einfacher Chernoff-Grenzen niedriger begrenzt werden. Kann ich hoffen, etwas zu bekommen, das wesentlich besser ist als diese Grenze? Für den Anfang kann ich wenigstens bekommen$x_1 \ldots x_a,y_1 \ldots y_b$$+1$$-1$$S = \sum_{i,j} x_i\times y_j$$P(|S| > t)$$2e^{-\frac{ct}{\max(a,b)}}$$c$$Pr(|x_1 + \dots + x_n|<\sqrt{t})$$Pr(|y_1 + \dots + y_n|<\sqrt{t})$$e^{-c\frac{t}{\sqrt{ab}}}$ . Wenn ich subgaußsche Schwänze bekommen kann, wäre das wahrscheinlich das Beste, aber können wir das erwarten (ich denke nicht, aber ich kann mir kein Argument vorstellen)?

Die algebraische Beziehung

$$S = \sum_{i,j} x_i y_j = \sum_i x_i \sum_j y_j$$

zeigt als Produkt zweier unabhängiger Summen. Da und unabhängige Bernoulli -Variaten sind, ist eine Binomialvariable , die wurde verdoppelt und verschoben. Daher ist sein Mittelwert und seine Varianz ist . In ähnlicher Weise hat einen Mittelwert von und eine Varianz von . Lassen Sie uns sie jetzt durch Definieren standardisieren$S$$(x_i+1)/2$$(y_j+1)/2$$(1/2)$$X=\sum_{i=1}^a x_i$$(a, 1/2)$$0$$a$$Y=\sum_{j=1}^b y_j$$0$$b$

$$X_a = \frac{1}{\sqrt a} \sum_{i=1}^a x_i,$$

woher

$$S = \sqrt{ab} X_a X_b = \sqrt{ab}Z_{ab}.$$

Um ein hohes (und quantifizierbares) Grad an Genauigkeit, wie wächst großer nähert sich die Standardnormalverteilung. Lassen Sie uns daher als mal das Produkt zweier Standardnormalen approximieren.$a$$X_a$$S$$\sqrt{ab}$

Der nächste Schritt ist, das zu bemerken

$$Z_{ab} = X_aX_b = \frac{1}{2}\left(\left(\frac{X_a+X_b}{\sqrt 2}\right)^2 - \left(\frac{X_a-X_b}{\sqrt 2}\right)^2 \right) = \frac{1}{2}\left(U^2 - V^2\right).$$

ist ein Vielfaches der Differenz der Quadrate der unabhängigen Standard - Normalvariablen und . Die Verteilung von kann analytisch berechnet werden (durch Invertieren der charakteristischen Funktion ): Sein PDF ist proportional zur Bessel-Funktion der Ordnung Null, . Da diese Funktion exponentielle Schwänze hat, schließen wir sofort, dass es für großes und und festes keine bessere Annäherung an als in der Frage angegeben.$U$$V$$Z_{ab}$$K_0(|z|)/\pi$$a$$b$$t$${\Pr}_{a,b}(S \gt t)$

Es bleibt Raum für Verbesserungen, wenn eines (mindestens) von und nicht groß ist oder an Punkten im Schwanz von nahe . Direkte Berechnungen der Verteilung von zeigen eine gekrümmte Verjüngung der Schwanzwahrscheinlichkeiten an Punkten, die viel größer als , ungefähr jenseits von . Diese logarithmisch linearen Diagramme der CDF von für verschiedene Werte von (in den Titeln angegeben) und (ungefähr in den gleichen Werten wie , unterschieden durch Farbe in jedem Diagramm) zeigen, was los ist. Als Referenz dient der Graph der Begrenzung$a$$b$$S$$\pm a b$$S$$\sqrt{ab}$$\sqrt{ab\max(a,b)}$$S$$a$$b$$a$$K_0$Verteilung wird in schwarz angezeigt. (Da um symmetrisch ist , ist , so dass es ausreicht, den negativen Schwanz zu betrachten.)$S$$0$$\Pr(S \gt t) = \Pr(-S \lt -t)$

Wenn größer wird, wächst die CDF näher an der Referenzlinie.$b$

Die Charakterisierung und Quantifizierung dieser Krümmung würde eine genauere Analyse der normalen Annäherung an Binomialvariablen erfordern.

Die Qualität der Bessel-Funktionsnäherung wird in diesen vergrößerten Bereichen (in der oberen rechten Ecke jedes Diagramms) klarer. Wir sind schon ziemlich weit draußen. Obwohl die logarithmische vertikale Skala erhebliche Unterschiede verbergen kann, eindeutig durch die Zeit erreicht die Annäherung ist gut für .$a$$500$$|S| \lt a\sqrt{b}$

---

R-Code zur Berechnung der Verteilung von$S$

Die Ausführung des folgenden Vorgangs dauert einige Sekunden. (Es werden mehrere Millionen Wahrscheinlichkeiten für 36 Kombinationen von und berechnet .) Lassen Sie auf langsameren Maschinen die größeren ein oder zwei Werte von und weg und erhöhen Sie die untere Plotgrenze von auf etwa .$a$$b$ab$10^{-300}$$10^{-160}$

s <- function(a, b) {
  # Returns the distribution of S as a vector indexed by its support.
  products <- factor(as.vector(outer(seq(-a, a, by=2), seq(-b, b, by=2))))
  probs <- as.vector(outer(dbinom(0:a, a, 1/2), dbinom(0:b, b, 1/2)))
  tapply(probs, products, sum)
}

par(mfrow=c(2,3))
b.vec <- c(51, 101, 149, 201, 299, 501)
cols <- terrain.colors(length(b.vec)+1)
for (a in c(50, 100, 150, 200, 300, 500)) {
  plot(c(-sqrt(a*max(b.vec)),0), c(10^(-300), 1), type="n", log="y", 
       xlab="S/sqrt(ab)", ylab="CDF", main=paste(a))
  curve(besselK(abs(x), 0)/pi, lwd=2, add=TRUE)
  for (j in 1:length(b.vec)) {
    b <- b.vec[j]
    x <- s(a,b)
    n <- as.numeric(names(x))
    k <- n <= 0
    y <- cumsum(x[k])
    lines(n[k]/sqrt(a*b), y, col=cols[j], lwd=2)
  }
}

Kommentar: Ich habe den Titel bearbeitet, um besser zu reflektieren, welche Art von Wohnmobilen in der Frage berücksichtigt werden. Jeder kann sie erneut bearbeiten.

Motivation: Ich denke, es besteht keine Notwendigkeit, sich mit einer Obergrenze zufrieden zu geben, wenn wir die Verteilung vonableiten können . ( UPDATE : Wir können Whubers Kommentare und Antworten nicht sehen).$|S_{ab}|$

Bezeichne . Es ist leicht zu überprüfen, ob die gleiche Verteilung wie und . Die Momenterzeugungsfunktion ist$Z_k = X_iY_j,\;\; k=1,...,ab$$Z$$X$$Y$

$$M_Z(t) = E[e^{zt}]=\frac 12e^{-t}+\frac 12e^t = \cosh(t)$$

Darüber hinaus sind die paarweise unabhängig: Die Variable (Indizes können natürlich beliebig sein) unterstützt mit entsprechenden Wahrscheinlichkeiten . Seine Momenterzeugungsfunktion ist$Z$$W = Z_1+Z_2$$\{-2,0,2\}$$\{1/4,1/2,1/4\}$

$$M_{W}(t) = E[e^{(z_1+z_2)t}] = \frac 14e^{-2t}+\frac 12 +\frac 14e^{2t}=\\ =\frac 14(e^{-2t}+1)+ \frac 14(e^{2t}+1) = \frac 14 2e^{-t}\cosh(t)+\frac 14 2e^{t}\cosh(t)\\ =\cosh(t)\cdot \cosh(t) = M_{Z_1}(t)M_{Z_2}(t)$$

Ich werde versuchen zu vermuten, dass die vollständige Unabhängigkeit wie folgt gilt (ist es für die weiseren offensichtlich?): Bezeichnen Sie für diesen Teil . Dann ist nach der Kettenregel $Z_{ij}=X_iY_j$

$$P[Z_{ab},...,Z_{11}] = P[Z_{ab}\mid Z_{a,b-1},...,Z_{11}]\cdot ...\cdot P[Z_{13}\mid Z_{12},Z_{11}]\cdot P[Z_{12}\mid Z_{11}]\cdot P[Z_{11}]$$

Durch paarweise Unabhängigkeit haben wir . Betrachten Sie . und sind unabhängig von also haben wir die zweite Gleichheit durch paarweise Unabhängigkeit. Aber das impliziert das$P[Z_{12}\mid Z_{11}] = P[Z_{12}]$
$P[Z_{13},Z_{12}\mid Z_{11}]$$Z_{13}$$Z_{12}$$Z_{11}$

$$P[Z_{13}\mid Z_{12},Z_{11}] = P[Z_{13}\mid Z_{11}] = P[Z_{13}]$$

$$P[Z_{13}\mid Z_{12},Z_{11}]\cdot P[Z_{12}\mid Z_{11}]\cdot P[Z_{11}] = P[Z_{13},\,Z_{12},\,Z_{11}] = P[Z_{13}]\cdot P[Z_{12}]\cdot P[Z_{11}]$$

Usw. (glaube ich). ( UPDATE : Ich denke falsch . Unabhängigkeit gilt wahrscheinlich für jedes Triplett, aber nicht für den gesamten Haufen. Was folgt, ist nur die Ableitung der Verteilung eines einfachen zufälligen Spaziergangs und keine korrekte Antwort auf die Frage - siehe Wolfies und Whubers Antworten).

Wenn die volle Unabhängigkeit tatsächlich zutrifft, haben wir die Aufgabe, die Verteilung einer Summe der dichotomen rvs

$$S_{ab}=\sum_{k=1}^{ab}Z_k$$

das sieht aus wie ein einfacher zufälliger Spaziergang , allerdings ohne die klare Interpretation des letzteren als Sequenz.

Wenn die Unterstützung von die geraden ganzen Zahlen in einschließlich Null, während wenn die Unterstützung von die ungeraden ganzen Zahlen in ohne Null. $ab=even$$S$$[-ab,...,ab]$$ab=odd$$S$$[-ab,...,ab]$

Wir behandeln den Fall von . Bezeichne als die Anzahl der , die den Wert . Dann wird die Unterstützung der geschrieben werden . Für jeden gegebenen , wir einen eindeutigen Wert für erhalten . Darüber hinaus sind aufgrund symmetrischer Wahrscheinlichkeiten und Unabhängigkeit (oder nur Austauschbarkeit?) Alle möglichen gemeinsamen Realisierungen der Variablen wahrscheinlich. Also zählen wir und stellen fest, dass die Wahrscheinlichkeitsmassenfunktion von ist,$ab=odd$
$m$$Z$$-1$$S$$S\in \{ab-2m;m\in \mathbb Z_+\cup\{0\};m\le ab\}$$m$$S$$Z$$\{Z_1=z_1,..., Z_{ab}=z_{ab}\}$$S$

$$P(S=ab-2m)={ab \choose m}\cdot \frac 1{2^{ab}}, \qquad 0\le m\le ab$$

Definieren und ungerade Anzahl von Konstruktion und das typische Element der Unterstützung von , haben wir$s\equiv ab-2m$$S$

$$P(S=s)={ab \choose \frac{ab-s}{2}}\cdot \frac 1{2^{ab}}$$

Wechseln zu, da, wenn , die Verteilung von um Null symmetrisch ist, ohne die Wahrscheinlichkeitsmasse Null zuzuweisen, und somit die Verteilung vonwird durch "Falten" des Dichtediagramms um die vertikale Achse erhalten, wodurch die Wahrscheinlichkeiten für positive Werte im Wesentlichen verdoppelt werden.$|S|$$ab=odd$$S$$|S|$

$$P(|S|=|s|)={ab \choose \frac{ab-s}{2}}\cdot \frac 1{2^{ab-1}}$$

Dann ist die Verteilungsfunktion

$$P(|S|\le|s|)=\frac 1{2^{ab-1}}\sum_{1\le i\le s,\, i\,odd}{ab \choose \frac{ab-i}{2}}$$

Daher erhalten wir für jedes reelle , , die erforderliche Wahrscheinlichkeit $t$$1\le t<ab$

$$P(|S|> t) = 1- P(|S|\le t) = 1-\frac 1{2^{ab-1}}\sum_{1\le i\le t,\, i\,odd}{ab \choose {\frac{ab-i}{2}}}$$

Beachten Sie, dass die Angabe garantiert, dass die Summe nur bis zu den Werten läuft, die in der Unterstützung von- Wenn wir zum Beispiel , läuft immer noch bis , da es zwangsläufig ungerade ist, zusätzlich zu einer ganzen Zahl.$i=odd$$|S|$$t=10.5$$i$$9$

Keine Antwort, sondern ein Kommentar zu Alecos 'interessanter Antwort, der zu lang ist, um in ein Kommentarfeld zu passen.

Sei unabhängige Rademacher-Zufallsvariablen und sei unabhängige Rademacher-Zufallsvariable. Alecos bemerkt, dass:$(X_1, ..., X_a)$$(Y_1, ..., Y_b)$

$$S_{ab}=\sum_{k=1}^{ab}Z_k \qquad \text{where} \qquad Z_k = X_i Y_j$$

"... sieht aus wie ein einfacher zufälliger Spaziergang ". Wenn es wie ein einfacher zufälliger Spaziergang wäre, wäre die Verteilung von symmetrisch "glockenförmig unimodal" um 0.$S$

Um zu veranschaulichen, dass es sich nicht um einen einfachen zufälligen Spaziergang handelt, finden Sie hier einen kurzen Monte-Carlo-Vergleich von:

• Dreieckspunkte: Monte-Carlo-Simulation der pmf von bei und$S$$a = 5$$b = 7$
• runde Punkte: Monte-Carlo-Simulation eines einfachen zufälligen Spaziergangs mit Schritten$n = 35$

Offensichtlich ist kein einfacher zufälliger Spaziergang; Beachten Sie auch, dass S nicht auf alle geraden (oder ungeraden) ganzen Zahlen verteilt ist.$S$

Monte Carlo

Hier ist der Code (in Mathematica ), der verwendet wird, um eine einzelne Iteration der Summe zu erzeugen , wenn und :$S$$a$$b$

 SumAB[a_, b_] :=  Outer[Times, RandomChoice[{-1, 1}, a], RandomChoice[{-1, 1}, b]] 
                         // Flatten // Total 

Dann können 500.000 solcher Pfade, beispielsweise wenn und , erzeugt werden mit:$a = 5$$b = 7$

 data57 = Table[SumAB[5, 7], {500000}];

Die Unterstützungsdomäne für diese Kombination von und ist:$a$$b$

{-35, -25, -21, -15, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 15, 21, 25, 35}