1
$\begingroup$

A connected weighted graph $G(V,E,W)$ is give, where $w_{uv}$ corresponds to the probability to jump from node $u$ to node $v$. Also, a function $l$ maps nodes with positive and negative labels, where $V_+$ are the nodes having positive label (+1) and $V_-$ are the ones having negative label (-1). Assuming to have a random walk starting visiting nodes in the graph (with no assumption about the starting node) is possible to estimate (in expected value) $S$, i.e. the number of steps presenting consecutively same label (positive or negative)?

I'm trying to understand which is the average length of subsequences of having the same label without any assumption on edges distribution (in a random graph configuration).

$\endgroup$
2
  • $\begingroup$ Without any assumptions whatsoever, the expected value is $2$, since if we don't know anything about $V_+$ and $V_-$ and how they interact with the graph and its weights, then each step has a fifty-fifty chance of switching to the other label. I don't think that's the sort of answer you're looking for, though; can you clarify? $\endgroup$ Jun 12, 2020 at 15:52
  • $\begingroup$ Knowing the relative size of the two groups should not help? Anyway knowing adjacency matrix do you think should be possible to get an expected length of subsequence? I'm imagining a matrix where, depending on the seed node (row-i) we then know the expected value $\endgroup$ Jun 12, 2020 at 15:57

1 Answer 1

1
$\begingroup$

If you have the adjacency matrix and want to compute the expected time to stay in $V^-$ (for instance) starting from various vertices in $V^-$, then we first want to simplify the adjacency matrix to get rid of the useless information about $V^+$. We want to work with the $|V^-|$ by $|V^-|$ matrix $A$ where the $(u,v)$ entry is still $w_{uv}$, but only the vertices from $V^-$ are present. (So instead of summing to $1$, row $u$ should sum to the probability that a transition from $u$ leads to another vertex in $V^-$.)

Then if we start with a column vector $\mathbf x$ describing a probability distribution over states in $V^-$ (which could just have probability $1$ on a single state), then $A \mathbf x$ will be a sort-of-probability distribution over the state after one step: it will tell us the probabilities for every next state in $V^-$, but transitions to $V^+$ will just disappear. The sum of the components of $A\mathbf x$, which is $\mathbf 1^{\mathsf T}A\mathbf x$ algebraically, will be the probability of staying in $V^-$ after one step.

More generally, $\mathbf 1^{\mathsf T}A^k \mathbf x$ will give us the probability of staying in $V^-$ after $k$ steps. So if we want to know the total number of vertices we visited in $V^-$ before moving to $V^+$, that's going to be $\mathbf 1^{\mathsf T}(I + A + A^2 + \dots )\mathbf x$, which simplifies to $\mathbf 1^{\mathsf T}(I - A)^{-1}\mathbf x$.

So $\mathbf 1^{\mathsf T}(I - A)^{-1}$ tells you the vector of expected lengths of stays in $V^-$ for all starting vertices in $V^-$. (It counts the starting vertex as well, so if a vertex always transitions to $V^+$, it'll have an expected length of $1$.)

We can do this for both $V^+$ and $V^-$ at the same time if we work with the bigger matrix $$A = \begin{bmatrix}A^- & 0 \\ 0 & A^+\end{bmatrix},$$ where $A^-$ is the $V^- \to V^-$ transition matrix and $A^+$ is the $V^+ \to V^+$ transition matrix. (So we take the adjacency matrix for the graph and wipe out the entries that go from one set to the other.) But this is a block matrix and the inverses $(I - A^-)^{-1}$ and $(I - A^+)^{-1}$ are going to be completely independent, anyway.

$\endgroup$
1
  • $\begingroup$ Great, thank you for the detailed answer. I'm wondering now if there exists some reference about absorbing random walks of different colors (like this where we have a partition of two colors). I would be interested to understand if some relationships exist between the two distinct absorbing random walks, even if independent. $\endgroup$ Jun 14, 2020 at 10:50

You must log in to answer this question.

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