= Solution
The chain is a random walk on the finite abelian group $(\mathbb Z/n\mathbb Z)^d$, so its stationary distribution is uniform and its characters diagonalize the transition operator. For one coordinate and $\theta=2\pi k/n$, the eigenvalue is
$$
\lambda_{p}(\theta)=\frac12+
rac p2e^{i\theta}+
rac{1-p}{2}e^{-i\theta}.
$$
Uniformly in $p\in[0,1]$,
$$
|\lambda_p(\theta)|^2
\leq1-c\min\left\{\frac{k^2}{n^2},1\right\}
$$
for an absolute $c>0$. Hence the one-coordinate chi-squared distance after $t\geq n^2$ is at most $Ce^{-ct/n^2}$. The coordinates evolve independently, so the product formula for chi-squared distance gives
$$
1+\chi^2_d(t)
=\prod_{j=1}^d(1+\chi^2_j(t))
\leq\exp\left(Cd e^{-ct/n^2}\right).
$$
The <chi-squared divergence> bound on <total variation distance> now yields
$$
\boxed{t_{\mathrm{mix}}=O(n^2\log(d+1)),}
$$
uniformly in $p_1,\ldots,p_d$.
For $d=1$, the first nonconstant character has eigenvalue modulus $1-O(n^{-2})$, uniformly in $p$. Testing against its real or imaginary part gives a fixed positive total-variation distance until time $cn^2$. Thus
$$
\boxed{t_{\mathrm{mix}}=\Theta(n^2)\quad(d=1).}
$$
Back to article page
