tag:blogger.com,1999:blog-4115025577315673827.post6406755734282818612..comments2019-12-04T14:40:09.489+05:30Comments on CSE Blog - quant, math, computer science puzzles: Random Walk around SquarePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-4115025577315673827.post-30649987379181132772010-11-10T23:20:46.380+05:302010-11-10T23:20:46.380+05:30Thanks a lot for the solutions.
@Naval: Thanks or...Thanks a lot for the solutions.<br /><br />@Naval: Thanks or the hard work. Good work!<br /><br />@Ankush: Brilliant solution! Happy_Max!! Thanks for the code simulation as well.<br /><br />@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."Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-6165816761743259762010-11-09T11:48:41.006+05:302010-11-09T11:48:41.006+05:30Lets label the vertices as A,B,C and D in clockwis...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.<br /> <br />Now 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.<br />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. <br /><br />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. <br /><br />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.<br /><br />So answer is 1/3*8 + 2/3*10 = 28/3yashhttps://www.blogger.com/profile/09303331364304094162noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-38676693294539560052010-11-08T13:09:41.035+05:302010-11-08T13:09:41.035+05:30@VG : Your symmetric random walk does not simulate...@VG : Your symmetric random walk does not simulate the given question.<br />Here is a counter eg : <br />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<br />you end up at the origin instead of ending up at +/-4.Ankushhttps://www.blogger.com/profile/09691343611737045503noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-32450489031935914132010-11-08T07:12:56.783+05:302010-11-08T07:12:56.783+05:30i was trying to convert this problem as a standard...i 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 approachVGhttps://www.blogger.com/profile/12530365276921956337noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-67302513167276052762010-11-03T18:21:38.882+05:302010-11-03T18:21:38.882+05:30Out of curiosity , i simulated this experiment in ...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.Ankushhttps://www.blogger.com/profile/09691343611737045503noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-3872950367948124332010-11-03T16:48:57.626+05:302010-11-03T16:48:57.626+05:30I have a solution which gives me 28/3(9.33) steps....I have a solution which gives me 28/3(9.33) steps.<br />I have used the Linearity of Expected Value.<br /><br />Label the vertices A,B,C,D with A as the starting vertex.<br />First I calculate the following two expected path lengths : <br />1)Expected path length from a vertex to its diagonally opposite vertex(eg : Expected Path from A to C)<br />2)Expected path length from a vertex to a GIVEN adjacenet vertex(eg : Expected path length from A to B)<br /><br />1)This is calculated using the definition of expected value,i.e SUM_TO_INF(path_length*probability_of_this_path_length)<br />=(2*(1/2))+(4*(1/4))+(6*(1/8))+(8*(1/16)).... = 4<br /><br />2)For calculating this, i use the previous result<br />From A you can go directly to B in one step with prob 0.5<br />or you can go to D with prob 0.5. Now using the prev result,expected path length from D to B = 4.<br />expected path length from A to B = 0.5*(1)+0.5*(1+4) = 3<br /><br />When you go from A to C, there are three cases : <br />(i)encounter B but NOT D. <br />(ii)encounter D but NOT B. <br />(iii)encounter both B AND D.<br /><br />Calculating the prob of these three events:<br />We calculate (i) and then use this to calculate ii and iii.<br />P(B Only) = P(B Only AND 2 steps) + P(B Only AND 4 steps) + P(B Only AND 6 steps) ..<br />= 1/4 + 1/16 + 1/64 + ...<br />= 1/3 <br />Similarly P(D Only) = 1/3 and P(Both B AND D) = 1-(1/3+1/3)=1/3.<br /><br />Now the final solution using these above results :<br />Any Valid Path must be of the following form :<br />a) Go from A to C .<br />b) Return from C to A.<br />Expected Path Length from A to C = 4.<br />During the return path there are three cases<br />(i)During (a) you encountered ONLY B , p=1/3<br />(ii)During (a) you encountered ONLY D , p=1/3<br />(iii)During (a) you encountered BOTH B AND D , p=1/3<br /> <br />In case i, we have not encountered D yet, so we have to go to D sometime <br />and using the result (2) expected path length from C to D = 3 and then expected <br />path length from D to A = 3<br /><br />Case (ii) is similar to case (i) with expected path length = 3+3.<br /><br />In case (iii) we just have to calculate the expected path length from C to A <br />which is equal to 4. <br /><br />Hence total expected path length = 4 + 1/3(6) + 1/3(6) + 1/3(4) = 28/3 steps.Ankushhttps://www.blogger.com/profile/09691343611737045503noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-68942860574293352722010-11-03T00:45:57.871+05:302010-11-03T00:45:57.871+05:30Working on sid's method the answer comes out t...Working on sid's method the answer comes out to be 9.33<br /><br />Basically did the same, wrote a number of equations and solved them.navalhttps://www.blogger.com/profile/00643183076091075896noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-68065236743892818432010-11-03T00:44:10.668+05:302010-11-03T00:44:10.668+05:30Working on sid's solution I did the following ...Working on sid's solution I did the following :<br /><br />Notation: square is ABCD<br />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.<br /><br />Examples: <br />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.<br /><br />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.<br /><br />Hence E(A) = our required value<br /><br />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.<br /><br />We get the following equations:<br /><br />E(A) = 0.5(1 + E(AB)) + 0.5(1 + E(AB))<br />E(AB) = 0.5(1 + E(ABC)) + 0.5(1 + E(BA))<br />E(ABC) = 0.5(1 + E(ACB)) + 0.5(1 + E(ABCD))<br />E(ABCD) = 0.5(1 + E(ABDC)) + 0.5<br />E(BA) = 0.5(1 + E(AB)) + 0.5(1 + E(ABD))<br />E(ACB) = 0.5(1 + E(ABC)) + 0.5(1 + E(BCA))<br />E(ABDC) = 0.5(1 + E(ABCD)) + 0.5(1 + E(ABCD))<br />E(ABD) = 0.5(1 + E(ABDC)) + 0.5(1 + E(BDA))<br />E(BCA) = 0.5(1 + E(ABCD) + 0.5(1 + E(ACB))<br />E(BDA) = 0.5(1 + E(ABD)) + 0.5(1 + E(ABD))<br /><br />Solving the above equations for E(A), we get the value 9.33<br /><br />Again, a brute force solution, but hope it is correct :)navalhttps://www.blogger.com/profile/00643183076091075896noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-73294557811048108622010-11-01T10:06:20.708+05:302010-11-01T10:06:20.708+05:30sorry the last soln is for when u have to traverse...sorry the last soln is for when u have to traverse all edges and come back to the starting vertexsidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-37717978506268477442010-10-31T23:38:19.919+05:302010-10-31T23:38:19.919+05:30By brute force i got the answer as 12. But I essen...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:<br /><br />Notation: 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<br /><br />So we can calculate:<br />1) (1234B)=(1234D)=3 <br /> (1234C) = 4<br />2) (123A) = 32/5<br /> (123B) = 39/5<br /> (123C) = 36/5<br /> (123D) = 23/5<br />3) (412A) = 48/5<br /> (412B) = 47/5<br /> (412C) = 36/5<br /> (412D) = 39/5<br />4) (12A) = 10<br /> (12B) = 153/15<br /> (12C) = 42/5<br />5) (41B) = 51/5<br /> (41A) = 56/5<br />6) (1A) = 58/5<br /> (1B) = 11<br /><br />and the answer is 1 + (1B) = 12<br />I hope there is a better solution than this.sidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.com