1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ How is $n_{u,v,r}$ being considered as a random variable? It appears to just be a constant. $\endgroup$
    – Brent Kerby
    Commented Mar 4, 2015 at 14:43
  • $\begingroup$ maybe my question is not very well-formed. $n_{u,v,r}$ is not a constant. the walk is a markov process, with the current state being dependent on a previous state. if we start a random walk from $u$, the walk follows nodes $w_1, w_2, w_3, w_4,$ and $w_5$, where $w_5 = v$. The probability of arriving at $w_5$ from $w_4$ depends on $N_{w_4}$. Similarly for $w_4$, and so on. $\endgroup$
    – berlinoob
    Commented Mar 4, 2015 at 15:12
  • $\begingroup$ So are you assuming that a graph is chosen at random, so that the $N_k$ are random? If so, what distribution are you using? $\endgroup$
    – Brent Kerby
    Commented Mar 4, 2015 at 16:22
  • $\begingroup$ for a chosen $u$, the number of edges $N_k$ is not random, it is equal to the number of edges from $u$ to other nodes. But if you consider any node in the graph, then yes, $N_k$ is random. But the question is about the probability of ending at a node $v$ after starting at a chosen node $u$. Is this different from any other description of random walks on graphs? $\endgroup$
    – berlinoob
    Commented Mar 4, 2015 at 23:51

1 Answer 1

Reset to default
0
$\begingroup$

Isn't the expected value of $n_{u,v,r}/N_{u,r}$ the amount $p_{u,v,r}$ (as $N_{u,r}$ grows) ?

i.e., $E(n_{u,v,r}/N_{u,r}) = p_{u,v,r}$ ?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .