weise unabhängige Wahrscheinlichkeitsräume

Ich hatte große Schwierigkeiten, eine Referenz zu finden, die Folgendes einfach und unkompliziert erklärt:

Angenommen, wir haben $n$ Zufallsvariablen $Y_1, \dots, Y_n$ , die jeweils $b$ Bit lang sind. (Dh mit Werten in $\{0, \dots, 2^b-1 \}$ ). Wir wollen einen Wahrscheinlichkeitsraum, in dem jedes $Y_i$ unverzerrt ist (nimmt jeden Wert mit einer Wahrscheinlichkeit von genau $2^{-b}$ ) und $k$ Unabhängigkeit hat. Das heißt, für jedes $i_1 < \dots < i_k$ und jedes $y_1, \dots, y_k$ haben wir

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

Wenn $b = 1$ , können Sie immer einen Wahrscheinlichkeitsraum der Größe $n^{k}$ und manchmal können Sie $n^{k/2}$ Gibt es eine klare Aussage darüber, wann diese möglich sind?

Kann mich jemand auf Hinweise verweisen, was passiert, wenn $b > 1$ ?

Vielen Dank

pr.probability limited-independence David Harris
quelle

Ich bin nicht sicher, was die Referenz ist, aber die Konstruktion, die ich kenne, ist: Wählen Sie ein zufälliges Polynom über

Grad höchstens

und bewerten Sie es an

Punkten . Dies ergibt einen Probenraum der Größe

. Ist dies das Ergebnis, nach dem Sie suchen?

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

Es gibt eine gute Umfrage zu diesem Thema von Salil Vadhan; Es ist online verfügbar: people.seas.harvard.edu/~salil/pseudorandomness . Kapitel 3 behandelt

weise unabhängige Zufallsvariablen.

k

$k$

Yury

Antworten:

Für beliebige , Alon, Babai und Itai zeigte eine untere Schranke für die Wahrscheinlichkeitsraum Größe von wobei $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}$

Das ist für die Konstante . $\Omega(n^{k/2})$ $k$

Sie gaben auch eine Konstruktion der Größe im Fall von . $O(n^{k/2})$ $b = 1$

Für gibt es eine Arbeit von Karloff und Mansour, die untere und obere Grenzen für beliebige Wahrscheinlichkeiten zeigt, dh für mit . Beispielsweise gibt es Wahrscheinlichkeiten so dass die Wahrscheinlichkeitsraumgröße mindestens beträgt . Sie sagen auch, dass auch eine Obergrenze für beliebige Wahrscheinlichkeiten ist. $b=1$ $p_1,\ldots,p_n$ $p_i = P(Y_i = 1)$ $p_1,\ldots,p_n$ $m(n,k)$ $m(n,k)$

Ich kenne keine Konstruktion mit einer besseren Obergrenze als die durch die von Thomas als Kommentar erwähnte Konstruktion (siehe hier ) gegeben ist. $O(n^k)$

Marc Bury
quelle