Question: Consider n independent tosses of a $k$-sided fair dice. Let $X_i$ be the number of tosses that result in $i$.
What is the covariance $\mathrm{cov}(X_1,X_2)$ of $X_1$ and $X_2$.
\begin{align} \mathrm{cov}(X_1,X_2) = \mathbf{E}[X_1X_2] - \mathbf{E}[X_1]\mathbf{E}[X_2] \end{align}
I get a different $\mathbf{E}[X_1X_2]$ than the given solution.
The solution given is
Let $A_t$ (respectively, $B_t$) be a Bernoulli random variabe that is equal to 1 if and only if the $t$th toss resulted in 1 (respectively, 2). We have E$[A_tB_t] = 0$ (since $A_t \neq 0$ implies $B_t \neq 0$)
$$ \mathbf{E}[A_tB_s] = \mathbf{E}[A_t]\mathbf{E}[B_t] = \frac{1}{k} \cdot \frac{1}{k} \mathrm{for}\ s \neq t.$$
Thus,
\begin{align} \mathbf{E}[X_1X_2] &= \mathbf{E}[(A_1+\cdots + A_n)(B_1+\cdots B_n)]\\ &=n\mathbf{E}[A_1(B_1+\cdots+B_n)] = n(n-1)\cdot \frac{1}{k} \cdot \frac{1}{k} \\ &= \frac{n(n-1)}{k^2} \end{align}
and
My solution that gives slightly off answer
My approach uses iterated expectations. \begin{align} \mathbf{E}[X_1X_2] = \mathbf{E}[\mathbf{E}[X_1X_2|X2]] \end{align} If I had $k$ instead of $k-1$ in the following equation, I would get an answer identical to given solution but if I already know $X_2=x_2$ then dice tosses should be identically distributed among k-1 remaining options, right? \begin{align} \mathbf{E}[X_1|X_2=x_2] = \frac{n-x_2}{k-1} \end{align}
Then \begin{align} \mathbf{E}[X_1X_2|X_2] = \frac{n-X_2}{k-1} \cdot X_2 \end{align} \begin{align} \mathbf{E}[\mathbf{E}[X_1X_2|X_2]] = \mathbf{E}[\frac{nX_2-{X_2}^2}{k-1}] \end{align}
given $\mathbf{E}[{X_2}^2] = \mathbf{E}[{X_2}] = \frac{n}{k}$
\begin{align} \mathbf{E}[X_1X_2] = \frac{n(n-1)}{k(k-1)} \end{align}
So my answer differs to the solution on the matter of $\mathbf{E}[X_1X_2]$
\begin{align} \mathbf{E}[X_1X_2] = \frac{n(n-1)}{k^2} \neq \frac{n(n-1)}{k(k-1)} \end{align} Whats wrong with my logic? Or maybe MIT is wrong.
Unfortunately it turns out MIT was right and I was wrong.
Thanks to the help from JeanMarie I was able to come up with the following derivation.
\begin{align} \mathbf{E}[{X_2}^2] &= \mathrm{var}(\mathbf{E}[{X_2}^2]) + \mathbf{E}[X_2]^2 \\ \mathrm{var}(\mathbf{E}[{X_2}^2]) &= \frac{n(k-1)}{k^2} \\ \mathbf{E}[X_2]^2 &= \big(\frac{n}{k}\big)^2 \\ \mathbf{E}[{X_2}^2] &= \frac{n(k-1)}{k^2} + \frac{n^2}{k^2} \\ &= \frac{n^2+n(k-1)}{k^2} \end{align}
Following from where my own solution left off, bunch of algebra.
\begin{align} \mathbf{E}[X_1X_2] &= \mathbf{E}[\frac{nX_2-{X_2}^2}{k-1}] \\ &= \frac{1}{k-1}\big(n \cdot \frac{n}{k} - \frac{n^2+n(k-1)}{k^2}\big) \\ &= \frac{1}{k-1} \big( \frac{n^2k}{k^2} - \frac{n^2}{k^2}\big) - \frac{n}{k^2} \\ &= \frac{n^2}{k^2} - \frac{n}{k^2} \\ &= \frac{n(n-1)}{k^2} \end{align}
Which agrees with the MIT solution.