How to uniformly sample vertices from a large graph with given distance from a fixed vertex? Given an undirected graph $G=(V,E)$ and some vertex $v_0\in V$, let $V_k=\{\,v\mid v\in V,d(v_0,v)=k\,\}$ be the set of all vertices with distance $k$ to $v_0$.
How can I quickly draw uniform samples from $V_k$ for a given $k$?  In my case, $G$ is implicitly defined as the state transition graph of some combinatorial puzzle and has about $10^{25}$ vertices with $|V_k|\approx 2.3676^k$, so enumerating the vertices in $V_k$ is not an option.  I am mostly interested in values of $k$ from $30$ to $50$ and would like to draw about $10^6$ samples for every $k$ in this range.
 A: Given the information you've provided here is an approach I think works.
I will extend your notation to have $V_r(v)$ be the set of vertices of exactly distance $r$ from vertex, $v$. For convenience let $N(v)$ be the neighbours of $v$.
We note that for a given vertex, it has 2, 3 or 4 neighbours, which are easily determinable (constant time); i.e. $V_1(v)$ is trivial. We likewise assume that there is some constant cost for calculating $d(v_0, v)$ for all $v$ for which $d(v_0, v) \leq k$.
Assume that we have an efficient algorithm for all distances $\leq i$, we now show how to solve for $i+1$.
The algorithm is easy to explain - we choose some starting vertex $v_s$ uniformly at random from $V_i$. We then find its neighbours, and check their distance from $v_0$. 
Let $C(v_s) = V_{i+1} \bigcap N(v_s)$.
We note that, at least one vertex in $N(v_s)$ must be in $V_{i-1}$. Thus $|C(v_s)| \leq 3$. Then, with probability $\frac{3 - |C(v_s)|}{3}$ we reject $v_s$ and start again. 
Otherwise, we choose a candidate $v_c$ from $C(v)$ uniformly at random: Let $n_c$ be the number of its neighbours which are in $V_i$. Then, we accept $v_c$ with probability $\frac{1}{n_c}$. Otherwise, reject $v_s$ and start again.
Correctness:
Define $I(v) = V_i \bigcap N(v)$.
Then, the probability of accepting a given $v \in V_{i+1}$ in a round is
$$
\sum_{v_s \in I(v)} P[v_s] P[v | v_s]
$$
where $P[v_s]$ is the probability of choosing $v_s$ in $V_i$ and is $1/|V_i|$, and $P[v | v_s]$ is the probability of accepting $v$ given that we chose $v_s$. 
$$
P[v |v_s] = \left(1 - \frac{3 - |C(v_s)|}{3}\right)\frac{1}{|C_v(s)|}\frac{1}{|I(v)|} = \frac{1}{3|I(v)|}
$$
Plugging this back in gives us a probability to accept $v$ of $\frac{1}{3V_i}$. Thus, the probability that an iteration accepts any member of $V_{i+1}$ is $\frac{V_{i+1}}{3V_i}$. Assuming the original poster's estimate that $V_i \approx 2.3676^i$, gives us that the probability an iteration succeeds is approximately $\frac{2.3676}{3}$.
Let the cost of determining neighbours be N, the cost of checking distance bound by $i+1$ be $D_{i+1}$, the cost of drawing from $V_i$ be $T_i$, then a round of the algorithm (which may or may not succeed) costs up to:
$T_i + N + 4*D_{i+1} + N + 4*D_{i+1}$. Unfortunately, this does mean that the cost of this algorithm to generate a single point is still exponential, albeit with a sizable improvement over enumeration, if one desires a small sample. If we assume that we can swallow the $D_i$ values into reasonable sized constants (in particular since the higher $i$ values where it is more costly they are calculated much less frequently than for lower $i$ values), we have an overall expected complexity of $O\left(\left(\frac{3}{2.3676}\right)^{k-1}\right)$.
Since for each $k$ we need to draw a point from a sub-sample, we get lower values of $k$ for free. For $k=30$, this works out to a complexity of about $10^3$, for $k=40$, this is roughly $10^4$, for $k=50$, this is $10^5$.
So determining whether this is feasible for you to sample $10^6$ points will depend on the horsepower you can bring to bear. For $k=50$ (which would give you all $k \leq 50$) it would be on the order of magnitude of $10^{11}$ work.
A: After reading MotiN's nice answer, I have decided to modify his procedure as follows:
Let $N(v)=\{\,w\mid w\in V, v\sim w\,\}$ be the neighborhood of $v$.  Let $d(v,w)$ be the length of the shortest path between $v$ and $w$.
We draw samples from $V_k$ by means of a random walk from $v_0$ with $k$ steps. At each step $i$, we pick a random edge from $v_{i+1}\in N(v_i)\setminus\{v_{i-1}\}$ with $v_1$ picked from $N(v_0)$, i.e. we do not pick the edge we just came from.  Further restrictions can be made (e.g. by means of FSM pruning) to improve the yield.
For each sample $v_k$, we determine all shortest paths to $v_0$ and thus $d(v_0, v_k)$.  If $d(v_0, v_k)=k$, we accept the sample, otherwise we reject it.  The probability of a sample being accepted is the yield $y=P\big(d(v_0, v_k)=k\big)$ which we compute during the sampling process.
For each accepted sample $v_k$, we have a set of shortest paths $S$ leading from $v_0$ to it.  We can use this set to compute the probability $P(v_k)$ of having chosen this sample by summing over all shortest paths to $v_k$:
$$P(v_k)=\sum_{v_0,\dots,v_k\in S}{1\over|N(v_0)|}\prod_{i=1}^{k-1}{1\over|N(v_i)|-1}$$
Using the yield $y$, we can compute the chance $p$ of having chosen $v_k$ from all accepted samples:
$$p=P\big(v_k\mid d(v_0,v_k)=k\big)={P[v_k]\over y}$$
If $|V_k|$ is known, this can be used to compute a bias $b$ for the sample $v_k$
$$b=p\,|V_k|$$
This method allows us to sample vertices from $V_k$ and to compute the bias of each path leading to the sample picked.  While we do not get a uniform sample this way, we can compensate for the bias later on.
