Get Stochastic Transitivity essential facts below. View Videos or join the Stochastic Transitivity discussion. Add Stochastic Transitivity to your PopFlock.com topic list for future reference or share this resource on social media.
Stochastic transitivity models are stochastic versions of the transitivity property of binary relations studied in mathematics. Several models of stochastic transitivity exist and have been used to describe the probabilities involved in experiments of paired comparisons, specifically in scenarios where transitivity is expected, however, empirical observations of the binary relation is probabilistic. For example, players' skills in a sport might be expected to be transitive, i.e. "if player A is better than B and B is better than C, then player A must be better than C"; however, in any given match, a weaker player might still end up winning with a positive probability. Tighly matched players might have a higher chance of observing this inversion while players with large differences in their skills might only see these inversions happen seldomly. Stochastic transitivity models formalize such relations between the probabilities (e.g. of an outcome of a match) and the underlying transitive relation (e.g. the skills of the players).
A binary relation on a set is called transitive, in the standard non-stochastic sense, if
for all members of .
Stochastic versions include of transitivity include:
Weak Stochastic Transitivity (WST): and implies , for all ;:12:43rg
Strong Stochastic Transitivity (SST): and implies , for all ;:12
Linear Stochastic Transitivity (LST):, for all , where is some increasing and symmetric[clarify] function (called a comparison function), and is some mapping from the set of alternatives to the real line (called a merit function).
A toy example
The marble game - Assume two kids, Billy and Gabriela, collect marbles. Billy collects blue marbles and Gabriela green marbles. When they get together they play a game where they mix all their marbles in a bag and sample one randomly. If the sampled marble is green, then Gabriela wins and if it is blue then Billy wins. If is the number of blue marbles and is the number of green marbles in the bag, then the probability of Billy winning against Gabriela is
In this example, the marble game satisfies linear stochastic transitivity, where the comparison function is given by and the merit function is given by , where is the number of marbles of the player. This game happens to be an example of a Bradley-Terry model.
Ranking and Rating - Stochastic transitivity models have been used as the basis of several ranking and rating methods. Examples include the Elo-Rating system used in chess, go, and other classical sports as well as Microsoft's TrueSkill used for the Xbox gaming platform.
Machine Learning and Artificial Intelligence (see Learn to Rank) - While Elo and TrueSkill relly on specific LST models, machine learning models have been developed to rank without prior knowledge of the underlying stochastic transitivity model or under weaker than usual assumptions on the stochastic transitivity. Learning from paired comparisons is also of interest since it allows for AI agents to learn the underlying preferences of other agents.
Game Theory - Fairness of random knockout tournaments is strongly dependent on the underlying stochastic transitivity model. Social choice theory also has foundations that depend on stochastic transitivity models.
Connections between models
Every model that satisfies Linear Stochastic Transitivity must also satisfy Strong Stochastic Transitivity, which in turn must satisfy Weak Stochastic Transitivity. This is represented as: LST SSTWST ;
Since the Bradeley-Terry models and the Thurstanian model 5[clarify] are LST models, they also satisfy SST and WST;
Two LST models given by invertible comparison functions and are equivalent[clarify] if and only if for some 
Stochastic transitivity models are empirically unverifiable[clarify], however, they may be falsifiable;
Distinguishing[clarify] between LST comparison functions and can be impossible even if an infinite amount of data is provided over a finite number of points[clarify];
The estimation problem[clarify] for WST, SST and LST models are in general NP-Hard,  however, near optimal polynomially computable estimation procedures are known for SST and LST models.
^Cavagnaro, Daniel R.; Davis-Stober, Clintin P. (2014). "Transitive in our preferences, but transitive in different ways: An analysis of choice variability". Decision. 1 (2): 102-122. doi:10.1037/dec0000011. ISSN2325-9973.