Deje $X_i$ ser independientes de Bernoulli variables aleatorias con probabilidades de éxito $p_i$. Es decir, $\mathbb{P}(X_i = 1) = p_i, \mathbb{P}(X_i = 0) = 1-p_i$. Hay un circuito cerrado de expresión o de una fórmula aproximada para la siguiente expectativa? $$\mathbb{E}\left(\frac{\sum_i \sum_j X_i X_j B_{ij}}{(\sum_i X_i)^2}\right)$$ donde $B_{ij}$ son los coeficientes y $B_{ij} = B_{ji}, B_{ii} = 0, \forall i, j$.
En la forma de la matriz, esta es una relación de dos formas cuadráticas (mientras que la última tiene una potencia de 2)
$$\mathbb{E}\left(\frac{\mathbf{X}^T \mathbf{B} \mathbf{X}}{(\mathbf{X}^T \mathbf{X})^2}\right)$$
donde $\mathbf{B}$ es una diagonal libre matriz simétrica.
Intuitivamente, este valor se espera que el valor promedio de una submatriz de a $\mathbf{B}$ donde las filas (y columnas) son escogidos al azar.
Puede ser evaluada en tiempo exponencial mediante la enumeración de todos los escenarios. Pero me pregunto si hay métodos que puede evaluar esta expectativa en el polinomio de tiempo.
Tenga en cuenta que si podemos evaluar $$\mathbb{E}\left(\sum_i \sum_j X_i X_j B_{ij} \Big| \sum_i X_i = m\right)$$ a continuación, hemos terminado, ya que la distribución de $\sum_i X_i$ es conocido (Poisson, Binomial Disribution)
Nota demasiado que ya he averiguado la siguiente expectativa $$\mathbb{E}\left(\sum_i C_i X_i \Big| \sum_i X_i = m\right) = \frac{1}{P_k}\sum_{n=0}^N \sum_{j=1}^N \frac{A^{-nm+n}}{(N+1)}p_j C_j \prod_{\substack{k=1\\k\neq j}}^N (p_k A^n + (1-p_k))$$ $$P_k = \mathbb{P}\left(\sum_i X_i = m\right) = \frac{1}{N+1}\sum_{n=0}^N A^{-nm}\prod_{j=1}^N (p_j A^n + (1-p_j)),\quad A = e^{2i\pi/(N+1)}$$ utilizando el método introducido en Fernández (2010).
Respuesta
¿Demasiados anuncios?
Acabo de encontrar una expresión de forma cerrada para la expectativa, que se puede evaluar en tiempo polinómico.
\begin{align} &\mathbb{E} \left[\left( \displaystyle\sum_{i=1}^N X_i \right)^{-2} \sum_{\substack{1\le i, j\le N \\ i\neq j}} X_iX_j B_{ij} \right] \\ &= \sum_{m=2}^N \mathbb{E} \left[\left( \displaystyle\sum_{i=1}^N X_i \right)^{-2} \sum_{\substack{1\le i, j\le N \\ i\neq j}} X_iX_j B_{ij} \left| \sum_{i=1}^N X_i = m \right. \right] \mathbb{P}\left( \sum_{i=1}^N X_i = m \right) \\ &= \sum_{m=2}^N \mathbb{E} \left[\left( \displaystyle\sum_{i=1}^N X_i \right)^{-2} \sum_{\substack{1\le i, j\le N \\ i\neq j}} X_iX_j B_{ij} \left| \sum_{i=1}^N X_i = m \right. \right] \mathbb{P}\left( \sum_{i=1}^N X_i = m \right) \\ &= \sum_{m=2}^N \frac{1}{m^2} \sum_{\substack{1\le i, j\le N \\ i\neq j}} B_{ij} \mathbb{E} \left[ X_iX_j \left| \sum_{i=1}^N X_i = m \right. \right] \mathbb{P}\left( \sum_{i=1}^N X_i = m \right) \\ &= \sum_{m=2}^N \frac{1}{m^2} \sum_{\substack{1\le i, j\le N \\ i\neq j}} B_{ij} \mathbb{P} \left( X_i = 1, X_j = 1 \left| \sum_{i=1}^N X_i = m \right. \right) \mathbb{P}\left( \sum_{i=1}^N X_i = m \right) \\ &= \sum_{m=2}^N \frac{1}{m^2} \sum_{\substack{1\le i, j\le N \\ i\neq j}} B_{ij} \mathbb{P} \left( \left. \sum_{i=1}^N X_i = m \right| X_i = 1, X_j = 1 \right) \mathbb{P}\left( X_i = 1, X_j = 1 \right) \\ &= \sum_{m=2}^N \frac{1}{m^2} \sum_{\substack{1\le i, j\le N \\ i\neq j}} B_{ij} p_i p_j \sum_{n=0}^N \frac{1}{(N+1)} A^{-nm+2n} \prod_{\substack{k=1\\k\neq i,j}}^N (p_k A^n + (1-p_k)) \\ \end{align}
Tenga en cuenta que$m$ comienza a partir de 2 como cuando$m < 2$ la expectativa condicional es 0. En lugar de$O(2^N)$, esta fórmula puede ser evaluada en$O(N^5)$ de tiempo.
