I have the following problem: Let's assume $G$ is a graph with vertices in red or blue colour. There is no limitation on how we connect the vertices, i.e., a red vertex can be connected with either red or blue vertex. The given graph is not a full graph. I perform a random walk on this graph, starting from a randomly selected red vertex. Now, I am interested in what is the probability that after $k$ steps of the random walk I will end up in (any) red vertex? The artcile which I am reading says that this probability is given by the below formula:
$$Pr(\text{end in red after k steps}| \text{start in any red}) = \frac{\sum_{x \in R}\sum_{y \in R}\Pi(x)\Pr(y|x)^k}{\Pi(R)}$$
Where $R$ is the set of all red vertices and $\Pi$ is the distribution. Now, I try to understand why this formula is defined like that. So my understanding of the numerator is that we sum all possible ways to go from a red vertex to another red vertex, i.e., assuming $x$ and $y$ are any two red vertices, we compute probability we are in $x$, multiplied by the probability that in $k$ steps the random walk will go from $x$ to $y$. However, I have a problem to understand what is the role of the denominator here. Can someone help me with that?
It's simply the definition of conditional probability: $$P(A \mid B) = \frac{P(A \cap B)}{P(B)}$$ So on the top you have the probability that the walk starts and ends on a red vertex. On the bottom you have the probability that the walk merely starts on a red vertex, which is exactly what $\Pi(R)$ measures.