tag:blogger.com,1999:blog-4115025577315673827.post4608937943338224492..comments2018-09-20T15:33:47.048+05:30Comments on CSE Blog - quant, math, computer science puzzles: Consecutive HeadsPratik Poddarnoreply@blogger.comBlogger23125tag:blogger.com,1999:blog-4115025577315673827.post-58840413815230773612017-04-01T21:43:50.520+05:302017-04-01T21:43:50.520+05:30I have exactly the same cincernI have exactly the same cincernSwati Kawatrahttps://www.blogger.com/profile/13229370445887098422noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-91941697006627278672017-04-01T21:43:25.790+05:302017-04-01T21:43:25.790+05:30I have exactly the same doubt with the solutionI have exactly the same doubt with the solutionUnknownhttps://www.blogger.com/profile/13229370445887098422noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-19189605048109454152014-08-29T17:22:25.614+05:302014-08-29T17:22:25.614+05:30Pratik .. can you give a detailed explaination for...Pratik .. can you give a detailed explaination for all the 3 sub questions? ADITYA P.https://www.blogger.com/profile/05362276501444300572noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86186413263169737322013-02-22T15:06:55.925+05:302013-02-22T15:06:55.925+05:30In your solution to the 1st part, 2nd recursion is...In your solution to the 1st part, 2nd recursion is as follows:<br />f(1,1) = 1/4[f(0,2) + f(0,0)]<br /><br />Isn't this incorrect? How can you go from f(0,2) to f(1,1) in a single step?<br /><br />Shouldn't the correct expression for f(1,1) be: f(1,1) = 1/4[f(0,0)], as you can only be on a (1,1) state if you were previously on (0,0) state and both A&B got heads?Manuhttps://www.blogger.com/profile/12608424690861013659noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-6168241933621381232012-06-20T02:43:26.141+05:302012-06-20T02:43:26.141+05:30My bad , In fact it turns out to be that n1+n1 (by...My bad , In fact it turns out to be that n1+n1 (by chera) is indeed valid and can be substituted back into the recursion to prove n1 is infinitedontevenbotherhttps://www.blogger.com/profile/13451012657610194784noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-19400210941403959422012-06-19T23:33:00.586+05:302012-06-19T23:33:00.586+05:30I disagree with the comment posted by chera . In m...I disagree with the comment posted by chera . In my opinion the recursive equation to solve this would be :F(n) = F(n-1) + 1/2(1) + 1/2(1+F(n+1))<br />where F(n) represents expected number of toss to get n more heads than tails.<br />I am uncomfortable with the notion of adding "n1+n1" , because the the expected function need not be linear , getting two more heads (after a tail) does not mean getting one more head twice<br />or f(n+1) != f(n) + f(1) or f(1) + f(n)<br />I have not solved the recursion thoughdontevenbotherhttps://www.blogger.com/profile/13451012657610194784noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-30355390640889430432012-05-26T00:08:31.199+05:302012-05-26T00:08:31.199+05:30"every snapshot event is equally likely, maki..."every snapshot event is equally likely, making the equivalent problem holds." - prove it! <br /><br />"Also, the snapshot does NOT depend on the history. Because if the HH (or HHH) happened, it is already happened." - Can you go to (TT, TTT) after (TH, TTT) in one step?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-91902422893532320722012-05-25T21:31:49.703+05:302012-05-25T21:31:49.703+05:30Hello Pratik, thank you for the reply. So I double...Hello Pratik, thank you for the reply. So I double checked my solution. I still believe the answer is 3/11<br /><br />Although my independent assumption is definitely not true, every snapshot event is equally likely, making the equivalent problem holds. Also, the snapshot does NOT depend on the history. Because if the HH (or HHH) happened, it is already happened.<br /><br />Also I rerun the code and the solution almost surely lies in [0.270 - 0.275]<br /><br />If you still don't believe me, you may run the code or tell me where I am wrong in the code :)HanChenhttps://www.blogger.com/profile/00926922790399803490noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-69316956260154862852012-05-25T04:44:43.421+05:302012-05-25T04:44:43.421+05:30Hello HanChen, Thanks for your comment! Your solut...Hello HanChen, Thanks for your comment! Your solution is not correct, precisely because of the assumption that queues' snapshots are independent.<br /><br />If the problem were restated as:<br />A tosses a fair coin twice and B tosses a fair coin thrice. If A gets both heads, he wins. If B gets all three heads, he wins. Else, both play again. What is the expected number of plays? Then, your assumption is correct.<br />But in our case, its not true.<br />A queue snapshot is really dependent on the previous queue snapshot.<br />This is clearly evident from the state diagram solution. <br /><br />You should actually run the monte carlo code again, with the correct problem statement and let us know. <br /><br />Thanks. Hope that helps!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-69923203211347463342012-05-25T00:33:40.580+05:302012-05-25T00:33:40.580+05:30Hello Pratik, I have obsessed with your question 1...Hello Pratik, I have obsessed with your question 1 for a whole day. I think I got the answer: 3/11.<br />My solution is inspired by my matlab code I posted yesterday. As you noticed I used two queues: X (2 bits), and Y (3 bits). The key thing is we do not need to think of the sampling history as a whole array, but only the most recent 2 or 3 bits. Because if there is anything of HH for X or HHH for Y, the experiment will stop earlier and we would not have the chance of keeping doing the experiment after that. At each time, we simply take a snapshot of the two queues and determine it the experiment can be stopped now.<br /><br />Therefore we can use the equivalent problem:<br />There are two bowls. Bowl 1 (corresponding to X) has 4 balls (2^2, 3 black, 1 red) in it. Bowl 2 has 8 balls(2^3, 7 black, 1red) in it. Person A and B draws balls independently from the balls and see who draws the red ball first.<br />The solution is<br />\sum_{i^1}^{\infty} \frac{1}{8} (\frac{7}{8})^{i-1}(\frac{3}{4})^i<br />= 3/11 \approx 0.2727<br />(By the way, the error bond in my post yesterday is actually larger)<br />Clearly think my statement here is not rigorous, specifically because of my independent assumption of the queues' snapshots. However, intuitively it isn't a problem because all events for the queue is equally likely.<br />How do you think?HanChenhttps://www.blogger.com/profile/00926922790399803490noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-41816265585225473532012-05-24T04:05:04.710+05:302012-05-24T04:05:04.710+05:30Hi Pratik, I am doubtful about your solution to th...Hi Pratik, I am doubtful about your solution to the first question. I monte carloed it and get<br />P(X>Y) = 0.2720 +- 0.001<br />while your answer is<br />361/1699 = 0.2125<br /><br />This is the simple matlab code for verification.<br /><br /><br /><br />clear;<br /><br />X = zeros(1,2);<br />Y = zeros(1,3);<br />truecases = 0;<br />mcnum = 1e6;<br /><br />for mc = 1:mcnum,<br /><br />for t = 1: 1e4,<br /> X(1) = X(2);<br /> Y(1) = Y(2); Y(2) = Y(3);<br /> <br /> X(2) = rand(1)>0.5;<br /> Y(3) = rand(1)>0.5;<br /> <br /> if (~all(X)) && ( all(Y) ),<br /> truecases = truecases+1;<br /> break;<br /> elseif all(X),<br /> break;<br /> end<br />end<br /><br />end<br /><br />truecases / mcnumHanChenhttps://www.blogger.com/profile/00926922790399803490noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-13140224288695177652011-06-09T20:51:19.542+05:302011-06-09T20:51:19.542+05:30@SeineRiver
We will always need prod array to ret...@SeineRiver<br /><br />We will always need prod array to return product array. See not other temp array was used.<br /><br />If you don't want to see prod array getting malloced in the method, one can pass prod arry in method.Vipulhttps://www.blogger.com/profile/18123066138041812770noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-10618423502203336472011-06-09T20:01:28.787+05:302011-06-09T20:01:28.787+05:30@Vipul:
int *prod = (int *)malloc(sizeof(int)*n);...@Vipul:<br /><br />int *prod = (int *)malloc(sizeof(int)*n);<br /><br />Doesn't this mean O(n) space complexity?<br /><br />Also, be careful with your memset(prod,1,n);<br /><br />It may not work in the way you think ;) Actually this would fill your array with 16843009, using gcc compiler.SeineRiverhttps://www.blogger.com/profile/04133805255439672427noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-24174253768847353022011-02-20T07:12:01.836+05:302011-02-20T07:12:01.836+05:30The above method can be optimized to work in space...The above method can be optimized to work in space complexity O(1). void productArray(int arr[], int n)<br />{<br /> int i, temp = 1;<br /> <br /> /* Allocate memory for the product array */<br /> int *prod = (int *)malloc(sizeof(int)*n);<br /> <br /> /* Initialize the product array as 1 */<br /> memset(prod,1,n);<br /> <br /> /* In this loop, temp variable contains product of<br /> elements on left side excluding arr[i] */<br /> for(i=0; i=0; i--)<br /> {<br /> prod[i] *= temp;<br /> temp *= arr[i];<br /> }<br /> <br /> /* print the constructed prod array */<br /> for (i=0; i<n; i++)<br /> printf("%d ", prod[i]);<br /> <br /> return;<br />}Vipulhttps://www.blogger.com/profile/18123066138041812770noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-27730905151099097432011-02-06T13:58:17.191+05:302011-02-06T13:58:17.191+05:30Your calculation seems correct.
I have another so...Your calculation seems correct.<br /><br />I have another solution for proving that expected number of tosses for equal number of heads and tails is infinite.<br /><br />Also, intuitively, why is that surprising to you? In the state diagram for n heads, we have n+1 states, but in state diagram of heads=tails, we have infinite states. So, expected value in the second case was "expected" to be larger. Right?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-73912098775705204932011-02-05T21:58:23.549+05:302011-02-05T21:58:23.549+05:30as per above discussion, for any arbitrary n, expe...as per above discussion, for any arbitrary n, expected no. of trials to get n consecutve heads is a finite number.<br /><br />surprisingly expected no. of trials to get heads =tails i.e. HT,TH,HHTHTT etc. is infinite. the same is true if we want no. of heads - no. of tails =n, for any n.<br /><br />proof for the case H-T=1:<br /><br />suppose n1 is expected no. of trials to get H-T=1. then<br /><br />n1=1/2*1+1/2*(1+n1+n1)<br /><br />i.e. n1=1+n1. so n1 is infinite.<br /><br />above equaion is true becoz for the case we get H on first trial, we get term 1/2*1. If we get T on first trial, then note that H-T= -1 after first trial. So incrementally, in later trials, twice we must have H-T=1. thus we get term 1/2*(1+n1+n1).cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-11281568133662010422011-02-02T17:54:01.691+05:302011-02-02T17:54:01.691+05:30:) Dude, Nothing is mixed up. You need to spend so...:) Dude, Nothing is mixed up. You need to spend some time to understand this.<br /><br />"Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently"<br /><br />X>Y succeeds when A reaches 2 "only after" B reaches 3 (as X and Y are number of tosses). So, (0,3) and (1,3) are accepted states and (2,0) (2,1) (2,2) (2,3) are failure states.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-45701885697692442502011-02-01T22:38:05.738+05:302011-02-01T22:38:05.738+05:30I am not really a math buff, but aren't (2,0) ...I am not really a math buff, but aren't (2,0) (2,1) (2,2) accepted states and (0,3) (1,3) (2,3) failure states?!<br />Either I do not get what you wrote down or you have it all mixed up in there?XL-30ESEMhttps://www.blogger.com/profile/03481843376250118187noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-74129358358765818362009-12-07T12:59:55.722+05:302009-12-07T12:59:55.722+05:30@tejasvph...
nice generalization.. Using the metho...@tejasvph...<br />nice generalization.. Using the method to solve 2 and 3 part for a general n, we see that z = 2^(n+1) - 2...<br />thanx..Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-21505213807900422082009-12-06T14:26:06.245+05:302009-12-06T14:26:06.245+05:30Interestingly for n consecutive heads, the expecta...Interestingly for n consecutive heads, the expectation value is 2^(n+1) - 2. Might there be an even more elegant solution? :)tejasvphhttps://www.blogger.com/profile/14026392904050871300noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-69109965489841506432009-11-08T22:57:23.313+05:302009-11-08T22:57:23.313+05:30@Pulkit..
I verified it. I think its correct.. Ca...@Pulkit..<br /><br />I verified it. I think its correct.. Can you point out the mistake..<br /><br />Since I made this solution, there is every possibility of a mistake. Can you show why I am wrong?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-85959929032379673852009-11-08T22:52:47.415+05:302009-11-08T22:52:47.415+05:30I think Pratik the recursive relation for x(n) is ...I think Pratik the recursive relation for x(n) is not correct at all.Pulkithttps://www.blogger.com/profile/08900675841142991831noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-62023640307897225802009-11-08T22:51:58.993+05:302009-11-08T22:51:58.993+05:30I think Pratik you have not done the 1st part corr...I think Pratik you have not done the 1st part correctly. the recursion <br /><br />x(n)=1/2*x(n-1)+1/4*x(n-2) is not correct I thinkPulkithttps://www.blogger.com/profile/08900675841142991831noreply@blogger.com