Discrete incremental voting on expanders

Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of k distinct opinions, and at each step a random vertex alters its opinion to that of a randomly chosen neighbour until the system reaches a state where each vertex holds the same opinion. In general the opinions of the vertices in pull voting are regarded as incommensurate, whereas we consider a type of pull voting, which we call discrete incremental voting, suitable for moving towards consensus on integer opinions such as {1,2,…,<i>k}</i>. On observing the opinion of a random neighbour, the vertex updates its opinion by a discrete change in the direction of the neighbour's opinion, if different. In the simplest case, the vertex increases its opinion by +1 if the opinion of the chosen neighbour is larger, or decreases its opinion by −1, if the opinion of the neighbour is smaller. If initially there are only two adjacent integer opinions, incremental voting coincides with pull voting, whereas if there are more than two opinions this is not the case. Let <i>G=(V,E)</i> be a connected non-bipartite n-vertex graph, and let λ be the absolute second eigenvalue of the transition matrix P of a simple random walk on G with stationary distribution π=(π _v) _v∈V. Let the initial opinions of the vertices be chosen from {1,2,…,k}, let X _v be the initial opinion of vertex v, and let c=∑ _v∈Vπ _vX _v be the initial weighted average opinion. We show that provided λk=<i>o</i>(1) and k=<i>o</i>(<i>n</i>/log⁡<i>n</i>) the following holds with high probability. If<i> c</i> is integer then the final opinion is <i>c</i>. Otherwise the final opinion is ⌊<i>c</i>⌋ with probability ⌈<i>c</i>⌉−<i>c</i>, and ⌈<i>c</i>⌉ with probability 1−(⌈<i>c</i>⌉−<i>c</i>). In particular if <i>G </i>is a regular graph, and <i>c</i> is the initial unweighted average opinion, then with high probability the final opinion held by all vertices is either ⌊<i>c</i>⌋ or ⌈<i>c</i>⌉, the rounded values of the initial average.