Suma produktów zmiennych losowych Rademacher

Niech będą niezależnymi zmiennymi losowymi przyjmującymi wartości lub -1 z prawdopodobieństwem 0,5 każda. Rozważ sumę S = \ sum_ {i, j} x_i \ razy y_j . Chciałbym przekroczyć górną granicę prawdopodobieństwa P (| S |> t) . Najlepsza granica, jaką mam teraz, to 2e ^ {- \ frac {ct} {\ max (a, b)}}, gdzie c jest stałą uniwersalną. Osiąga się to poprzez niższe ograniczenie prawdopodobieństwa Pr (| x_1 + \ dots + x_n | <\ sqrt {t}) i Pr (| y_1 + \ dots + y_n | <\ sqrt {t}) poprzez zastosowanie prostych granic Chernoffa. Czy mogę mieć nadzieję, że dostanę coś znacznie lepszego niż to ograniczenie? Na początek mogę przynajmniej dostać$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}}}$ . Jeśli uda mi się uzyskać ogony sub-gaussowskie, które prawdopodobnie byłyby najlepsze, ale czy możemy się tego spodziewać (nie sądzę, ale nie mogę wymyślić kłótni)?

Relacja algebraiczna

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

wykazuje jako iloczyn dwóch niezależnych sum. Ponieważ i są niezależnymi zmiennymi Bernoulliego , jest zmienną dwumianową , która został podwojony i przesunięty. Dlatego jego średnia wynosi , a jego wariancja jest . Podobnie ma średnią i wariancję . Standaryzujmy je teraz, definiując$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,$$

skąd

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

Do wysokiego (i policzalne) stopień dokładności, jak rośnie duża zbliża się do rozkładu normalnego. Przybliżmy zatem jako razy iloczyn dwóch standardowych normalnych.$a$$X_a$$S$$\sqrt{ab}$

Następnym krokiem jest zauważenie tego

$$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).$$

jest wielokrotnością różnicy kwadratów niezależnych zmiennych standardowych Zwykłe i . Rozkład można obliczyć analitycznie ( odwracając funkcję charakterystyczną ): jego pdf jest proporcjonalny do funkcji Bessela rzędu zero, . Ponieważ ta funkcja jest wykładniczy ogony natychmiast stwierdzić, że w przypadku dużych i i stałej , nie ma lepsze przybliżenie niż w pytaniu.$U$$V$$Z_{ab}$$K_0(|z|)/\pi$$a$$b$$t$${\Pr}_{a,b}(S \gt t)$

Pozostaje potrzeba tak, gdy jedna (co najmniej) z i jest niewielka lub w punktach ogona blisko . Bezpośrednie obliczenia rozkładu pokazują zakrzywione zwężenie prawdopodobieństwa ogona w punktach znacznie większych niż , mniej więcej powyżej . Te logarytmiczno-liniowe wykresy CDF dla dla różnych wartości (podanych w tytułach) (w przybliżeniu powyżej tych samych wartości co , rozróżnianych kolorem na każdym wykresie) pokazują, co się dzieje. Dla porównania wykres ograniczenia$a$$b$$S$$\pm a b$$S$$\sqrt{ab}$$\sqrt{ab\max(a,b)}$$S$$a$$b$$a$$K_0$dystrybucja jest pokazana na czarno. (Ponieważ jest symetryczny wokół , , więc wystarczy spojrzeć na ujemny ogon.)$S$$0$$\Pr(S \gt t) = \Pr(-S \lt -t)$

Gdy rośnie, CDF zbliża się do linii odniesienia.$b$

Charakterystyka i kwantyfikacja tej krzywizny wymagałaby dokładniejszej analizy przybliżenia normalnego do zmiennych dwumianowych.

Jakość przybliżenia funkcji Bessela staje się wyraźniejsza w tych powiększonych częściach (w prawym górnym rogu każdego wykresu). Jesteśmy już dość daleko w tyle. Chociaż logarytmiczna skala pionowa może ukryć znaczne różnice, wyraźnie do czasu, gdy osiągnie przybliżenie jest dobre dla .$a$$500$$|S| \lt a\sqrt{b}$

---

Kod R do obliczenia rozkładu$S$

Wykonanie poniższych czynności potrwa kilka sekund. (Oblicza kilka milionów prawdopodobieństwa dla 36 kombinacji i ). Na dłuższych maszyn pominąć większy lub dwie wartości i i wzrost dolnej granicy kreślenia od około .$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)
  }
}

Komentarz: Zredagowałem tytuł, aby lepiej odzwierciedlić, jakie rv są rozważane w pytaniu. Każdy może ponownie edytować.

Motywacja: Myślę, że nie ma potrzeby zadowolenia się górną granicą, jeśli możemy wyprowadzić rozkład. ( AKTUALIZACJA : Nie możemy zobaczyć komentarzy i odpowiedzi Whubera).$|S_{ab}|$

Oznaczają . Jest to łatwe do sprawdzenia, że „y mają ten sam rozkład co ” S i „S. Funkcja generowania momentu to$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)$$

Co więcej, są na początek niezależne parami: Zmienna (wskaźniki mogą być oczywiście dowolne), ma wsparcie z odpowiednimi prawdopodobieństwami . Jego funkcją generowania momentu jest$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)$$

Spróbuję podejrzewać, że zachowuje się pełna niezależność w następujący sposób (czy jest to oczywiste dla mądrzejszych?): W tej części . Następnie według reguły łańcucha $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}]$$

Dzięki niezależności parami mamy . Rozważmy . i są niezależne od więc mamy druga równość przez niezależność par. Ale to implikuje$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}]$$

Itp (myślę). ( AKTUALIZACJA : Wydaje mi się, że jest źle . Niepodległość prawdopodobnie dotyczy każdej trypletu, ale nie całej grupy. A więc po prostu wyprowadzenie rozkładu zwykłego losowego marszu, a nie poprawna odpowiedź na pytanie - patrz Wolfies i Odpowiedzi Whubera).

Jeśli rzeczywiście zachodzi pełna niezależność, mamy za zadanie wyprowadzić rozkład sumy Sid dychotomicznego rv iid d_hotomous rv

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

który wygląda jak zwykły losowy spacer , choć bez jasnej interpretacji tego ostatniego jako sekwencji.

Jeśli wsparcie będzie parzystymi liczbami całkowitymi w włączając zero, podczas gdy jeśli wsparcie będzie nieparzystymi liczbami całkowitymi w , bez zera. $ab=even$$S$$[-ab,...,ab]$$ab=odd$$S$$[-ab,...,ab]$

Traktujemy przypadek . Oznaczmy jako liczbę przyjmującą wartość . Następnie można napisać wsparcie dla . Dla danego , otrzymujemy unikalną wartość . Ponadto, ze względu na symetryczne prawdopodobieństw i niezależności (lub po prostu zamienności?), Wszystkich możliwych wspólnych realizacje -zmienne są jednakowo prawdopodobne. Liczymy więc i stwierdzamy, że funkcja masy prawdopodobieństwa jest,$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$$

Definiując i liczbę nieparzystą według konstrukcji oraz typowy element podparcia , mamy$s\equiv ab-2m$$S$

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

Przeprowadzka do, ponieważ jeśli , rozkład jest symetryczny wokół zera bez przydzielania masy prawdopodobieństwa do zera, a zatem rozkładuzyskuje się przez „złożenie” wykresu gęstości wokół osi pionowej, zasadniczo podwajając prawdopodobieństwo dla wartości dodatnich,$|S|$$ab=odd$$S$$|S|$

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

Zatem funkcja dystrybucji to

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

Dlatego dla dowolnego rzeczywistego , otrzymujemy wymagane prawdopodobieństwo $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}}}$$

Zauważ, że wskazanie gwarantuje, że suma będzie działać tylko do wartości zawartych w obsłudze- Na przykład, jeśli zestaw , wciąż będą działać do , ponieważ jest ona ograniczona być dziwne, na górze jest liczbą całkowitą.$i=odd$$|S|$$t=10.5$$i$$9$

Nie odpowiedź, ale komentarz do interesującej odpowiedzi Alecos, która jest zbyt długa, aby zmieściła się w polu komentarza.

Niech będą niezależnymi zmiennymi losowymi Rademacher i niech będą niezależnymi zmiennymi losowymi Rademacher. Alecos zauważa, że:$(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$$

„… Wygląda jak zwykły losowy spacer ”. Gdyby to był zwykły losowy spacer, wówczas rozkład byłby symetryczny „unimodalny” w kształcie dzwonu wokół 0.$S$

Aby zilustrować, że to nie proste błądzenia losowego, tutaj jest szybkie porównanie Monte Carlo:

• Kropki trójkąt: symulacji Monte Carlo PMF z danym , a$S$$a = 5$$b = 7$
• okrągłe kropki: symulacja Monte Carlo prostego losowego marszu z kroków$n = 35$

Oczywiście nie jest zwykłym przypadkowym spacerem; zauważ także, że S nie jest rozłożone na wszystkie parzyste (lub nieparzyste) liczby całkowite.$S$

Monte Carlo

Oto kod (w Mathematica ) użyty do wygenerowania pojedynczej iteracji sumy , biorąc uwagę i :$S$$a$$b$

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

Następnie 500000 takie ścieżki, np gdy , a , można wytworzyć z:$a = 5$$b = 7$

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

Dziedziną wsparcia dla tej kombinacji i jest:$a$$b$

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