Suppose I throw a fair die $1995$ times. What is the probability that the total is divisible by 3?
I tried to attack this problem inductively, storing the total in a variable $t \mod 6$, and then showing that for any total $t$ there is a $1/3$ probability of the next throw of the dice creating a total $t+n$ divisible by three. However, I've had difficulty formalizing the proof and I'm wondering if there isn't a better way to do this.
On
You have a good idea, I think.
The trick is that you don't want a variable $t$: you want a random variable $t$.
More precisely, you want to define the random variable $t_n$ that has the distribution
$P(t_n = a) = $ the probability that the total after $n$ rolls is equivalent to $a$ modulo $6$
(actually, you only need mod $3$, but using $6$ makes the problem no harder)
You know the probability distribution on $t_1$. From there, you can work out, inductively, the probability distribution for $t_{n+1}$ from the probability distribution on $t_n$.
(you can start at $t_0$ instead of $t_1$ if you like)
On
The probability for one dice is $\frac{1}{3}$. For two die, the probaility is $\frac{2+5+4+1}{36}=\frac{1}{3}$. Also, the probability of the total being $1\; \text{mod}\; 3$ is $\frac{3+6+3}{36} = \frac{1}{3}$. I'm going to posit that the probability is $\frac{1}{3}$ that you'll get any one of the three remainders. Now, suppose it's true for $n\leq k $. Then, the probability for $n = k+1$ is simply $(\frac{1}{3})^{2}\cdot 3 = \frac{1}{3}$.
On
Here is a solution using generating functions. Suppose we roll the die $n$ times, then the generating function of the totals is $$f(z) = (z+z^2+z^3+z^4+z^5+z^6)^n.$$ Now put $$w = e^{2\pi i/3}$$ then it is not difficult to see that the generating function of those terms whose exponents are divisible by three is given by $$g(z) = \frac{1}{3} (f(wz)+f(w^2z)+f(w^3z)).$$ The count that we are interested in is given by $g(1),$ which is $$\frac{1}{3} \left( (w+w^2+w^3+w+w^2+w^3)^n \\+ (w^2+w+w^3+w^2+w+w^3)^n \\+ (w^3+w^3+w^3+w^3+w^3+w^3)^n \right).$$ Now observe that $w^3=1$ and $$w+w^2+w^3 = w (1+w+w^2) = w \frac{w^3-1}{w-1} = 0,$$ and therefore $$g(1) = \frac{1}{3} 6^n.$$ The desired probability is thus $$\frac{g(1)}{f(1)} = \frac{1}{3} \frac{6^n}{6^n} = \frac{1}{3}.$$
Let $X_n$ be the $n$th number rolled by a fair die (modulo $3$) and let $S_n = X_1 + \ldots + X_n \pmod 3$ be the sum of the first $n$ numbers modulo $3$. We will prove by induction on $n \in \mathbb N$ that for any $r \in \{0,1,2\}$, we have that $P(S_n = r) = 1/3$. The base case is clear; we will focus on the induction step.
Induction Hypothesis: Assume that the claim holds true for $n = k$.
It remains to prove that the claim holds true for $n=k+1$. Indeed, for any $r \in \{0,1,2\}$, observe that: \begin{align*} &P(S_{k+1} = r) \\ &= P(S_k = 0)P(X_{k+1} = r) + P(S_k = 1)P(X_{k+1} = r-1) + P(S_k = 2)P(X_{k+1} = r-2) \\ &= P(S_k = 0)\cdot\frac{1}{3} + P(S_k = 1)\cdot\frac{1}{3} + P(S_k = 2)\cdot\frac{1}{3} \\ &= \frac{1}{3}\cdot\frac{1}{3} + \frac{1}{3}\cdot\frac{1}{3} + \frac{1}{3}\cdot\frac{1}{3} \qquad\text{by the induction hypothesis}\\ &= 3\left(\frac{1}{3^2}\right)\\ &= \frac{1}{3}\\ \end{align*} as desired. Note that $r-1$ and $r-2$ are taken modulo $3$.