Naslov
Reaching consensus on a connected graph

Autori
Haslegrave, John ; Puljiz, Mate

Izvornik
Journal of applied probability (0021-9002) 54 (2017), 1; 181-198

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Stabilisation time ; random walk ; coupon collector ; voter model

Sažetak
We study a simple random process in which vertices of a connected graph reach consensus through pairwise interactions. We compute outcome probabilities, which do not depend on the graph structure, and consider the expected time until a consensus is reached. In some cases we are able to show that this is minimised by K n . We prove an upper bound for the p=0 case and give a family of graphs which asymptotically achieve this bound. In order to obtain the mean of the waiting time we also study a gambler's ruin process with delays. We give the mean absorption time and prove that it monotonically increases with p∈[0, 1∕2] for symmetric delays.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA