Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

True, but I think Grue3's remark is more about the fact that this Markov chain is not irreducible than the number of states being wrong. Because you can go from the state where one person has all the money to the other states but not the other way around.


This doesn't matter all that much -- I think the Markov chain becomes irreducible if you chop off the states in which one person has all the money.


Why would that not matter? If you ignore some states that are possible is that not changing the problem?


In this case, the unreachable states don't partition the space in a meaningful manner, nor does the system start in an unreachable state, so the only effect is that those states occur with probability zero instead of with very low probability in the stationary distribution. There are also very few (N) of those states compared to the total number of states (about N^(2N) if I'm estimating right), so removing them has very little effect on the overall statistics.

For a more interesting example, suppose that on each round, everyone with money picked a random person and gave them 2 dollars (and take N even). Now you'd have a Markov chain that is reducible in a nontrivial manner -- think about the parity constraints.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: