Mínima distancia de distribución en un subconjunto aleatorio de vectores binarios + de Hamming

Question

Seleccione $K$ random vectores binarios $Y_i$ de la longitud de la $m$ uniformemente al azar.

Vamos a la siguiente colección de variables aleatorias se define como: $X_{i,j}=w(Y_i \oplus Y_j)$ donde $w(\cdot)$ denota el peso de Hamming de un vector binario, es decir, el número de los distinto de cero de las coordenadas en su argumento. Definir $D_{min}(Y_1,\ldots,Y_K)$ como la más pequeña de las $X_{i,j}$ $i \neq j.$

Así tenemos a $n=C(K,2)=K(K-1)/2$ no-independiente de las variables aleatorias $X_{i,j}$ con el apoyo {$0,1,\ldots,m$} y distribución individual $Bin(m,1/2)$. A mí me parece que las variables aleatorias $X_{i,j}$ $s$- sabio correlacionó negativamente (por $s$ lo suficientemente grande) si las distancias entre los pares elegidos a partir de una subcolección de $Y_{i_1},Y_{i_2},\ldots,Y_{i_v}$ donde: ( $v < K$ ) tincreases, a continuación, las distancias entre las $Y_{i_j}$ y el resto de los vectores tenderá a disminuir. Tome $s=v+1.$

Es posible obtener un límite en la cantidad. Fix $w$ un entero menor que $m/2.$ El Hamming esfera de radio w tiene "volumen", es decir, contiene $V_w(m)=\sum_{s=0}^w C(m,s)$ vectores y tenemos aproximadamente la mitad de primer orden en el exponente $$ V_w(m) =2^{m H((w+1)/2)} $$ donde $H(\cdot)$ es el binario de la entropía de la función. Entonces, por un azar del uniforme de la selección de la $Y_i$ $i=1,2,\ldots,K$ es claro que si el Hamming esferas centradas en estos vectores son distintos, entonces la distancia mínima es de al menos $2w+1$, con lo que $Pr[D_{min} \geq 2 w+1] \leq \frac{(2^m-V)}{2^m}\frac{ (2^m-2 V) }{2^m} \cdots\frac{ (2^m - (K-1)V)}{ 2^{m}}$

donde $V=V_w(m).$ Esto significa que, mediante la sustitución de cada fracción de la forma $(1-x)$ $exp(-x)$ donde $x >0$ pero pequeño, se obtiene el límite superior aproximado $Pr[ D_{min} \geq 2w+1] \leq exp\left[-K(K-1)V^2/(2^{m+1} \right]$ , lo que expresa este límite superior en términos de la entropía de la función, lo cual es bueno. Por desgracia, este límite superior es bastante flojo.

Voy a ser feliz con los punteros a la literatura o cualquier otra sugerencia.

Answer 1

Aquí es una aplicación directa del Teorema de 21 de Gabor Lugosi la concentración de la medida de notas. Su $Y_i$ corresponde a su $X_{i,1}^m$ e su $X_{i,j}$ a de su $d(X_{i,1}^m, X_{j,1}^m)$. Tome su $A$ a de su $\{X_{i,j}\}_{i \neq j}$. El problema del cumpleaños le da la probabilidad de que cualquiera de las dos de la $Y_i$ son exactamente los mismos. Que es: $$\mathbb{P}(0^m \in A) = \mathbb{P}\left(\left\{X_{i,j} = 0^m : i \neq j\right\}\right) = \mathrm{(omitted\ for\ simplicity)} $$ Ahora su $D_{min}$ corresponde a su $d(0^m,A)$. Por el Teorema de, por cualquier $t > 0$, $$\mathbb{P}\left(D_{min} \geq t + \sqrt{\frac{m}{2} \mathrm{log}\frac{1}{\mathbb{P}(0^m \in A)}}\right) \leq e^{-2t^2/m}.$$ Esta obligado puede estar bien para sus necesidades. Si no lo está, consulte Lugosi la discusión de Talagrand del convexa de la distancia de la desigualdad, que es una gran mejora.