0
$\begingroup$

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.

Suppose that I flip a coin $t$ times. How can I find a generalized formula for the probability that the number of tails I will get will be equivalent to $0$ mod $3$ ?

I have tried my hand at this problem- I believe that the result is related to $t$ mod $6$. I am not able to get a formula that works, other than that.

  • 0
    @AndréNicolas I don't have a working formula- only a hunch that it is related to tmod6.I know enough about complex numbers, yes.2012-10-04

2 Answers 2

2

Let $1$, $\omega$, and $\omega^2$ be the cube roots of unity. So $\omega=e^{2\pi i/3}$. I don't like the letter $t$ in the context you are using it, so will use $n$.

By the Binomial Theorem, we have $(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k.$ Now let $F(x)=(1+x)^n +(1+\omega x)^n+(1+\omega^2 x)^n.$ If we expand, the coefficient of $x^k$ is $\binom{n}{k}(1+\omega^k+\omega^{2k}).$ If $k$ is divisible by $3$, then $1+\omega^k+\omega^{2k}=1+1+ 1=3$. If $k$ is not divisible by $3$, then $1+\omega^k+\omega^{2k}=0$. So $\frac{F(x)}{3}=1+\binom{n}{3}x^3+\binom{n}{6}x^6+\binom{n}{9}x^9+\cdots,$ (finite sum). Put $x=1$. We get $\frac{F(1)}{3}=\frac{(1+1)^n+(1+\omega)^n+(1+\omega^2)^{2n}}{3}=\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\binom{n}{9}+\cdots.$ For the probability, divide by $2^n$. So our probability, simplified a bit, is given by $\frac{1}{3}+\frac{(1+\omega)^n +(1+\omega^2)^n}{3\cdot 2^n}.$

For computation, we will want to fool around with $(1+\omega)^n+(1+\omega^2)^{n}$. Note that $1+\omega$ and $1+\omega^2$ are conjugates. Express $\omega$ in polar form $re^{i\theta}$. It will involve a $60^{\circ}$ angle. Then $(1+\omega)^n+(1+\omega^2)^n =r^n (e^{i n\theta}+e^{-i n\theta})$. That will just be $2r^n \cos(n\theta)$. Can simplify further, getting a "mod" expression, since the cosines cycle.

Another way: Here is a brief sketch of another approach. Let $P_0(n)$ be the probability that the number of tails is congruent to $0$ modulo $3$, and let $P_1(n)$ the probability that the number of tails is congruent to $1$ modulo $3$. For symmetry we should also have a $P_2(n)$, but it can be dispensed with, since it is $1-P_0(n)-P_1(n)$.

We can get recurrences for $P_0(n)$ and $P_1(n)$ in terms of each other. The first is $P_0(n)=\frac{1}{2}P_0(n)+\frac{1}{2}P_2(n-1)=\frac{1}{2}P_0(n-1)+\frac{1}{2}(1-P_0(n-1)-P_1(n-1)).$ This is because in our $n$ tosses, the number of tails is congruent to $0$ mod $3$ if (i) it was congruent to $0$ and we got a head or (ii) it was congruent to $2$ and we got a tail. Similarly, but more simply, $P_1(n)=\frac{1}{2}P_1(n-1)+\frac{1}{2}P_0(n-1).$ We can solve this system of two recurrences by matrix methods. It is more common in undergraduate courses to get from our two first-order recurrences a single second-order linear recurrence for $P_0(n)$. You may have seen methods to deal with these (find roots of characteristic polynomial, $\dots$).

  • 1
    Yes, was obviously in need of coffee.2012-10-04
1

Say the coin comes up tails with probability $p$, heads with probability $q=1-p$. Let $f(x)=(px+q)^t=\sum_{r=0}^t{t\choose r}p^rq^{t-r}x^r$ Then the coefficient of $x^r$ is the probability of exactly $r$ tails in $t$ tosses.

Now let $a$ and $b$ be the nonreal cube roots of 1. It's not hard to show that $1^r+a^r+b^r=3{\rm\ if\ }3\mid r,1^r+a^r+b^r=0{\rm\ else}$ So $f(1)+f(a)+f(b)=1+(pa+q)^t+(pb+q)^t=3\sum_{3\mid r}{t\choose r}p^rq^{t-r}$ tells you the answer to your question is $(1/3)(1+(pa+q)^t+(pb+q)^t)$.