Minimum probability of biased coin to satisfy particular condition

Question

Take $n$ pairs of integers $(x_i,y_i)$, $1\leq i\leq n$, selected independently as follows:

Toss a fair coin $X$ and a biased coin $Y$ with $$\Pr[Y=\text{heads}] = p \neq 1$$

• If $(X=\text{heads})$, then $x_i=-1$, otherwise $x_i=1$
• If $(Y=\text{heads})$, then $y_i=0$, otherwise $y_i=1$

Find $\min(p)$ such that $\Pr[\sum_{i=1}^{n}x_iy_i=0]\geq a$ for some given $a$.

(Note: not a homework question)

Answer 1

Warm-up ($n=4$ case)

Start with the case of $n=4$. We want to know $\text{Pr}\left(\sum_{i=1}^4 x_i y_i = 0\right)$. There are three cases where this sum could be zero:

1. None of the $\{y_i\}$ equals 1, which happens with probability $p^4$.
2. Exactly two of the $\{y_i\}$ equal 1, which follows a Binomial distribution, ie. $\binom{4}{2}p^2\left(1-p\right)^2$. Furthermore, exactly 1 of the two $\{x_i\}$ associated with non-zero $y_i$'s must take the value of -1, which is also Binomial: $\binom{2}{1}\left(\widetilde p\right)^1\left(1-\widetilde p\right)^{2-1}$, where $\widetilde p$ is the probability of $x_i$ being -1, so $\widetilde p=\frac{1}{2}$ in your case. Therefore, the probability of this event is $$\binom{4}{2}p^2\left(1-p\right)^2 \binom{2}{1}\left(\widetilde p\right)^1\left(1-\widetilde p\right)^{2-1}$$
3. Exactly four of the $\{y_i\}$ equal 1 (ie. all of them), which has probability $\binom{4}{4}\left(1-p\right)^4$, and the four $x_i$'s associated with the non-zero $y_i$'s must take the value of -1, which happens with probability: $\binom{4}{2}\left(\widetilde p\right)^2\left(\widetilde p\right)^{4-2}$. Therefore the probability is $$\binom{4}{4}\left(1-p\right)^4 \binom{4}{2}\left(\widetilde p\right)^2\left(1-\widetilde p\right)^{4-2}$$

And to get $\text{Pr}\left(\sum_{i=1}^4 x_i y_i = 0\right)$, we just sum these cases together.

General Case

This method can be generalized to $n$ integer pairs, giving

$$\text{Pr}\left(\sum_i^n x_i y_i = 0\right) = \sum_{j=0,2,4,\ldots}^n \binom{n}{j}p^{n-j} (1-p)^j \binom{n-j}{\frac{n-j}{2}}\left(\widetilde p\right)^{\frac{n-j}{2}}\left(1-\widetilde p\right)^{\frac{n-j}{2}}$$

where $\widetilde p \equiv \text{Pr}\left(x_i=-1\right)=\frac{1}{2}$, and in the summation on the right-hand side, if $n$ is odd, stop summation at $n-1$.

The question is now: for what value of $p$ does this probability equal $a$? We therefore must solve for $p$ in an $n$-th order polynomial of $p$. If $n\geq5$, you cannot solve this analytically, but a computer could numerically solve it for particular values of $a$.