Threshold behaviour of discordant voting on the complete graph

Abstract Given a connected graph G whose vertices are coloured in some way, a discordant voting process on G is as follows. At each step a pair of adjacent vertices with different colours interact, and one of the vertices changes its colour to match the other one. If eventually all vertices have the same colour, we say a consensus has been reached. A vertex is discordant if it has a discordant edge, i.e. a neighbour of a different colour. In the general discordant voting process, at each step a discordant vertex u is chosen uniformly at random, and then a discordant edge ( u , v ) is chosen from among the discordant edges of u , also uniformly at random. With probability β vertex u adopts the colour of vertex v and with probability 1 − β vertex v adopts the colour of vertex u . Let T be the number of steps needed to reach consensus. For the complete graph K n with an initial colouring where half the vertices are red and half blue, then when β = 0 , E T = Θ ( n log ⁡ n ) , whereas when β = 1 then E T = Θ ( 2 n ) . The case β = 1 / 2 corresponds to a simple random walk on a path with vertex set { 0 , 1 , . . . , n } and has E T = n 2 / 4 . We study the effect of varying β from zero to one, thus revealing the detailed transition from E T = Θ ( n log ⁡ n ) to E T = Θ ( 2 n ) . In terms of β , the transition from Θ ( n log ⁡ n ) to Θ ( n 2 ) occurs in a scaling window of width O ( 1 / n ) around β = 1 / 2 . For any a > 1 , there is an explicit value of β = 1 / 2 + O ( log ⁡ n / n ) for which E T = Θ ( n a ) . When β > 1 / 2 constant, there is an explicit value a ( β ) such that E T = Θ ( a n ) .