Probability in connected graph
Source:
July 25, 2021
probabilityProbabilistic Methodcombinatorics
Problem Statement
In a finite, simple, connected graph we play the following game: initially we color all the vertices with a different color. In each step we choose a vertex randomly (with uniform distribution), and then choose one of its neighbors randomly (also with uniform distribution), and color it to the the same color as the originally chosen vertex (if the two chosen vertices already have the same color, we do nothing). The game ends when all the vertices have the same color.Knowing graph find the probability for each vertex that the game ends with all vertices having the same color as the chosen vertex.