Consider a random walk on a directed graph $G$, where every node has the same in-degree and out-degree $d$. As usual, the probability that the walker moves from node $i$ to node $j$ is $0$ if they are not adjacent, and $\frac{1}{d}$ if they are. A simple cycle of length $n$ is a sequence of nodes $c_1,\dots,c_n,c_{n+1}=c_1$, where $c_i\neq c_j$ for $i,j=1,\dots,n$, $i\neq j$.
What is the probability that the first simple cycle that the walker completes is of length $k$?