tag:blogger.com,1999:blog-8890204.post342639137580044130..comments2023-03-21T09:40:10.543-04:00Comments on My Biased Coin: Voting and Anti-VotingMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-8890204.post-43257280907255830792008-03-05T10:14:00.000-05:002008-03-05T10:14:00.000-05:00It is very difficult to study Markov chain topic. ...It is very difficult to study Markov chain topic. Not many good reference textbooks to study Markov chain.<BR/><BR/>I use <A HREF="http://www.cocomartini.com/rainyland/product_info.php?products_id=390" REL="nofollow"><STRONG>Markov Chains and Stochastic Stability</STRONG></A> to study. This is good reference textbook.<BR/><BR/>Do you have any other good Markov Chains related textbooks recommend?<BR/><BR/>Regards,<BR/><BR/>AndyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-67026218018747440102008-03-03T21:28:00.000-05:002008-03-03T21:28:00.000-05:00Cool reference! Thanks!Cool reference! Thanks!Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-8447426792435511372008-03-03T21:13:00.000-05:002008-03-03T21:13:00.000-05:00As for question 1 about the hardness of computing ...As for question 1 about the hardness of computing the probability of absorption in a general graph G, it turns out that there is a simple solution. An exposition can be found in Chapter 2 of <A HREF="http://www.math.unl.edu/~shartke2/math/exposition.php" REL="nofollow"> this thesis</A>.<BR/><BR/>The main idea is to consider the system of random walks on G induced by looking at where each vertex last got its label. <BR/><BR/>The end result is that the probability of being absorbed in the all-zeros state is equal to the degrees of all the vertices initially set to zero divided by the sum of the degrees of all the vertices in G.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-19861478245330169362008-03-03T20:37:00.000-05:002008-03-03T20:37:00.000-05:00The recurrences I found are:p_k = n/(n+1) p_{k+1} ...The recurrences I found are:<BR/><BR/>p_k = n/(n+1) p_{k+1} + 1/(n+1) q_k<BR/>q_k = n/(n+1) q_{k-1} + 1/(n+1) p_kAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-43322114891287959872008-03-03T19:30:00.000-05:002008-03-03T19:30:00.000-05:00What is the recurrence that you are getting? I'm g...What is the recurrence that you are getting? I'm getting p_k = (n-k)/n*(p_{k+1} + 1/(n+1)*q_k)<BR/>and q_k = k/n*(q_{k-1}+1/(n+1)*p_k), so I can't see how you obtain p_k + q_{k+1} = q_k + p_{k+1}?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-23181109377353575502008-03-03T16:01:00.000-05:002008-03-03T16:01:00.000-05:00Oops. I misinterpreted the model. I had each rando...Oops. I misinterpreted the model. I had each randomly selected vertex imposing its label on one of its neighbours instead of vice versa which I guess is more of a contagion model than a voter model.<BR/><BR/>The recurrences are different in this case, but the key observation (i.e.: p_k + q_{k+1} = q_k + p_{k+1}) somehow remains the same. The correct recurrences give p_k = (n+k)/(2n) and q_k = k/(2n) in a star graph with n+1 nodes, which agrees with Randy Cogill's result.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-74625709183963390082008-02-29T21:15:00.000-05:002008-02-29T21:15:00.000-05:00Given a star graph with n+1 nodes (it makes the no...Given a star graph with n+1 nodes (it makes the notation better with n+1), with the center node labelled 1 and k of the other nodes labelled 0, the probability of reaching the all-zero state is kn/(n^2+1). Also, if the center node is labelled 0 and k of the other nodes are labelled 0, the probability of reaching the all-zero state is (kn+1)/(n^2+1).<BR/><BR/>Method: Let (k,1) denote the state where the center node is labelled 1 and k of the other nodes are labelled 0. Similiarly denote (k,0). Let p_k denote the probability of reaching (n,0) from (k,0). Similarly, let q_k denote the probability of reaching (n,0) from (k,1). Note that p_n = 1 and q_0 = 0.<BR/><BR/>After establishing the relevant recurrences in the usual way, the key manipulation is to obtain the identity: p_k + q_{k+1} = q_k + p_{k+1} for all k. The rest follows.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-36883461284095472912008-02-26T22:21:00.000-05:002008-02-26T22:21:00.000-05:00I couldn't help but take a stab at this. For voter...I couldn't help but take a stab at this. For voter model question #2, it turns out that the probability of reaching the all zero state from the given initial state is always 1/2, regardless of the value of n. My solution is a bit of a mess, but I'd be happy to share the details if anyone is interested.<BR/><BR/>I agree with you, though. Nothing is more fun than easily stated, not so easily solved Markov chain problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-9145930968857196022008-02-26T00:08:00.000-05:002008-02-26T00:08:00.000-05:00the closest i know of such problems are in the "ev...the closest i know of such problems are in the "evolutionary dynamics on graphs" papers by martin nowak. basically, 0 = cooperators, 1 = defectors; you start with an initial configuration in a population, run the dynamics much like you proposed, and try to compute the "fixation probability."<BR/><BR/>see: http://www.fas.harvard.edu/~ped/people/faculty/all_publications.html<BR/><BR/>A simple rule for the evolution of cooperation on graphs and social networks.Anonymousnoreply@blogger.com