Random Walk around Square
Source: Placement Test of a Quant Company at IITB in 2010
Problem: Consider a random walk around the edges of a square. From any vertex, the probability of moving to any adjacent vertex is 0.5. Suppose the walk stops as soon as after all traversing through all the vertices, you return to your starting vertex. What is the expected path length?
Update (Nov 10, 2010):
Solution:
1) First solution posted by Naval Chopra (Final year student, CSE, IIT Bombay) in comments!
2) A more elegant solution posted by Ankush Agarwal (Third Year undergraduate student, CSE, IIT Bombay) in comments! He has also posted a mathematica code for verifying his solution :)
3) A similar solution posted by Yash in comments (with a minor typo though)
Thanks a lot for the active participation!
Problem: Consider a random walk around the edges of a square. From any vertex, the probability of moving to any adjacent vertex is 0.5. Suppose the walk stops as soon as after all traversing through all the vertices, you return to your starting vertex. What is the expected path length?
Update (Nov 10, 2010):
Solution:
1) First solution posted by Naval Chopra (Final year student, CSE, IIT Bombay) in comments!
2) A more elegant solution posted by Ankush Agarwal (Third Year undergraduate student, CSE, IIT Bombay) in comments! He has also posted a mathematica code for verifying his solution :)
3) A similar solution posted by Yash in comments (with a minor typo though)
Thanks a lot for the active participation!
By brute force i got the answer as 12. But I essentially calculated all the path lengths that are possible. The method is as follows:
ReplyDeleteNotation: square is ABCD. and sides are numberes 1234 for AB,BC,CD and DA respectively. Denote (123B) = expected no of steps required for the person who is at vertex B and has already covered sides 1,2 and 3 to visit all vertices and end at A. Similar notation for others
So we can calculate:
1) (1234B)=(1234D)=3
(1234C) = 4
2) (123A) = 32/5
(123B) = 39/5
(123C) = 36/5
(123D) = 23/5
3) (412A) = 48/5
(412B) = 47/5
(412C) = 36/5
(412D) = 39/5
4) (12A) = 10
(12B) = 153/15
(12C) = 42/5
5) (41B) = 51/5
(41A) = 56/5
6) (1A) = 58/5
(1B) = 11
and the answer is 1 + (1B) = 12
I hope there is a better solution than this.
sorry the last soln is for when u have to traverse all edges and come back to the starting vertex
ReplyDeleteWorking on sid's solution I did the following :
ReplyDeleteNotation: square is ABCD
E(ABC) = expected number of steps required for the person who is at vertex C and has already covered vertices A,B to visit all the vertices and end at A.
Examples:
E(ABDC) = expected number of steps required for the person who is at vertex C and has already covered vertices A,B,D to reach A.
E(ACB) = expected number of steps required for the person who is at vertex B and has already covered vertices A,C to visit all the vertices and end at A.
Hence E(A) = our required value
Also by symmetry, D can be interchanged with B. Hence, E(AB) = E(AD), E(ABC) = E(ADC), E(ACB) = E(ACD), E(ACDB) = E(ABCD), and so on.
We get the following equations:
E(A) = 0.5(1 + E(AB)) + 0.5(1 + E(AB))
E(AB) = 0.5(1 + E(ABC)) + 0.5(1 + E(BA))
E(ABC) = 0.5(1 + E(ACB)) + 0.5(1 + E(ABCD))
E(ABCD) = 0.5(1 + E(ABDC)) + 0.5
E(BA) = 0.5(1 + E(AB)) + 0.5(1 + E(ABD))
E(ACB) = 0.5(1 + E(ABC)) + 0.5(1 + E(BCA))
E(ABDC) = 0.5(1 + E(ABCD)) + 0.5(1 + E(ABCD))
E(ABD) = 0.5(1 + E(ABDC)) + 0.5(1 + E(BDA))
E(BCA) = 0.5(1 + E(ABCD) + 0.5(1 + E(ACB))
E(BDA) = 0.5(1 + E(ABD)) + 0.5(1 + E(ABD))
Solving the above equations for E(A), we get the value 9.33
Again, a brute force solution, but hope it is correct :)
Working on sid's method the answer comes out to be 9.33
ReplyDeleteBasically did the same, wrote a number of equations and solved them.
I have a solution which gives me 28/3(9.33) steps.
ReplyDeleteI have used the Linearity of Expected Value.
Label the vertices A,B,C,D with A as the starting vertex.
First I calculate the following two expected path lengths :
1)Expected path length from a vertex to its diagonally opposite vertex(eg : Expected Path from A to C)
2)Expected path length from a vertex to a GIVEN adjacenet vertex(eg : Expected path length from A to B)
1)This is calculated using the definition of expected value,i.e SUM_TO_INF(path_length*probability_of_this_path_length)
=(2*(1/2))+(4*(1/4))+(6*(1/8))+(8*(1/16)).... = 4
2)For calculating this, i use the previous result
From A you can go directly to B in one step with prob 0.5
or you can go to D with prob 0.5. Now using the prev result,expected path length from D to B = 4.
expected path length from A to B = 0.5*(1)+0.5*(1+4) = 3
When you go from A to C, there are three cases :
(i)encounter B but NOT D.
(ii)encounter D but NOT B.
(iii)encounter both B AND D.
Calculating the prob of these three events:
We calculate (i) and then use this to calculate ii and iii.
P(B Only) = P(B Only AND 2 steps) + P(B Only AND 4 steps) + P(B Only AND 6 steps) ..
= 1/4 + 1/16 + 1/64 + ...
= 1/3
Similarly P(D Only) = 1/3 and P(Both B AND D) = 1-(1/3+1/3)=1/3.
Now the final solution using these above results :
Any Valid Path must be of the following form :
a) Go from A to C .
b) Return from C to A.
Expected Path Length from A to C = 4.
During the return path there are three cases
(i)During (a) you encountered ONLY B , p=1/3
(ii)During (a) you encountered ONLY D , p=1/3
(iii)During (a) you encountered BOTH B AND D , p=1/3
In case i, we have not encountered D yet, so we have to go to D sometime
and using the result (2) expected path length from C to D = 3 and then expected
path length from D to A = 3
Case (ii) is similar to case (i) with expected path length = 3+3.
In case (iii) we just have to calculate the expected path length from C to A
which is equal to 4.
Hence total expected path length = 4 + 1/3(6) + 1/3(6) + 1/3(4) = 28/3 steps.
Out of curiosity , i simulated this experiment in Mathematica.(Code is available : goo.gl/7DkzN ). I ran this experiment 1000,10000,100000,1000000 times and in each case caclulated the mean of the path length for the respective number of runs. The resuts were : 9.62,9.45,9.33,9.31 respectively.
ReplyDeletei was trying to convert this problem as a standard symmetric random walk.. starting from 0, moving clockwise is +1 and moving anticlockwise is -1.. aim is to reach 4 or -4.. however i didn't get 28/3(which is the right ans ,source: WQ examiner). Can sum1 tell whats wrong in this approach
ReplyDelete@VG : Your symmetric random walk does not simulate the given question.
ReplyDeleteHere is a counter eg :
You can complete the random walk in the given question by the following 6 steps(c=clockwise,ac=anti-c) : c,c,a,a,a,c. If you follow the same steps for your model 1,1,-1,-1,-1,1
you end up at the origin instead of ending up at +/-4.
Lets label the vertices as A,B,C and D in clockwise fashion. Now lets calculate the expected path to move from A to B or A to C. Lets assume it to be x. Now x = 0.5*1 + 0.5*(2+x). This is because there is a 0.5 probability of directly moving to B or 0.5 probability of moving to C. If you move to C, then one will either go back to A or to D. In either case, the path length so far is 2 and now we again simply need to move to the adjacent vertex. So total path length in this case will be 2+x. Solving this equation we get x=3.
ReplyDeleteNow lets calculate the probability of moving to opposite vertex. This will simply be 1+x because first move will be to either B or D and then we simply need to move to an adjacent vertex. So this will be 4.
Now we need to calculate the probability that all 4 points were covered while moving from A to C or not. First move from A will be either to B or to D. Now lets take the B case. I will define a probability y that trying to reach from B to C covers D as well. Now from B there is 0.5 probability that I move directly to C thus D is not covered. The other 0.25 probability is that I end up at D via A and 0.25 probability that I am back to B via A again. SO the equation will be y = 0.5*0 + 0.25*1 + 0.25*y. This gives me y as 1/3.
Now we can easily calculate the path length. 1/3 is the probability that we ended up at C having covered all the vertices. So we simply need to go back to A now.So total path length will be 4+4 = 8.
2/3 is the probability that we reached C and need to cover either B or D. The expected path length for that is x=3. And once we reach B we again need to go back to A, for which again the expected path length is x=3. So total path length is 4+3+3 = 10.
So answer is 1/3*8 + 2/3*10 = 28/3
Thanks a lot for the solutions.
ReplyDelete@Naval: Thanks or the hard work. Good work!
@Ankush: Brilliant solution! Happy_Max!! Thanks for the code simulation as well.
@Yash: Thanks for the solution. Your solution is same as Ankush's. There is one minor typo though: The second line should be "Now lets calculate the expected path to move from A to B or A to D." instead of "Now lets calculate the expected path to move from A to B or A to C."