For a regular graph, each walk of a given length has the same probability, so let's just consider the number of walks.

A walk starting and ending at a given vertex is comprised of zero or more pieces that consist of non-trivial walks that return to the start only on their last step. So if $w(x)$ is the ordinary generating function of all walks that end at the starting vertex, and $r(x)$ is the ordinary generating function of the non-trivial walks that first return to the start on the last step, then $$ w(x) = 1 + r(x) + r(x)^2 + \cdots = \frac{1}{1-r(x)},$$ or equivalently $$ r(x) = \frac{w(x)-1}{w(x)}.$$ If you know the coefficients of $w(x)$ (in general the coefficient of $x^j$ is the sum of the $j$-th powers of the eigenvalues of the adjacency matrix, equivalently the trace of the $j$-th power of the adjacency matrix, but there can be easier ways depending on the graph), this lets you get the coefficients of $r(x)$.

Since these generating functions are rational functions (see Didier's answer for a proof), the asymptotics of the probability you want are determined by the smallest (complex) solution of $w(x)=0$.

For a regular graph, each walk of a given length has the same probability, so let's just consider the number of walks.

A walk starting and ending at a given vertex is comprised of zero or more pieces that consist of non-trivial walks that return to the start only on their last step. So if $w(x)$ is the ordinary generating function of all walks that end at the starting vertex, and $r(x)$ is the ordinary generating function of the non-trivial walks that first return to the start on the last step, then $$ w(x) = 1 + r(x) + r(x)^2 + \cdots = \frac{1}{1-r(x)},$$ or equivalently $$ r(x) = \frac{w(x)-1}{w(x)}.$$ If you know the coefficients of $w(x)$, this lets you get the coefficients of $r(x)$.

Since these generating functions are rational functions (see Didier's answer for a proof), the asymptotics of the probability you want are determined by the smallest (complex) solution of $w(x)=0$.

For a regular graph, each walk of a given length has the same probability, so let's just consider the number of walks.

A walk starting and ending at a given vertex is comprised of zero or more pieces that consist of non-trivial walks that return to the start only on their last step. So if $w(x)$ is the ordinary generating function of all walks and $r(x)$ is the ordinary generating function of one piece, then $$ w(x) = 1 + r(x) + r(x)^2 + \cdots = \frac{1}{1-r(x)},$$ or equivalently $$ r(x) = \frac{w(x)-1}{w(x)}.$$ If you know the coefficients of $w(x)$ (in general the coefficient of $x^j$ is the sum of the $j$-th powers of the adjacency matrix, but there can be easier ways depending on the graph), this lets you get the coefficients of $r(x)$.

For a regular graph, each walk of a given length has the same probability, so let's just consider the number of walks.

A walk starting and ending at a given vertex is comprised of zero or more pieces that consist of non-trivial walks that return to the start only on their last step. So if $w(x)$ is the ordinary generating function of all walks that end at the starting vertex, and $r(x)$ is the ordinary generating function of the non-trivial walks that first return to the start on the last step, then $$ w(x) = 1 + r(x) + r(x)^2 + \cdots = \frac{1}{1-r(x)},$$ or equivalently $$ r(x) = \frac{w(x)-1}{w(x)}.$$ If you know the coefficients of $w(x)$ (in general the coefficient of $x^j$ is the sum of the $j$-th powers of the eigenvalues of the adjacency matrix, equivalently the trace of the $j$-th power of the adjacency matrix, but there can be easier ways depending on the graph), this lets you get the coefficients of $r(x)$.

Since these generating functions are rational functions (see Didier's answer for a proof), the asymptotics of the probability you want are determined by the smallest (complex) solution of $w(x)=0$.