espaços de probabilidade independentes

8

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

Suponha que tenhamosn variáveis ​​aleatóriasY1,,Yn , cada uma comb bits de comprimento. (Ou seja, com valores em{0,,2b1} ). Queremos um espaço de probabilidade onde cadaYi seja imparcial (assume cada valor com probabilidade exatamente2b ) e temk independência. Ou seja, para qualqueri1<<ik e qualquery1,,yk temos

P(Yi1=y1Yik=yk)=2kb

Quando b=1 você sempre pode obter um espaço probabilístico de tamanho nk e, às vezes, obter nk/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

David Harris
fonte
GF(2max{b,log2n})k1nmax{2kb,nk}
1
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
Yury

Respostas:

5

Para arbitrário , Alon, Babai e Itai mostraram um limite inferior no tamanho do espaço de probabilidade de m ( n , k / 2 ) onde bm(n,k/2)

m(n,k)=i=0k(ni)

que é para a constante .Ω(nk/2)k

Eles também deram uma construção do tamanho no caso de .O(nk/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=1p1,,pnpi=P(Yi=1)p1,,pnm(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(nk)

Marc Bury
fonte