A Sample Space Reducing (SSR) process is a stochastic process
whose sample space reduces as it evolves in time.
In its simplest version, imagine a set of N states in a system,
labelled by i = 1, 2, ... , N.
The states are ordered by the label.
The only rule that defines the SSR process is that transitions
between states may only occur from higher to lower labels.
This means that transition from state j to i is possible only
if label j > i. When the lowest state i = 1 is reached,
the process is restarted.
This simple dynamics leads to a Zipf’s law in the frequency
of state visits, i.e. the probability to visit state i is given
by p(i) = 1/i (with a slope corresponding to the red straight
line in the plot below with circles).
This scaling law is extremely robust and occurs for a wide class
of prior probabilities.
[
PNAS 112, 5348–5353, (2015)
]
