Suma de productos de variables aleatorias Rademacher

Supongamos que son variables aleatorias independientes que toman valores o con probabilidad 0.5 cada uno. Considere la suma . Deseo el límite superior de la probabilidad . El mejor límite que tengo en este momento es donde c es una constante universal. Esto se logra limitando la probabilidad Pr (| x_1 + \ dots + x_n | <\ sqrt {t}) y Pr (| y_1 + \ dots + y_n | <\ sqrt {t}) mediante la aplicación de límites simples de Chernoff. ¿Puedo esperar obtener algo que sea significativamente mejor que este límite? Para empezar, ¿puedo al menos obtener$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}}}$ . Si puedo obtener colas subgaussianas, eso probablemente sería lo mejor, pero ¿podemos esperar eso (no lo creo pero no puedo pensar en una discusión)?

La relacion algebraica

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

exhibe como el producto de dos sumas independientes. Como y son variantes independientes de Bernoulli , es una variable binomial que ha sido duplicado y desplazado. Por lo tanto, su media es y su varianza es . Del mismo modo, tiene una media de y una varianza de . Estandaricemos ahora mismo definiendo$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,$$

De dónde

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

Para un alto (y cuantificable) grado de precisión, como aumenta de tamaño aproxima a la distribución normal estándar. Por lo tanto, aproximaremos como veces el producto de dos normales estándar.$a$$X_a$$S$$\sqrt{ab}$

El siguiente paso es notar que

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

es un múltiplo de la diferencia de los cuadrados de las variables normales estándar independientes y . La distribución de puede calcularse analíticamente ( invirtiendo la función característica ): su pdf es proporcional a la función de Bessel de orden cero, . Debido a que esta función tiene colas exponenciales, llegamos a la conclusión inmediata de que para y grandes y fija , no hay mejor aproximación a que la dada en la pregunta.$U$$V$$Z_{ab}$$K_0(|z|)/\pi$$a$$b$$t$${\Pr}_{a,b}(S \gt t)$

Queda algo de mejora cuando uno (al menos) de y no es grande o en puntos en la cola de cerca de . Los cálculos directos de la distribución de muestran una disminución curva de las probabilidades de cola en puntos mucho más grandes que , aproximadamente más allá de . Estas gráficas log-lineales del CDF de para varios valores de (dados en los títulos) (que varían aproximadamente sobre los mismos valores que , distinguidos por el color en cada gráfica) muestran lo que está sucediendo. Como referencia, la gráfica de la limitación$a$$b$$S$$\pm a b$$S$$\sqrt{ab}$$\sqrt{ab\max(a,b)}$$S$$a$$b$$a$$K_0$La distribución se muestra en negro. (Debido a que es simétrica alrededor de , , entonces es suficiente mirar la cola negativa).$S$$0$$\Pr(S \gt t) = \Pr(-S \lt -t)$

A medida que crece, el CDF se acerca a la línea de referencia.$b$

Caracterizar y cuantificar esta curvatura requeriría un análisis más fino de la aproximación normal a las variantes binomiales.

La calidad de la aproximación de la función de Bessel se vuelve más clara en estas porciones ampliadas (de la esquina superior derecha de cada gráfico). Ya estamos bastante lejos en las colas. Aunque la escala vertical logarítmica puede ocultar diferencias sustanciales, claramente para cuando ha alcanzado la aproximación es buena para .$a$$500$$|S| \lt a\sqrt{b}$

---

Código R para calcular la distribución de$S$

Lo siguiente tardará unos segundos en ejecutarse. (Se calcula varios millones de probabilidades para 36 combinaciones de y .) En las máquinas más lentas, omitir los más grandes uno o dos valores de y y aumentar el límite de trazado inferior de de alrededor de .$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)
  }
}

Comentario: edité el título en un intento de reflejar mejor qué tipo de vehículos se consideran en la pregunta. Cualquiera puede reeditar libremente.

Motivación: supongo que no hay necesidad de conformarse con un límite superior, si podemos derivar la distribución de. ( ACTUALIZACIÓN : No podemos ver los comentarios y la respuesta de Whuber).$|S_{ab}|$

Denotan . Es fácil verificar que 's tienen la misma distribución que la ' s y el 's. La función generadora de momento es$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)$$

Además, las son, para empezar, independientes por pares: la variable (los índices pueden ser cualquiera, por supuesto), tiene soporte con las probabilidades correspondientes . Su función generadora de momento es$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)$$

Intentaré sospechar que la independencia total es válida, como sigue (¿es obvio para los más sabios?): Para esta parte, denote . Luego, por la regla de la cadena $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}]$$

Por independencia en pares, tenemos . Considere . y son condicionales independientes de por lo que tenemos la segunda igualdad por independencia en pares. Pero esto implica que$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}]$$

Etc (creo). ( ACTUALIZACIÓN : Pienso mal . La independencia probablemente sea válida para cualquier triplete, pero no para todo el grupo. Entonces, lo que sigue es solo la derivación de la distribución de una caminata aleatoria simple, y no una respuesta correcta a la pregunta: vea Wolfies y Las respuestas de Whuber).

Si la independencia total es válida, tenemos la tarea de derivar la distribución de una suma de iid dicotómicos rv's

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

que parece una simple caminata aleatoria , aunque sin la clara interpretación de este último como una secuencia.

Si el soporte de serán los enteros pares en incluyendo cero, mientras que si el soporte de serán los enteros impares en , sin cero. $ab=even$$S$$[-ab,...,ab]$$ab=odd$$S$$[-ab,...,ab]$

Tratamos el caso de . Denote como el número de toman el valor . Entonces el soporte de se puede escribir . Para cualquier dado , obtenemos un valor único para . Además, debido a las probabilidades simétricas y la independencia (¿o solo a la intercambiabilidad?), Todas las posibles realizaciones conjuntas de las variables son equiprobables. Entonces contamos y encontramos que la función de masa de probabilidad de es,$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$$

Definiendo , y número impar por construcción, y el elemento típico del soporte de , tenemos$s\equiv ab-2m$$S$

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

Mudarse a, dado que si , la distribución de es simétrica alrededor de cero sin asignar la masa de probabilidad a cero, por lo que la distribución dese obtiene "doblando" el gráfico de densidad alrededor del eje vertical, esencialmente duplicando las probabilidades de valores positivos,$|S|$$ab=odd$$S$$|S|$

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

Entonces la función de distribución es

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

Por lo tanto, para cualquier real , , obtenemos la probabilidad requerida $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}}}$$

Tenga en cuenta que la indicación garantiza que la suma se ejecutará solo hasta valores incluidos en el soporte de- por ejemplo, si establecemos , todavía a correr hasta , ya que está limitado a ser impar, además de ser un número entero.$i=odd$$|S|$$t=10.5$$i$$9$

No es una respuesta, sino un comentario sobre la interesante respuesta de Alecos que es demasiado largo para caber en un cuadro de comentarios.

Deje que sean variables aleatorias independientes de Rademacher, y deje que sean variables aleatorias independientes de Rademacher. Alecos señala que:$(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$$

"... parece una simple caminata aleatoria ". Si fuera como una simple caminata aleatoria, entonces la distribución de sería simétrica 'unimodal en forma de campana' alrededor de 0.$S$

Para ilustrar que no se trata de una simple caminata aleatoria, aquí hay una comparación rápida de Monte Carlo de:

• puntos del triángulo: simulación Monte Carlo de la pmf de dado y$S$$a = 5$$b = 7$
• puntos redondos: simulación de Monte Carlo de una caminata aleatoria simple con pasos$n = 35$

Claramente, no es una simple caminata aleatoria; También tenga en cuenta que S no se distribuye en todos los enteros pares (o impares).$S$

Monte Carlo

Aquí está el código (en Mathematica ) utilizado para generar una única iteración de la suma , dados y :$S$$a$$b$

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

Entonces, 500.000 tales caminos, dicen cuando y , se pueden generar con:$a = 5$$b = 7$

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

El dominio de soporte para esta combinación de y es:$a$$b$

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