Aunque el problema es en general intratable, tu ejemplo motivador supone eventos independientes, lo que proporciona una estructura más que suficiente para resolver este problema. Permítame volver a exponer lo que intenta demostrar para asegurarme de que lo entiendo:
Usted tiene $n$ variables aleatorias binomiales independientes $X_i\sim \mathrm{Binomial}(p_i)$ , $i=1,\dotsc,n$ . Su objetivo es encontrar un punto $\hat x \in \{0, 1\}^n$ que maximiza la probabilidad $$\mathbb{P}\{\mathrm{d}_H(\hat x, {X})\le k\},$$ donde $\mathrm{d}_H$ denota la métrica de Hamming y ${X}=(X_1,\dotsc,X_n)$ es el vector de variables aleatorias binomiales.
Debido a la independencia, la respuesta es trivial: Elija el punto más probable es decir, el conjunto
$$ \hat{x}_i = \begin{cases} 0,& p_i \le 0.5 \\ 1, &p_i >0.5.\end{cases}$$
Veamos por qué esto es cierto utilizando la inducción. La receta anterior es trivial para $n=1$ . Sea $n>1$ y supongamos que la receta es válida para $n-1$ . Entonces, por la independencia,
$$ \mathbb{P}\{ \mathrm{d}_H(x,X)\le k\} = \mathbb{P}\{x_n = X_n\} \mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)}) \le k\} + \mathbb{P}\{x_n \ne X_n\} \mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)}) \le k-1\}$$
donde utilizamos la abreviatura $x^{(n-1)} = (x_1,\dotsc,x_{n-1})$ . Por la hipótesis de inducción, nuestra mejor elección posible de $x^{(n-1)}$ est $\hat{x}^{(n-1)}$ el punto más probable de $X^{(n-1)}$ . Además, como siempre tenemos
$$\mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)}) \le k\} \ge \mathbb{P}\{\mathrm{d}_H({x}^{(n-1)}, X^{(n-1)})\le k-1\},$$
debemos elegir siempre ${x}_n$ para maximizar $\mathbb{P}\{\hat x_n = X_n\}$ que es la receta reclamada. #
¿Cerca de la independencia?
La independencia es claramente una suposición muy fuerte, pero en muchos casos tenemos razones para creer que los elementos son casi independiente. Una forma común de medir la "cercanía" de las variables aleatorias (digamos, binarias) $X$ y $Y$ es el métrica de variación total :
$$ d_{TV}(X,Y):= \sup_{A \subset \{0,1\}^n} | \mathbb{P}\{ X \in A\} - \mathbb{P}\{Y\in A\} | $$
Tomando, por ejemplo, $A:= \{y \mid d_H(x,y) \le k\}$ encontramos que para cualquier variable aleatoria binaria $X$ , $Y$
$$ |\mathbb{P}\{ d_H(x, X) \le k\} - \mathbb{P}\{d_H(x,Y)\le k\}| \le d_{TV}(X,Y).$$
Concluimos que cuando $Y$ es "casi independiente" en el sentido de que la distancia de la norma TV a una variable RV $X$ con entradas independientes es muy pequeño, entonces es posible argumentar que tomar $\hat x$ para ser el vector más probable para $X$ también es una buena opción para $Y$ .
Hay que tener cuidado Sin embargo, no se puede aplicar esta lógica. En primer lugar, no he dado ninguna pista sobre cómo calcular una métrica de televisión; tendrás que utilizar los datos concretos que tengas a mano y algo de ingenio.
Un peligro más sutil reside en el hecho de que la estimación de la norma de televisión suele ser inútil a menos que $k$ es grande . Esto se debe a que el supremum en la TV se producirá a menudo para los conjuntos $A$ con medida cerca de $1/2$ . A menos que $k$ es grande, es probable que la bola de Hamming de anchura $k$ tiene una medida minúscula en comparación con la norma televisiva.
Es posible que pueda afinar un poco sus argumentos, pero la capacidad de controlar el error utilizando este enfoque depende (una vez más) en gran medida de su situación particular.
