1 Probability and Computing 1 Probability and Computing 1.2 Discrete Random Variable and Expectation

1.1 Events and Probability

Exercise 1.1.1 (Exercise 1.6 [MU17]).

Consider the following balls-and-bin game. We start with one black ball and one white ball in a bin. We repeatedly do the following: choose one ball from the bin uniformly at random, then put the ball back in the bin with another ball of the same color. We repeat until there are $n$ balls in the bin. Show that the number of white balls is equally likely to be any number between $1$ and $n-1$ .

Proof.

We rethink the behavior as: choose a color from the current balls in bin, and add one more ball with same color to the bin. Then we introduce a random variable $X_{n}$ representing the number of white balls in the bin, where there are $n$ balls in bin in total. The probability of $k$ white balls among $n$ balls can be represented by

	$\displaystyle\Pr\left[X_{n}=k\right]$	$\displaystyle=\Pr\left[X_{n}=k\mid X_{n-1}=k-1\right]\cdot\Pr\left[X_{n-1}=k-1\right]$
		$\displaystyle+\Pr\left[X_{n}=k\mid X_{n-1}=k\right]\cdot\Pr\left[X_{n-1}=k\right]$
		$\displaystyle=\frac{k-1}{n-1}\cdot\Pr\left[X_{n-1}=k-1\right]+\left(1-\frac{k}% {n-1}\right)\cdot\Pr\left[X_{n-1}=k\right].$

By induction we can have that, the probability of $X_{n}$ being $k$ is $1/(n-1)$ . ∎

Exercise 1.1.2 (Exercise 1.14 [MU17]).

Suppose I am playing in a tournament against a player never played before. Consider 3 probabilities for my prior model: we are equally talented, and each of us is equally likely to win each game; I am slightly better, and I win each game independently with probability $0.6$ ; or he is slightly better, and he wins each game independently with probability $0.6$ . Before we play, I think that each of these 3 probabilities is equally likely.

In the match we play until one player wins three games. I win the second game, but he wins the first, third, and fourth. After this match, with what probability should I believe that my opponent is slightly better than I am?

Proof.

This is the Bayesian prior to posterior update.

Let $E$ be the event that “I won the second and he won the first/third/fourth”.

Let $C_{0}$ be the event that he is better, $C_{1}$ be the event that I am better, $C_{2}$ be the event that we are equally talented. Then $C_{0},C_{1},C_{2}$ are disjoint events, with prior model on $C_{i}$ being $\Pr\left[C_{i}\right]=1/3$ . The posterior model on $C_{0}$ is derived by the Bayes’ law

	$\displaystyle\Pr\left[C_{0}\mid E\right]$	$\displaystyle=\frac{\Pr\left[E\mid C_{0}\right]\cdot\Pr\left[C_{0}\right]}{% \sum_{i\in[0,2]}\Pr\left[E\mid C_{i}\right]\cdot\Pr\left[C_{i}\right]}$
		$\displaystyle=\frac{\Pr\left[E\mid C_{0}\right]}{\sum_{i\in[0,2]}\Pr\left[E% \mid C_{i}\right]},$

and each $\Pr\left[E\mid C_{i}\right]=p_{i}\cdot(1-p_{i})^{3}$ , where $p_{i}$ is the probability of me winning a game preconditioned in $C_{i}$ .

Therefore, the exact probability of he is better preconditioned that $E$ happened is

\Pr\left[C_{0}\mid E\right]=\frac{0.6^{3}\cdot 0.4}{0.6^{3}\cdot 0.4+0.5^{4}+0% .4^{3}\cdot 0.6}\approx 0.46.

∎

Exercise 1.1.3 (Exercise 1.18 [MU17]).

We have function $F:[0,n-1]\to[0,m-1]$ , and we know $F((x+y)\mod n)=(F(x)+F(y))\mod m$ for $x,y\in[0,n-1]$ . The only way we have for evaluating $F$ is to use a lookup table that stores the values of $F$ . An adversary changed the value of $1/5$ of the table entries.

Describe a simple randomized algorithm that, given an input $z$ , outputs a value that equals $F(z)$ with probability at least $1/2$ . The algorithm should be working for every $z\in[0,n-1]$ , regardless of what values the adversary changed. The algorithm should use as few lookups and as little computation as possible.

Suppose I allow you to repeat the initial algorithm three times, what is the probability of the enhanced version of algorithm returning the correct answer?

Proof.

This looks very much like BLR linearity testing [BLR93]. We construct a random function as follows:

•

Sample $\alpha\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}[0,n-1]$ , and query $F(\alpha)$ and $F((z+\alpha)\mod n)$ .
•

Output $(F((z+\alpha)\mod n)-F(\alpha))\mod m$ .

Since the error probability at a single query is $1/5$ , the probability of this algorithm giving right answer is lower bounded by $3/5\geq 1/2$ .

Now that the error probability of our algorithm is upper bounded by $2/5$ , if we repeat the algorithm 3 times, the algorithm returning none of them being correct has probability upper bounded by $(2/5)^{3}$ .

•

The probability of existing a correct answer is lower bounded by $1-(2/5)^{3}$ .
•

If the majority are correct, then $(3/5)^{3}+3\times(2/5)\times(3/5)^{2}\geq 81/125$ .

Try majority vote from 3 repetition as an enhanced version, then the correctness is lower bounded by $81/125$ . ∎