Consider random walks of fixed length (e.g. $5$) starting at node $u$ in an undirected and connected graph with $N$ vertices. If a node $k$ has $N_k$ edges, the probability of the walk reaching any of the neighbors is $1/N_k$. The walk proceeds like this until it has traversed a fixed number of nodes. The probability of a length-$r$ random walk starting at $u$ ending at $v$ is denoted by $p_{u,v,r}$, and the number of walks that start at $u$ and end at $v$ is denoted by $n_{u,v,r}$. The total number of walks starting at $u$ is $N_{u,r}$.
I would like to calculate the Expected value and variance of of $n_{u,v,r}$. When $N_{u,r}$ grows, $n_{u,v,r}/N_{u,r}$ is close to $p_{u,v,r}$. Based on these, I would like to calculate the bounds on these values based on the Chernoff's or Hoeffding's inequality. Another question is: which of these inequalities to use. Considering that this is a multi-step walk, I think one should treat it as a Binomial process and use Chernoff's inequality.