Markov Chains: Discussion

Discussion

This is a place for questions, answers and discussion.

You can ask a question or comment with your real name, or anonymously by entering any nickname. Email address is optional. I will endeavour to answer questions.

Comments (14)

Logging you in...

Dashboard | Edit profile | Logout

Logged in as

+1 Vote up Vote down

Richard Weber 35p · 652 weeks ago

Apologies to "tf" the person who made a first comment - I had to reinstall the comment system on this page as it was not working properly.

+1 Vote up Vote down

Anony · 651 weeks ago

In Example 2.2 (Random walk on a tetrahedron), the eigenvalues of a 4x4 symmetric matrix P were given as 1, -1/3, -1/3, -1/3. Is there a fast way to calculate the final three eigenvalues?

1 reply · active 651 weeks ago

+1 Vote up Vote down

Richard Weber 35p · 651 weeks ago

Perhaps this? Maybe someone can find something more slick.

Let J be a 4x4 matrix of all 1s. Clearly, J has a set of linearly independent eigenvectors of (1,1,1,1), (-1,1,0,0), (-1,0,1,0),(-1,0,0,1), with eigenvalues of 4, 0, 0 ,0, respectively.

P = (1/3)(J-I), where I is the identity matrix. So any eigenvector of J is also an eigenvector of P. Hence the three eigenvectors of J with e-value 0, are eigenvectors of P with eigenvalue -1/3.

Clearly, this also works for a random walk on K_n (the complete graph on n vertices).

+1 Vote up Vote down

Vl@d · 650 weeks ago

Sorry, I'm just wondering, in the 'new' proof of Thm 4.2, in the first line (k_i ^A=...), shouldn't the probability be multiplied by 't'? It seems to be fine after we switch to E_i, but I was wondering whether we should have a 't' multiplied in the eqn's until then.
I also believe there is a 'P' missing in the first line, before (H^A...|X_ 1=j)... Hope I'm not mistaking.

1 reply · active 650 weeks ago

+1 Vote up Vote down

Richard Weber 35p · 650 weeks ago

You are correct about P missing. I will correct. Thanks.

There is no need for a t. We are using the idea that for a random variable Y taking values 1, 2, ... we can compute EY as sum_{t=1}^infty P(Y >= t).

+1 Vote up Vote down

Tadek Krassowski · 649 weeks ago

Question 15 on the example sheet states a theorem about recurrence of random walks on a graph and its subgraph. Could you recommend me some source which contains a proof of this theorem?

1 reply · active 649 weeks ago

+2 Vote up Vote down

Richard Weber 35p · 649 weeks ago

This topic is not in the schedules for our course. But it is certainly very interesting and if you would like to learn about it then I recommend the references mentioned on the course page. In particular, this result is discussed in Peter Doyle and Laurie Snell "Random walks and electric networks", 2006 (freely available to download from the link I give on the course information page). The result follows from the fact that cutting a link in an electrical networks of resistors increases the resistance between any two points. I will say a bit more about this in Lecture 12.

0 Vote up Vote down

Vl@d · 648 weeks ago

If γ_i^k is the expected number of hits on 'i' between successive hits on 'k', then I was wondering if γ_k is the same as γ^k and what they actually mean.

3 replies · active 648 weeks ago

+1 Vote up Vote down

Richard Weber 35p · 648 weeks ago

γ^k would be the vector whose components are γ_i^k (i in I)

If γ_k appears anywhere it is probably a misprint. Where did you see it?

0 Vote up Vote down

Vl@d · 648 weeks ago

γ_k appears on the blog on lecture 8.
Thank you for clarifying that for me!

+1 Vote up Vote down

Richard Weber 35p · 648 weeks ago

Thanks. I have corrected it to γ^k

0 Vote up Vote down

anon · 638 weeks ago

I've just been reading section 12.3 and it states "until the game ends the teacher gives out at least 1 gumdrop per round". Doesn't an initial configuration of (16 8 4) for example show this needn't necessarily be the case? While the statement to be proved is true in this case anyway, could there potentially be loops in which the teacher is not giving out gumdrops but the algorithm has yet to terminate in the more general case?

0 Vote up Vote down

JonnyTheStambledOne · 636 weeks ago

Well, this is my problem!
Few months ago I have stumbled upon some Markov chains. Last summer, I have red some interesting thing about it to. In high school I have red some things about it to.
My problem was when I analyzed the game of few people with the ball, each people have the probaliliti that will pass the ball to other person.
I got idea about multiple balls, and what if the game stoped if two balls are at one person, and also you could have the scenarion in witch U can have more balls in one person.
It could be the case that there is math developed for this, but I just dont know abut it....
If somebody know any thing about those subjects that I have mentioned above, I enurage it to writte to m;e...pleas..
ok it could be used in modeling Internet, servers, roads and so on....

1 reply · active 634 weeks ago

0 Vote up Vote down

anonymous · 634 weeks ago

Sound's like you want mixing times and information on coupling, eg. a google search for 'markov chains mixing times' throws this up:
http://www.manu-ao.ac.nz/massey/fms/Colleges/Coll...

Post a new comment

Comment as a Guest, or login:

Tweet this comment

Discussion

Forgot password?

Comments (14)

Post a new comment