Let $G=(V,E)$ be a random undirected, unweighted graph where each vertex $v\in V$ has degree $n>1.$ Let the $k$-sphere $S(v_0,k)=\{\,v\mid v\in V,\;d(v,v_0)=k\,\}$ of $v_0$ be the set of vertices at distance $k$ from $v_0$.
How can we estimate the sphere size as $k$ grows? Initially, $|S(v_0,k)|\approx n(n-1)^{k-1}\ll|V|$ as the neighbors of each vertex in the sphere, except for the one that leads back to $v_0$ are unlikely to be part of $S(v_0,0)\cup S(v_0,1)\cup\cdots\cup S(v_0,k-1)$. But as $k$ grows, this probability becomes higher and it's hard for me to estimate how this continues.
I am interested in this problem as a part of studying the distribution of vertices in the search spaces of combinatorial puzzles, such as sliding-tile puzzles or the Rubik's Cube.