Let $G$ be an infinite $d$-regular graph. Consider a symmetric simple random walk on $G$. For each $g \in G$, let $p(n, g)$ be the probability that an $n$-step random walk (starting at some arbitrary vertex in $G$) ends up at $g$. Can we find an upper bound for $p(n,g)$ only in terms of $n$ (or perhaps also $d$)?
I know how to solve this problem for $\mathbb{Z}$. If the random walk starts at the origin, then there are $\binom{n}{(n+g)/2}$ paths with $n$ steps starting with $0$ and ending at $g \in \mathbb{Z}$ (assuming $n+g$ even). So the probability that a $n$-step random walk starting at $0$ ends up at $g$ is $$ 2^{-n} \binom{n}{(n+g)/2} . $$ This quantity is largest when $g = 0$, in which case the estimate $\binom{n}{(n+g)/2} \approx 2^n / \sqrt{\pi n / 2}$ implies that the probability we want is at most $$ \frac{1}{\sqrt{n}} \sqrt{ \frac{2}{\pi} } \approx \frac{0.8}{\sqrt{n}}.$$
Since $\mathbb{Z}$ is the only infinite 2-regular graph, this answers the question for $d = 2$. What about larger $d$?
I feel like probably due to symmetry, it's always "most likely" to end up back where we started after $n$ steps. So we should be looking for "very recurrent" random walks for the worst case. Is $\mathbb{Z}$ the worst case, and therefore is $p(n,g)$ just $\frac{0.8}{\sqrt{n}}$?