La expectativa de $b^T \operatorname{sign}(Ab)$

Question

Estoy tratando de calcular la expectativa de:
$$b^T \operatorname{sign}(Ab)$$ Donde $b$ $n\times1$ vector de variables aleatorias de Bernoulli independientes:
$$P(b_i = 1) = 0.5,\quad P(b_i = -1) = 0.5$$ y $A$ es un fijo $n\times n$ matriz.
Creo que esto podría ser difícil de calcular, ya que es necesario para encontrar las probabilidades de:
$$v = \operatorname{sign}(Ab)\quad P(v_i > 0).$$

Y $v$ $b$ están correlacionadas...
Sin embargo, la informática, la $v_i$ corresponde al cálculo de la suma:
$$v_i = \sum_j A_{ij} b_i.$$

Creo que debe haber algún método para encontrar todos los valores de $v_i$ que son interesantes (cerca de cero), ya que se suma los valores de $A$. De esta manera es posible encontrar la densidad de probabilidad de $sign(v)$.
Sin embargo, también habrá que tomar la correlación en cuenta.

Si no es posible o sencillo para calcular, ¿alguien sabe cómo enlazado a la expectativa? O, posiblemente, sólo os muestra el $b$'s para calcular de forma empírica a la expectativa, sin embargo, me gustaría saber si podemos hacer alguna garantía de que el empírica expectativa está cerca de la expectativa real.

Answer 1

Una forma cerrada de la solución parece trivial; de hecho, una solución exacta para arbitrario $A$ parece ser #P duro. Pero fijo $A$ puede aproximar la expectativa con precisión arbitraria, utilizando la ley de los grandes números. Además, el teorema del límite central (CLT) da una tasa de convergencia. Vamos

$$f(b) = b^T \text{sign}(Ab) = b^T v$$

Informalmente, el CLT afirma que para que un gran $m$,

$$ \mathbb{E}[f(b)] \sim \frac{1}{m} \sum_{i=1}^m f(b^{(i)}) + \frac{\sigma \epsilon}{\sqrt{m}} $$

donde $\sim$ denota la convergencia en distribución como $m \rightarrow \infty$, $b^{(i)}$ $i=1,\ldots,m$ son una secuencia de iid aleatoria de Bernoulli vectores, $\sigma^2 = \text{Var}[f(b)]$ es una constante, y $\epsilon$ es una variable aleatoria normal estándar. Ten en cuenta que $\sigma^2$ depende de las entradas de $A$ y podría ser muy grande. También, puesto que esto es sólo un asintótica resultado, arbitrariamente grandes errores son todavía posibles para finitos $m$ y su probabilidad no es garantizado a seguir la distribución asintótica $\sigma \epsilon / \sqrt{m}$. Probablemente no es una buena idea confiar en este método, sin una consideración cuidadosa de estos temas.

Aquí están algunas observaciones detalladas sobre casos especiales y generales de la dureza:

1. Si $A$ es la matriz identidad tenemos $f(b) = \sum_{i=1}^n b_i^2 = n$. Esto debería ser útil para aproximar la solución al $A$ es una pequeña perturbación de la identidad.
2. Ya que sólo necesita la expectativa de que probablemente debería explotar la linealidad de la expectativa: \begin{align} E[b^T v] &= \sum_{i=1}^n E[b_i v_i] \\ &= \sum_{i=1}^n E[b_i E[v_i|b_i]] \\ &= \tfrac{1}{2} \sum_{i=1}^n (-E[v_i|b_i=-1] + E[v_i|b_i=1]) \end{align}
3. Si las entradas de $A$ son enteros delimitada de manera uniforme por $|a_{ij}| \leq k$, la distribución exacta de $(Ab)_i$ puede ser calculado en $O(kn^2)$ tiempo por iterativo de convolución. A partir de este se puede obtener a $E[v_i|b_i]$, lo que junto con la observación (2) produce una $O(kn^3)$ algoritmo para el cálculo de la expectativa en el caso de $A$ con delimitada entero entradas.
4. El algoritmo a partir de la observación (3) puede ser extendida para el caso de que las entradas de $A$ han precisión finita: por ejemplo, si las entradas de $A$ están restringidos a 0, +/- 0.1, +/- 0.2, etc. uno puede simplemente escala de $A$ por un factor de 10 para obtener un número entero de la matriz. Esto nos permite aproximarse a la expectativa con precisión arbitraria, pero el algoritmo de complejidad de las escalas de forma exponencial con el número de dígitos.
5. A partir de la observación (2) podemos ver que $E[v_i|b_i]$ es necesario para el cálculo de la expectativa. Este es trivial para calcular si hay una entrada $a_{ij}$ tal que $$|a_{ij}| > \sum_{k \neq j} |a_{ik}|$$, Pero en general, la informática, esta expectativa nos obliga a contar el número de maneras en las que una secuencia arbitraria de números enteros se pueden sumar para superar cero. Este problema es conocido por ser #P duro.

Answer 2

Si lo que quieres es una solución práctica para un determinado "valor" de Una, simplemente emplean la simulación estocástica, y producir un intervalo de confianza en la estimación de la expectativa.

No voy a tratar de determinar si hay una buena reducción de varianza esquema disponible, que supongo que hay (como variables de control). Porque usted puede muy rápidamente explosión de the living daylights fuera de esto haciendo cientos de millones de replicaciones.

Por otro lado, si usted necesita para realizar esta para una alta precisión en tiempo real para valores grandes de n con Un nuevo matrices ser proporcionado varias veces por segundo ....

Answer 3

Tome $n=2$. A continuación,$\nu_1=a_{11}b_1+a_{12}b_2$. Examinemos $b_1sign(\nu_1)$. Esta es una función de $(b_1,b_2)$. Vector de $(b_1,b_2)$ alcanza valores de $\{(1,1),(1,-1),(-1,1),(-1,-1)\}$, con igual probabilidad de 1/4. Sustituyendo estos valores en la función $b_1sign(a_{11}b_1+a_{12}b_2)$ podemos obtener la distribución exacta de dicha función.

Podemos repetir este proceso para $\nu_2$ general $n$, dada la particular de la matriz $A$. No sería difícil escribir un programa que hace eso. La alimentación a diferentes matrices que se le dará a usted una idea teórico sobre el comportamiento de dicha función, sin embargo no estoy seguro de que hay una solución analítica exacta para arbitrario de la matriz $A$.