Problem A. 800. (May 2021)

A. 800. In a finite, simple, connected graph \(\displaystyle G\) 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 \(\displaystyle G\) find the probability for each vertex that the game ends with all vertices having the same color as the chosen vertex.

Submitted by Dávid Matolcsi, Budapest

(7 pont)

Deadline expired on June 10, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Először is könnyű látni, hogy 1 valószínűséggel idővel az egész gráf egyszínű lesz.

Minden évben tekinthetem úgy, mintha az elejéről indulna a színezés, és egy csúcs esélye a világuralomra az az összege annak, hogy az ilyen színű csúcsoknak mekkora volt a folyanat kezdetén a valószínűsége, hogy végül az egész gráf ilyen színű lesz.

Nézzük a folyamat kezdetét. Legyen egy \(\displaystyle A\) csúcs színe \(\displaystyle v(A)\) valószínűséggel a végső szín.

Egy csúcs \(\displaystyle 1/n\) valószínűséggel lesz kiválasztva, ekkor ha fokszáma \(\displaystyle d\), akkor \(\displaystyle 1/d\) valószínűséggel színez át minden szomszédos \(\displaystyle A_i\) csúcsot.

A szomszédos \(\displaystyle A_i\) csúcsok is mind \(\displaystyle 1/n\) eséllyel lesznek kiválasztva, és ezután \(\displaystyle q/d_i\) eséllyel színezik át őt.

Ebből azt kapjuk, hogy \(\displaystyle v(A)=v(A)+1/n*1/d*(\sum v(A_i))-1/n*(\sum 1/d_i)*v(A)\), ahol a szummák az \(\displaystyle A\)-val szomszédos \(\displaystyle A_i\) csúcsokon futnak végig.

Vagyis \(\displaystyle (\sum 1/d_i)*v(A)-1/d*(\sum v(A_i))=0\) minden \(\displaystyle A\) csúcsra teljesül.

Könnyű látni, hogy tetszőleges \(\displaystyle \lambda\) érték esetén \(\displaystyle v(A)=\lambda/d\) kielégíti az egyenletrendszert. Mivel a valószínűségek összege 1 kell, hogy legyen, \(\displaystyle \lambda=1/(\sum 1/d)\), azaz a megoldás \(\displaystyle v(A)=1/d/(\sum 1/d)\).

Belátjuk még, hogy más vektor nem elégíti ki az egyenletrendszert.

Ha ugyanis az egyenletrendszernek megoldása lenne a \(\displaystyle w(A_i)\) vektor is, amely nem a fenti alakú, akkor a pozitív \(\displaystyle w(A_i)\) értékek közül kiválasztom azt az \(\displaystyle A_r\)-t, amelyre \(\displaystyle w(A_r)/(1/d_r)\) maximális. Legyen ez az érték \(\displaystyle \mu\), és vegyük a \(\displaystyle \mu/d_i-w(A_i)\) vektort.

Az így lineáris kombinációként kapott vektor is kielégíti az egyenletrendszert, minden koordintája nemnegatív, és az r-hez tartozó koordintája 0, viszont nem maga a \(\displaystyle \mathbf{0}\) vektor, mert \(\displaystyle w\) nem a fenti alakú.

Ilyen vektor azonban nem létezik, mert ahhoz, hogy \(\displaystyle A_r\)-nél 0 legyen és a feltételeknek eleget tegyen, az összes szomszédos csúcsnál is 0-nak kell lennie (mert a koordináták nemnegatívak), és így tovább, mivel a gráf összefüggő, minden csúcson 0-nak kell állnia.

Ezzel ellentmondásra jutottunk, tehát csak a fenti alakú megoldásai vannak az egyenletrendszernek, vagyis a korábban meghatározott valószínűség az egyetlen megoldás.

Statistics:

2 students sent a solution.
7 points:	Fleiner Zsigmond.
4 points:	1 student.

Problems in Mathematics of KöMaL, May 2021