espacios de probabilidad independientes -wise

He tenido muchas dificultades para encontrar una referencia que ofrezca una explicación simple y directa de lo siguiente:

Supongamos que tenemos variables aleatorias , cada una de bits de longitud. (Es decir, con valores en ). Queremos un espacio de probabilidad donde cada sea imparcial (toma cada valor con probabilidad exactamente ), y tiene independencia. Es decir, para cualquier y cualquier tenemos $n$ $Y_1, \dots, Y_n$ $b$ $\{0, \dots, 2^b-1 \}$ $Y_i$ $2^{-b}$ $k$ $i_1 < \dots < i_k$ $y_1, \dots, y_k$

P (Y_{i_{1}} = y_{1} \land \dots \land Y_{i_{k}} = y_{k}) = 2^{- k b}

$P(Y_{i_1} = y_1 \wedge \dots \wedge Y_{i_k} = y_k) = 2^{-k b}$

Cuando siempre puede obtener un espacio de probabilidad de tamaño y, a veces, puede obtener . ¿Hay alguna afirmación clara sobre cuándo es posible? $b = 1$ $n^{k}$ $n^{k/2}$

¿Alguien puede señalarme referencias sobre lo que sucede cuando ? $b > 1$

Gracias

pr.probability limited-independence David Harris
fuente

No estoy seguro de cuál es la referencia, pero la construcción que conozco es: elija un polinomio aleatorio sobre de grado como máximo y evaluarlo en puntos. Esto proporciona un espacio muestral de tamaño . ¿Es este el tipo de resultado que estás buscando?

G F (2^{max {b, ⌈ \log_{2} n ⌉}})

$GF(2^{\max\{b,\lceil \log_2 n \rceil\}})$

k - 1

$k-1$

n

$n$

max {2^{k b}, n^{k}}

$\max\{2^{kb}, n^k\}$

Thomas

Hay una buena encuesta sobre el tema realizada por Salil Vadhan; está disponible en línea: people.seas.harvard.edu/~salil/pseudorandomness . El Capítulo 3 cubre las variables aleatorias independientes -wise.

k

$k$

Yury

Respuestas:

Para el arbitrario , Alon, Babai e Itai mostraron un límite inferior en el tamaño del espacio de probabilidad de donde $b$ $m(n,\lfloor k/2 \rfloor)$

m (n, k) = \sum_{i = 0}^{k} (\binom{n}{i})

$m(n,k) = \sum\limits_{i=0}^k \binom{n}{i}$

que es para constante . $\Omega(n^{k/2})$ $k$

También dieron una construcción de tamaño en el caso de . $O(n^{k/2})$ $b = 1$

Para hay un artículo de Karloff y Mansour que muestra límites inferiores y límites superiores para probabilidades arbitrarias, es decir, para con . Por ejemplo, hay probabilidades modo que el tamaño del espacio de probabilidad sea al menos . También dicen que también es un límite superior para las probabilidades arbitrarias. $b=1$ $p_1,\ldots,p_n$ $p_i = P(Y_i = 1)$ $p_1,\ldots,p_n$ $m(n,k)$ $m(n,k)$

No conozco ninguna construcción con un límite superior mejor que que viene dada por la construcción (ver aquí ) mencionada por Thomas como comentario. $O(n^k)$

Marc Bury
fuente