Markov chain: Difference between revisions
mNo edit summary |
(Add more references about applying Markov chains to voting methods) |
||
| Line 5: | Line 5: | ||
Each Markov chain is associated with a stationary (or steady state) distribution, which is a distribution of events so that if an event is chosen at random according to the distribution, then the future event will also come from that distribution. |
Each Markov chain is associated with a stationary (or steady state) distribution, which is a distribution of events so that if an event is chosen at random according to the distribution, then the future event will also come from that distribution. |
||
The [[Keener eigenvector]] and [[Sinkhorn]] voting methods are based on Markov chains, and by calculating the steady state for a particular family of Markov matrices, it's possible to construct a number of [[Smith-efficient]] voting methods.<ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2002-December/008923.html|title=The Copeland/Borda wv hybrid (fwd)|website=Election-methods mailing list archives|date=2002-12-03|last=Simmons|first=F.}}</ref> Due to their construction, these methods give each candidate a score, not just an order of finish. |
The [[Keener eigenvector]] and [[Sinkhorn]] voting methods are based on Markov chains, and by calculating the steady state for a particular family of Markov matrices, it's possible to construct a number of [[Smith-efficient]] voting methods.<ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2002-December/008923.html|title=The Copeland/Borda wv hybrid (fwd)|website=Election-methods mailing list archives|date=2002-12-03|last=Simmons|first=F.}}</ref><ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-May/078240.html|title=Markov chain approaches|website=Election-methods mailing list archives|date=2004-05-15|last=Heitzig|first=J.}}</ref> Due to their construction, these methods give each candidate a score, not just an order of finish. |
||
Some nondeterministic methods can be derandomized by using Markov chains, for instance a semiproportional multi-winner generalization of [[random ballot]].<ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2019-October/002323.html|title=Semiproportional methods 2: derandomizing the obvious|website=Election-methods mailing list archives|date=2019-10-04|last=Munsterhjelm|first=K.}}</ref> |
|||
{{stub}} |
{{stub}} |
||
Latest revision as of 18:46, 12 May 2022
A Markov chain is a statistical process describing a (possibly infinite) sequence of steps where the probability of a state (event) occurring depends only on what event happened last time. Markov chains are usually represented as a probability matrix where denotes the probability that the next step will be in state j given that the current step is in state i.
Each Markov chain is associated with a stationary (or steady state) distribution, which is a distribution of events so that if an event is chosen at random according to the distribution, then the future event will also come from that distribution.
The Keener eigenvector and Sinkhorn voting methods are based on Markov chains, and by calculating the steady state for a particular family of Markov matrices, it's possible to construct a number of Smith-efficient voting methods.[1][2] Due to their construction, these methods give each candidate a score, not just an order of finish.
Some nondeterministic methods can be derandomized by using Markov chains, for instance a semiproportional multi-winner generalization of random ballot.[3]
This page is a stub - please add to it.
References
- ↑ Simmons, F. (2002-12-03). "The Copeland/Borda wv hybrid (fwd)". Election-methods mailing list archives.
- ↑ Heitzig, J. (2004-05-15). "Markov chain approaches". Election-methods mailing list archives.
- ↑ Munsterhjelm, K. (2019-10-04). "Semiproportional methods 2: derandomizing the obvious". Election-methods mailing list archives.