espaços de probabilidade independentes

Tenho tido muita dificuldade em encontrar uma referência que dê uma explicação simples e direta do seguinte:

Suponha que tenhamos $n$ variáveis aleatórias $Y_1, \dots, Y_n$ , cada uma com $b$ bits de comprimento. (Ou seja, com valores em $\{0, \dots, 2^b-1 \}$ ). Queremos um espaço de probabilidade onde cada $Y_i$ seja imparcial (assume cada valor com probabilidade exatamente $2^{-b}$ ) e tem $k$ independência. Ou seja, para qualquer $i_1 < \dots < i_k$ e qualquer $y_1, \dots, y_k$ temos

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}$

Quando $b = 1$ você sempre pode obter um espaço probabilístico de tamanho $n^{k}$ e, às vezes, obter $n^{k/2}$ - há alguma declaração clara sobre quando isso é possível?

Alguém pode me indicar referências sobre o que acontece quando $b > 1$ ?

obrigado

pr.probability limited-independence David Harris
fonte

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\}$

Há uma boa pesquisa sobre o tema por Salil Vadhan; está disponível online: people.seas.harvard.edu/~salil/pseudorandomness . O Capítulo 3 aborda variáveis aleatórias independentes, em sentido horário.

k

$k$

Yury

Respostas:

Para arbitrário , Alon, Babai e Itai mostraram um limite inferior no tamanho do espaço de probabilidade de onde $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 é para a constante . $\Omega(n^{k/2})$ $k$

Eles também deram uma construção do tamanho no caso de . $O(n^{k/2})$ $b = 1$

Para há um artigo de Karloff e Mansour que mostra limites inferiores e superiores para probabilidades arbitrárias, isto é, para com . Por exemplo, existem probabilidades modo que o tamanho do espaço de probabilidade seja pelo menos . Eles também dizem que também é um limite superior para probabilidades arbitrárias. $b=1$ $p_1,\ldots,p_n$ $p_i = P(Y_i = 1)$ $p_1,\ldots,p_n$ $m(n,k)$ $m(n,k)$

Não conheço nenhuma construção com um limite superior melhor que que é dado pela construção (veja aqui ) mencionada por Thomas como comentário. $O(n^k)$

Marc Bury
fonte