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).
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.