Minimum probability of biased coin to satisfy particular condition 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)
 A: 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:

*

*None of the $\{y_i\}$ equals 1, which happens with probability $p^4$.

*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}$$

*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$.
