next up previous contents
Next: Lecture 12 Up: Detour: Small stochastic spaces Previous: Detour: Small stochastic spaces

How to generate pairwise independence

Select a prime p, $n\le p\le 2n$. Such a prime exists because of the density of primes. For each vertex u, choose an integer au such that $\frac{a_u}{p}\approx \frac 1{2d(u)}$, and an interval Au, |Au|=au in Zp.

Let X(u) be the random variable from uniformly choosing $x,y\in Z_p$ and setting
\begin{displaymath}
X(u)=
 \begin{cases}
 1&\text{ if $xu+y\in A_u$, and}\  0& \text{ otherwise.}
 \end{cases}\end{displaymath} (13)
This means that $\Pr(X(u)=1)=\frac {a_u}p\approx \frac 1{2d(u)}$ because
\begin{multline}
\Pr_{x,y}(X(u)=1)=\Pr(\exists a\in A_u: xu+y=a)\  =\sum_{a\in A_u}\Pr(x=(a-y)u^{-1}) = \sum_{a\in A_u}\frac 1p=\frac {a_u}p.\end{multline}
For pairwise independence, we would like to conclude that
\begin{displaymath}
\Pr(X(u)=1, X(v)=1)=\Pr(X(u)=1)\Pr(X(v)=1)=\frac{a_ua_v}{p^2}.\end{displaymath} (14)
This is also true because of the following.
\begin{displaymath}
\begin{split}
 \Pr(X(u)=1, X(v)=1)
 &= \Pr(\exists a\in A_u,...
 ...b)\in A_u\times A_v}\frac1{p^2}=\frac{a_ua_v}{p^2}
 \end{split}\end{displaymath} (15)


Viggo Kann
Sat Dec 20 23:41:16 MET 1997