The probability of an ant rarely visiting the points with both coordinates even A point of the lattice $\mathbb{Z}^3$ in $\mathbb{R}^3$ is painted white if at least one of its coordinates is odd. An ant is moving in $\mathbb{R}^3$. 
At each integer time $t$ the ant is
at a point in $\mathbb{Z}^3$ and it chooses one of points in $\mathbb{Z}^3$ at distance $1$ with uniform
probability, and it moves there before time $t + 1$. 
For an integer $n$, denote by $P_n$
the probability that among the previous $n$ integer times the ant was at least $90\%$
of the time at a white point. 
Prove that $P_n$ decreases exponentially with $n$. Can
you compute the rate?
 A: As the coordinates of points in this question can only be distinguished modulo $2$, your question is equivalent to the following one:

Suppose our ant starts in a vertex $v(0)$ of the $H(3, 2)$ Hamming graph (or, equivalently, the edge graph of a cube). At each integer time the ant moves from his current vertex to one of the adjacent ones with uniform probability. Suppose $v(t)$ is the position of ant in the time $t$, $w$ - some fixed vertex. Let's denote $P(t, w, v(0))$ as the probability, that $\frac{|\{0 \leq \tau \leq t|v(\tau) = w\}|}{t} \leq \frac{1}{10}$. Prove, that $\exists \lim_{t \to \infty} (P(t, w, v(0)))^{\frac{1}{t}} = p(w, v(0))$ and find that $p(v, w(0)$.

As $H(3, 2)$ is highly symmetric, the only difference between the ant's position is the ants current distant from $w$, which can be $0$, $1$, $2$ or $3$. Those distances are states of a finite Markov chain with transition matrix:
$$A = \begin{pmatrix}
  0 & \frac{1}{3} & 0 & 0 \\
  1 & 0 & \frac{2}{3} & 0 \\
  0  & \frac{2}{3}  & 0 & 1  \\
  0 & 0 & \frac{1}{3} & 0 
 \end{pmatrix}$$
The stationary distribution of this Markov chain is $\begin{pmatrix} \frac{1}{10} \\
\frac{3}{10}\\
 \frac{3}{10}\\
  \frac{1}{10} 
 \end{pmatrix}$
From that we can conclude, that $\frac{|\{0 \leq \tau \leq t|v(\tau) = w\}|}{t}$ converges almost surely to $\frac{1}{10}$, because of the Theorem C.1 from "Markov Chains and Mixing Times" by David A. Levin, which states:

Suppose $X$ is the set of all states of an irreducible aperiodic finite-state Markov chain $a(t)$, $\pi$ is the stationary distribution of $a(t)$ and $f: X \to \mathbb{R}$ is some arbitrary function. Then $\frac{\sum_{s=0}^t f(a(t))}{t}$ converges almost surely to $\sum{x \in X}f(x)\pi(x)$.

And from that we can conclude that the probability that $\frac{|\{0 \leq \tau \leq t|v(\tau) = w\}|}{t} \leq \frac{1}{10}$ tends to $1$ and as $t \to \infty$. Thus such $p(w, v(0))$ does indeed exist and equals $1$.
