<p>I think you're overthinking this. Construct the witness set <span class="math-container">$W=\{0, 1, ..., \epsilon n\}$</span> (or really any contigious sequence of size <span class="math-container">$\epsilon n$</span>).</p>
<p>Consider the events where <span class="math-container">$b$</span> was selected from <span class="math-container">$\{\epsilon n + 1, ..., \epsilon n + \frac{(1-\epsilon)n}{2}\}$</span>, and <span class="math-container">$a$</span> was selected from <span class="math-container">$\{0, ..., \frac{(1-\epsilon)n}{2t}\}$</span>. Then the range of <span class="math-container">$r_i$</span>s is from <span class="math-container">$\epsilon n +1$</span> to <span class="math-container">$n-1$</span> (you might need a few floors here). So all the <span class="math-container">$\{r_i\}$</span> miss <span class="math-container">$W$</span>.</p>
<p>This event happens with probability <span class="math-container">$\frac{1-\epsilon}{2}\cdot \frac{1-\epsilon}{2t}$</span>, so the probability the <span class="math-container">$\{r_i\}$</span> miss <span class="math-container">$W$</span> is <strong>at least</strong> that (there could be other disjoint events where you miss <span class="math-container">$W$</span>). You were instead calculating an <em>upper bound</em> with Chebychev's inequality.</p>

CC BY-SA 4.0
2024-02-04T07:23:28.970Z
2024-02-04T07:23:28.970Z
user3508551
<blockquote>
<p>Let <span class="math-container">$a$</span> and <span class="math-container">$b$</span> be chosen independently and uniformly at random from
<span class="math-container">$\mathbb{Z}_n=\{0,1,2,\ldots,n-1\}$</span>, where <span class="math-container">$n$</span> is a prime. Suppose we
generate <span class="math-container">$t$</span> pseudo-random numbers from <span class="math-container">$\mathbb{Z}_n$</span> by choosing
<span class="math-container">$r_i=ai+b \mod{n}$</span>, for <span class="math-container">$1\le i\le t$</span>. For any <span class="math-container">$\epsilon\in[0,1]$</span>,
show that there is a choice of the witness set <span class="math-container">$W\subset\mathbb{Z}_n$</span>
such that <span class="math-container">$|W|\ge\epsilon n$</span> and the probability that <em>none</em> of the
<span class="math-container">$r_i$</span>'s lie in the set <span class="math-container">$W$</span> is at least <span class="math-container">$(1-\epsilon)^2/4t$</span>.</p>
</blockquote>
<p>The above is problem 3.7 from &quot;Randomized Algorithms&quot; by Motwani and Raghavan&quot; 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 <span class="math-container">$r_i$</span> is uniformly on <span class="math-container">$\mathbb{Z}_n$</span>, (2) <span class="math-container">$r_i$</span> and <span class="math-container">$r_j$</span> are pairwise independent for <span class="math-container">$i\neq j$</span>, and (3) that for <span class="math-container">$X=\sum_{i=1}^mX_i$</span> for pairwise independent random variables, the variance of <span class="math-container">$X$</span> is the sum of the variances of the <span class="math-container">$X_i$</span>.</p>
<p>For a fixed set <span class="math-container">$W$</span>, a simple upper bound on the probability that none of the <span class="math-container">$r_i$</span>'s lie in <span class="math-container">$W$</span> is <span class="math-container">$(1-t\epsilon)$</span> through a union bound. Moreover, since the expected number of <span class="math-container">$r_i$</span>'s in <span class="math-container">$W$</span> is <span class="math-container">$\epsilon t$</span> and the variance is <span class="math-container">$\epsilon(1-\epsilon)t$</span>, I also see how to use Chebyshev's inequality to upper bound the probability that none of the <span class="math-container">$r_i$</span>'s is contained in <span class="math-container">$W$</span>, which would give <span class="math-container">$\frac{(1-\epsilon)}{\epsilon t}$</span>.</p>
<p>Am I missing something obvious? Thanks in advance!</p>

<pr.probability><randomized-algorithms>
Moments and Deviation (Motwani and Raghavan, 3.7)
learning
# Moments and Deviation (Motwani and Raghavan, 3.7)

(Asked by: username_0 on 2024-02-03)

> 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!

**Tags:** pr.probability, randomized-algorithms


---

## 1 answers

### Answer by username_1 on 2024-02-04. Score: 2 | Accepted answer

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.


---

