2
$\begingroup$

Let $a$ and $b$ be chosen independently and uniformly at random from $\mathbb{Z}_n=\{0,1,2,\ldots,n-1\}$, where $n$ is a prime. Suppose we generate $t$ pseudo-random numbers from $\mathbb{Z}_n$ by choosing $r_i=ai+b \mod{n}$, for $1\le i\le t$. For any $\epsilon\in[0,1]$, show that there is a choice of the witness set $W\subset\mathbb{Z}_n$ such that $|W|\ge\epsilon n$ and the probability that none of the $r_i$'s lie in the set $W$ is at least $(1-\epsilon)^2/4t$.

The above is problem 3.7 from "Randomized Algorithms" by Motwani and Raghavan" from Chapter 3, Moments and Deviation. Some relevant facts (Exercise 3.7 and 3.8) from earlier in the chapter may be that (1) the distribution of each $r_i$ is uniformly on $\mathbb{Z}_n$, (2) $r_i$ and $r_j$ are pairwise independent for $i\neq j$, and (3) that for $X=\sum_{i=1}^mX_i$ for pairwise independent random variables, the variance of $X$ is the sum of the variances of the $X_i$.

For a fixed set $W$, a simple upper bound on the probability that none of the $r_i$'s lie in $W$ is $(1-t\epsilon)$ through a union bound. Moreover, since the expected number of $r_i$'s in $W$ is $\epsilon t$ and the variance is $\epsilon(1-\epsilon)t$, I also see how to use Chebyshev's inequality to upper bound the probability that none of the $r_i$'s is contained in $W$, which would give $\frac{(1-\epsilon)}{\epsilon t}$.

Am I missing something obvious? Thanks in advance!

$\endgroup$

1 Answer 1

2
$\begingroup$

I think you're overthinking this. Construct the witness set $W=\{0, 1, ..., \epsilon n\}$ (or really any contigious sequence of size $\epsilon n$).

Consider the events where $b$ was selected from $\{\epsilon n + 1, ..., \epsilon n + \frac{(1-\epsilon)n}{2}\}$, and $a$ was selected from $\{0, ..., \frac{(1-\epsilon)n}{2t}\}$. Then the range of $r_i$s is from $\epsilon n +1$ to $n-1$ (you might need a few floors here). So all the $\{r_i\}$ miss $W$.

This event happens with probability $\frac{1-\epsilon}{2}\cdot \frac{1-\epsilon}{2t}$, so the probability the $\{r_i\}$ miss $W$ is at least that (there could be other disjoint events where you miss $W$). You were instead calculating an upper bound with Chebychev's inequality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.