Probabilities involving $2018$ biased coins

Question

Consider a group of $2018$ biased coins such that for the $n^{th}$ coin the probability $P_{heads} = \frac{1}{p_n}$ where $p_n$ is the $n^{th}$ prime number. Thus the first coin will be unbiased while the second coin will give head $\frac{1}{3}$ times and so on.....

First Question

You toss the $2018$ coins one by one (starting with the first coin and ending with the last) and record the number of head you get. Let the total number of heads to get be equal to $H$. Find the probability $P$ such that $H$ is even.

---

Second Question

Now the first coin (which is unbiased) is removed and another coin is added at the end. So now the $n^{th}$ coin will have $P_{heads} = \frac{1}{p_{n+1}}$. Solve the first question again for this case.

---

Third Question

Does it really matter whether there are $2018$ coins? I believe that the answers should not depend on the total number of coins. Am I correct?

---

This is not homework. A friend asked me this question. I have a feeling that the answer to both questions must be $\frac{1}{2}$ but I am unable to prove it. Can someone help me?

Answer 1

(Expanding on comments)

Q1 Use induction (I got the idea from your Q3 whose answer is affirmative for Q1)

$$P(\sum_{n=1}^{k+1} 1_{H_n} \ \text{is even})$$

$$= P(\sum_{n=1}^{k} 1_{H_n} + 1_{H_{k+1}} \ \text{is even})$$

$$= P(\sum_{n=1}^{k} 1_{H_n} \ \text{is even} \cap 1_{H_{k+1}} = 0) + P(\sum_{n=1}^{k} 1_{H_n} \ \text{is odd} \cap 1_{H_{k+1}} = 1)$$

$$= P(\sum_{n=1}^{k} 1_{H_n} \ \text{is even}) P(1_{H_{k+1}} = 0) + P(\sum_{n=1}^{k} 1_{H_n} \ \text{is odd}) P(1_{H_{k+1}} = 1) \tag{independent?}$$

$$= \frac12 \frac1{p_{k+1}} + \frac12 (1-\frac1{p_{k+1}}) = \frac12 \tag{inductive hypothesis}$$

Now, $H = \sum_{n=1}^{2018} 1_{H_n}$. As it turns out, not only is 2018 irrelevant but also is $p_k$ irrelevant: as long as it is not $0$. It doesn't matter if it's prime, composite or 1.

Q2

(Edit: wait they're not independent. LOL. I can try again next time I guess. Or someone may edit.)

$$P(\sum_{n=1}^{2019} 1_{H_n} - 1_{H_1} \ \text{is even})$$

$$ = P(\sum_{n=1}^{2019} 1_{H_n} \ \text{is even})P(H_1^C) + P(\sum_{n=1}^{2019} 1_{H_n} \ \text{is odd})P(H_1) \tag{again, independent?}$$

$$ = \frac12 \frac12 + \frac12 (1-\frac12) \tag{by Q1}$$

$$ = \frac12$$

Answer 2

If $p_k$ is the probability to get heads on the $k$th throw and $P_k$ is the probability that the number of heads after $k$ throws is even, we have a recurrence relation $$P_k = (1 - p_k) P_{k-1} + p_k (1 - P_{k-1}), \quad P_0 = 1.$$ If $p_k$ is the reciprocal of the $(k + 1)$st prime, $P_{2018}$ is a huge fraction approximately equal to $.50435$. The limit $P_\infty$ appears to be $1/2$. For other sequences the limit will be different.

Answer 3

As others say, it depends on $p_n$.
$$P_n = P_{n-1}(1-\frac1{p_n})+(1-P_{n-1})\frac1{p_n}\\ 2P_n-1 = (2P_{n-1})(1-\frac1{p_n})+(2-2P_{n-1})\frac1{p_n}-(1-\frac1{p_n})-\frac1{p_n}\\ =(2P_{n-1}-1)(1-\frac1{p_n})+(1-2P_{n-1})\frac1{p_n}\\ 2P_n-1 = (2P_{n-1}-1)\left(1-\frac2{p_n}\right)\\ =(2P_{n-2}-1)\left(1-\frac2{p_{n-1}}\right)\left(1-\frac2{p_n}\right)\\ =\left(1-\frac2{p_1}\right)\left(1-\frac2{p_2}\right)\cdots\left(1-\frac2{p_n}\right)$$

If the $p_n$ don't increase too quickly, this product has limit zero, so $P_n\to\frac12$.
For example, if $p_n=n+2$, the product is $$(1-\frac23)(1-\frac24)(1-\frac25)\cdots=\frac13\frac24\frac35\cdots\frac n{n+2}$$ A lot of cancellation happens, leaving $$2P_n-1=\frac2{(n+1)(n+2)}$$ If $p_n=2n+1$, then (check this) $2P_n-1=1/(2n+1)$.
The primes also increase slowly enough that the product approaches zero. Using calculus, you can show that $2P_n-1$ is roughly $C/(\log p_n)^2$ for some constant $C$, so that approaches zero, and $P_n\to1/2$.
On the other hand, suppose $p_n=(n+1)(n+2)$. Then $p_n-2=n^2+3n=n(n+3)$, and the product is $$\left(1-\frac26\right)\left(1-\frac2{12}\right)\left(1-\frac2{20}\right)\cdots=\frac{1\cdot4}{2\cdot3}\frac{2\cdot5}{3\cdot4}\frac{3\cdot6}{4\cdot5}\frac{4\cdot7}{5\cdot6}\cdots$$ A lot of cancellation happens again, and the final product is $1/3$, so $P_n\to(1+1/3)/2=\frac23$.

EDIT
Back to $p_n=n^{th}$ prime.
When $x$ is small, $\ln(1-x)\approx -x$. So for large $n$, $$\ln(2P_n-1)=\sum_{k=1}^n\ln(1-\frac2{p_k})\approx A + \sum_{k=1}^n \frac{-2}{p_k}=A-2\sum_{k=1}^n\frac1{p_k}$$ where $A$ is the accumulated difference between $\ln(1-2/p_k)$ and $-2/p_k$ for small $k$.
The sum is only over prime $p_k$. Near $x=p_k$, roughly one number in $\ln p_k$ is prime. So this sum is roughly $$\ln(2P_n-1)\approx A - 2\sum_{x=3}^{p_n}\frac1x\frac1{\ln x}\\ \approx A-2\int_3^{p_n}\frac1{x\ln x}dx=B-2\ln\ln{p_n}\\ 2P_n-1\approx\frac {e^B}{(\ln x)^2}$$

Answer 4

I'll try to make the proof work for the 12 class.

Fix some $N$, e.g. $N=2018$.

Let $p_k,q_k$ with sum $=1$ be the (complementary) probability weight for H, resp. T for the $k$.th coin, $1=p_k+q_k$. Without any present connection to the given problem, let $x=(x_1,\dots,x_n)$, $y=(y_1,\dots,y_n)$, be variables, and introduce the homogeneous polynomial in these variables $$ \boxed{\qquad P(x,y)= \Big(\ p_1x_1+q_1y_1\ \Big) \cdot \Big(\ p_2x_2+q_2y_2\ \Big) \cdot\dots\cdot \Big(\ p_Nx_N+q_Ny_N\ \Big)\ . \qquad} $$ Now we expand it, getting many (exactly $2^N$) monomials in $x,y$ of total degree $N$. Each monomial is translated as a possible outcome of an $N$-coin tosses with our coins, where

• the occurence of an $x_k$ in the monomial translates as an H at $k$.th toss, and
• the occurence of an $y_k$ in the monomial translates as a T at $k$.th toss.

The coefficient of each such monomial is the probability to the one corresponding result.

We isolate easily the part of $P$ having a total even $x$-degree, it is $$ Q(x,y)=\frac 12\Big(\ P(x,y)+P(-x,y)\ \Big)\ , $$ where $-x=-(x_1,\dots,x_n):=(-x_1,\dots,-x_n)$.

So the wanted probability is, using the notation $\underline 1=(1,1,\dots,1)$, $$ \begin{aligned} Q(\underline 1, \underline 1) &= \frac 12\Big(\ P(\underline 1,\underline 1)+P(-\underline 1,\underline 1)\ \Big) \\ &= \frac 12\prod_{1\le k\le N}\underbrace{(p_k+q_k)}_{=1} -\frac 12\prod_{1\le k\le N}(p_k-q_k) \\ &= \frac 12 -\frac 12\prod_{1\le k\le N}(p_k-q_k) \ . \end{aligned} $$ Now we can split into cases.

(A) We have $p_1=q_1$, so the first factor in the above product vanishes, the whole product vanishes, we get $$\frac 12\ .$$

(B) The second term is no longer zero. The (sign adjusted) product has a huge number of subunitary factors (taken in modulus), this is the reason for getting a "small deviation". Pari/GP gives for instance for $N=2018$, resp. $N=2019$:

gp > 1./2. - 1./2. * prod( n=2, 2018, 2./prime(n) - 1 )
%4 = 0.5043508097943704655075452211

gp > 1./2. - 1./2. * prod( n=2, 2019, 2./prime(n) - 1 )
%5 = 0.4956496854882061604205676533

(C) If some coin (e.g. the first coin) is fair, the result does not depend on $N$, the probability is $1/2$, fair chance. Else there is a "small error" from the fair play, the sign can be predicted from the parity of $N$, assuming $p_k<q_k$ for all $k$.