Algorithm tug-of-war

The tug-of-war algorithm can be illustrated as follows: Suppose
that a crowd consists of several groups of varying numbers
of people, and that our goal is to estimate the skew in
the distribution of people to groups. That is, we would like
to estimate SJ(A) for the set {v_i}, where vi is the group
to which the i¡¯th person belongs. We arrange a tug-of-war,
forming two teams by having each group assigned at random
to one of the teams. Equating the displacement of the rope
from its original location with the difference in the sizes of
the two teams, it is shown in [AMS96] that the expected
square of the rope displacement is exactly SJ(A), and that
the variance is reasonably small.