4 ms·
I do not have the time to do this right now, but - as this is a recurrent, finite, state machine, there is a unique stable distribution on states by application
by beagle3 9y ago
I do not have the time to do this right now, but - as this is a recurrent, finite, state machine, there is a unique stable distribution on states by application of the Perron Frobenius theorem[0] to the state transition probability matrix; that stable distribution on states is a strictly positive eigenvector with sum 1 and eigenvalue 1 (and can thus easily[1] be computed from the sparse 23751x23751 transition matrix)
This, is, by the way, somewhat similar to how Google's original PageRank[2] worked: Each page has some "worthiness capital", and at each point in time, it randomly gives one "worthiness coin" to one of the outgoing links. Give each page some starting capital (e.g, 1,000,000 coins), run the game for a very long time, and rank pages by the capital they managed to collect. There is a big difference, though - each page is not equivalent to a person in the 5-person game, but to a state in the 23751-state space; also, PageRank had damping factors, sink escapes, and other changes, but the basic idea is the same, and was actually (at least) 20 years old at the time that Page and Brin applied it to links of the "href" kind.
[0] https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theor...
[1] for a suitable definition of easily.
[2] https://en.wikipedia.org/wiki/PageRank https://en.wikipedia.org/wiki/PageRank