There are many ways we can define in statistics good estimators for a model, like the mean or variance. However, instead of relying on authority and tradition to provide such estimators it would be useful to have a principled approach.
Hence, we are going to have a look at the maximum likelihood estimation, which is a very commonly used principle to derive the sought after estimators.
Let’s start by examining $m$ independent samples $\mathbb{X} = \{\x^{(1)}...\x^{(m)}\}$ from a distribution $\pdata$, where the latter is actually not known. Then, we can write down the model distribution as:
where $\THETA$ is a parameter over the family of probability distributions $\pmodel{\x}$. Then the maximum likelihood estimator for $\THETA$ is defined as:
Please note, that working with the product $\prod$ is for a variety of reasons rather inconvenient. Hence, let’s transform it into a sum $\sum$ by taking the logarithm:
This works because applying the logarithm does not change the $\argmax$ for $\THETA$. We can continue transforming by dividing by $m$, which also has no effect on the $\argmax$ for $\THETA$:
Summarized: So, by maximizing the expectation $\mathbb{E}$ over the logarithm of our model distribution $p_\text{model}$ for the given samples ${\x} \sim {\hat{p}_\text{data}}$ and with respect to the parameter $\THETA$, we tend to end up with good estimators.
Let’s assume you are watching a soccer game in a very large stadium built for such an event. Further, let’s assume that the capacity of the stadium is about one hundred thousand people. So the population $\mathcal{P}$ has a size of:
Now, let’s give the game a twist and ascribe to the spectators a dislike for centralized decision making: They’ll reflect such distaste equally in the soccer game and prefer to not have a referee. Or rather, they have restricted the power of the referee to not being able to issue a yellow or a red card upon a foul.
So, what happens when there is a situation where a player engages another player unfairly, but where it is not so clear if the situation deserves a yellow or a red punishment? The referee cannot issue a decision because otherwise the spectators would rip him apart for transgressing his powers.
So, they themselves have to decide: But the decision should be made almost unanimously, otherwise it does not count. To enable all of the $100'000$ people to converge quickly to the same conclusion, everybody agrees to the following consensus rules:
Upon an unfair behavior make an individual decision if the culprit deserves a yellow or a red punishment and then raise your card, such that it is easily visible for everybody else.
Then take a random sample of $n$ people among the other fellow spectators in the stadium and change your own card according to the majority of those people you have chosen; but stick to your card if there is a tie.
Iterate the second step until the whole (or almost whole) stadium displays the same color.
where each $p_i\hat\in{\mathcal{P}}$ denotes a random selection of $p_i$ from the population $\mathcal{P}$ according to the uniform distribution, i.e. probability $\mathbb{P}(p_i) = 1\big/|\mathcal{P}|$ for each $p_i\in{\mathcal{P}}$.
Summarized: People keep influencing each other, until everybody hopefully converges onto the same opinion.
There is now a very interesting question that needs to be clarified:
How many rounds does it usually take to reach consensus, i.e. until almost the whole stadium displays either $red$ or $yellow$ cards?
We have answered this question by running multiple simulations of the whole process as described above, and found that the number of rounds required to reach consensus is dependent on:
the total population $|\mathcal{P}|$, where the larger it gets the more rounds need to be iterated, and also on
the number of people randomly sampled in each round i.e. $|\mathbb{S}_{color}^{(r)}(p)|$, where for larger sample sizes fewer rounds need to be iterated.
The simulation is using the term avalanche, since the change of opinions is reminiscent of an avalanche, where the higher the percentage of people (in a given round $r$) thinking for example that a foul should be punished with red, the higher the probability of people changing their opinion from yellow to red (in the next round $r+1$).
Aggregate over $1'000$ simulations for $|\mathcal{P}|=100'000$: ¶
$|\mathcal{P}|=10^5$: Consensus for sample sizes $|\mathbb{S}|\in{[2..10]}$ and $rounds\in{[1..13]}$
For a population of $100'000$ people consensus can be achieved within $13$ rounds, where it is reached faster when more fellow spectators are taken into consideration: A sample size of $|\mathbb{S}|=8$ (or more) seems to produce average and median consensus levels very close to $100\%$ with a tiny standard deviation, while having reasonably low amounts of outliers.
$|\mathcal{P}|=10^5$: Consensus for sample sizes $|\mathbb{S}|\in{[2..10]}$ and $rounds\in{[1..13]}$
The same simulation data shown here as histograms yields overall the same results as above with the box plots.
Aggregate over $1'000$ simulations for $|\mathcal{P}|=1'000'000$: ¶
$|\mathcal{P}|=10^6$: Consensus for sample sizes $|\mathbb{S}|\in{[2..10]}$ and $rounds\in{[1..13]}$
One may expect, that by drastically increasing the population size by an order to $|\mathcal{P}|=1'000'000$ people, a similar increase of the sample size and rounds would be required, however that does not seem to be the case: While there is a small decrease in consensus, it is almost not perceptible (for the same sample size of $8$ and same number of rounds of $13$). However, the number of outliers seems to increase while still being reasonable.
$|\mathcal{P}|=10^6$: Consensus for sample sizes $|\mathbb{S}|\in{[2..10]}$ and $rounds\in{[1..13]}$
Again, using histograms for the visualization of the same simulations for a population of one million leads to the same conclusions as above with the box plots.
The overall approach of using the model of an avalanche seems to be an efficient process of generating consensus among a very large population. While there seems to be an engineering trade-off between a lower sample size and a higher number of rounds, sampling $8$ or more fellow spectators over $13$ rounds seems to be a good choice, given a population of $100'000$ people. Also, these parameters can be applied to a much larger crowd of one million people without almost any significant decrease in consensus.
Simulates for the provided population size $|\mathcal{P}|$, maximum sample size $|\mathbb{S}|$ and maximum number of rounds the avalanche process:
#!/usr/bin/env python
from typing import Dict
from numpy.random import choice
from numpy.random import randint
from numpy import array
from numpy import maximum
from numpy import round
from numpy import zeros
from matplotlib import pyplot as pp
import argparse
import json
import numpy
import sys
defavalanche(
population_size: int, max_sample: int, max_round: int
) -> array:
"""
Simulates for the provided number of `max_round`, the given
`population_size` and `max_sample` the *avalanche* process,
where we keep the `population_size` fixed, but consider all
sample sizes from `1` until `max_sample` (inclusive); then
return a matrix (array) `m` for each round and sample size.
While technically it is not required to use the matrix `m`,
and rely *only* on the array `p` (to successfully simulate
the avalanche process), it is used for book-keeping helping
later-on to generate plots of the entire process.
"""
m = zeros(shape=(max_round, max_sample))
for s in range(max_sample):
p = population(size=population_size)
for r in range(max_round):
m[r, s] = p.sum() / population_size
p = resample(p, s + 1)
return m
defpopulation(size: int) -> array:
"""
Returns a uniformly sampled population for the given `size`
where a value of `0` represents *yellow* and a value of `1`
*red* cards.
"""
return randint(0, 2, size=size)
defresample(p: array, size: int) -> array:
"""
Make a random choice of a sample `size` (from a given array
`p`) for *each* element within the array `p`. Then for each
sample calculate, if the majority of the sample indicates a
*red* (i.e. `1`) or a *yellow* (i.e. `0`) card. However, if
there is *no* majority (i.e. a tie) within the sample, then
do nothing.
Note that the returned array has the same size as the array
`p`: It represents a state update of `p`, where elements of
the array have switched their "opinion" with respect to the
majority they have sampled.
"""
parser = argparse.ArgumentParser(
description='Produces the Avalanche Matrix ''[rounds x max.sample-size]')
parser.add_argument('-p', '--population',
type=int, help='population size ''(default: %(default)s)', default=100000)
parser.add_argument('-r', '--max-round',
type=int, help='maximum number of rounds ''(default: %(default)s)', default=13)
parser.add_argument('-s', '--max-sample',
type=int, help='maximum sample size ''(default: %(default)s)', default=10)
args = parser.parse_args()
m = avalanche(
args.population, args.max_sample, args.max_round)
numpy.savetxt(
sys.stdout, m, header=json.dumps(vars(args)))
Running a single simulation for the population size of $|\mathcal{P}|=100'000$ people yields the matrix below, where the rows display the rounds in the range of $[1..13]$ and the columns iterate over the sample sizes of $[1..10]$:
