tag:blogger.com,1999:blog-4115025577315673827.post6464113678974409243..comments2020-07-30T14:44:21.349+05:30Comments on CSE Blog - quant, math, computer science puzzles: Equal Heads and TailPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-4115025577315673827.post-52574328598180178392013-10-05T18:37:41.655+05:302013-10-05T18:37:41.655+05:30@chera , How did you get the total number of ways ...@chera , How did you get the total number of ways for 2k trials ?Gupthttps://www.blogger.com/profile/06985035164770943409noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-88153839939148138132011-09-04T12:10:40.229+05:302011-09-04T12:10:40.229+05:30@Sumit, we also have to ensure that in first 2r t...@Sumit, we also have to ensure that in first 2r trials H never equals T, where r<k.<br /><br /> If there are 2k trials, total number of ways will be 2C(k-1) where C(n)= binomial(2n,n)/(n+1) is well known as catalan number.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-89301899105256158452011-09-03T23:06:53.686+05:302011-09-03T23:06:53.686+05:30The probability that if we had 2k trials, we'l...The probability that if we had 2k trials, we'll have equal heads and tails:<br />\binomial(2k,k)*2^(-2k)<br /><br />Therefore, expected value is<br />\sum_{K=1}^{K=\infty} 2k*\binomial(2k,k)*2^(-2k)Anonymoushttps://www.blogger.com/profile/00094235259094340406noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-10149530655042763722011-02-10T12:49:41.282+05:302011-02-10T12:49:41.282+05:30A (standard) generating function approach. Let P(x...A (standard) generating function approach. Let P(x) = sum_{n=0}^{\infty} p_n x^n where p_n is the probability that the walk returns to origin in 2n steps. note that p_0 = 1. Similarly, let Q(x) = sum_0^{\infty} q_n x^n where q_n is the probability that the walk returns to the origin for the first time in 2n steps. Note that q_0 = 0. Then, <br /><br />p_n = \sum_{k=1}^{n} q_k p_{n-k}<br /><br />The convolution suggests going to the generating function domain where this equation becomes P(x) - 1 = P(x)Q(x) or Q(x) = 1-(1/P(x)). Its easy to see that p_n = binomial(2n,n)(pq)^n. The generating function for the central binomial coefficient is 1/sqrt(1-4x). So Q(x) becomes 1-sqrt(1-4pqx). Q(1) gives the probability of return at some point to the origin and can be seen to equal 1-|p-q|. So probability of the walk escaping to infinity is |p-q|. If the walk isn't symmetric, then immediately the expected time of first return in infinite. If p=q, the expected time of first return is the derivative of 1-\sqrt{1-x} at x=1 which is again infinite. By extracting coefficients out of Q(x) using binomial series, we can compute q_n as well.Dinesh Krithivasanhttps://www.blogger.com/profile/13437484936096983201noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-78083233648917825542011-02-10T10:57:52.265+05:302011-02-10T10:57:52.265+05:30@pratik, To solve the recurrence find the value of...@pratik, To solve the recurrence find the value of E(d) in terms of the E(d+1). It turns out to be<br /><br />E(d) = d + d/(d+1) * E(d+1)<br /><br />This can be done using induction. If we plugin this to find the value of E we get,<br /><br />E = d + 1/d * E(d)<br /><br />This result is true for any d > 1 and can be proved via induction.AAhttps://www.blogger.com/profile/15052240248744955514noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-46309120284968274332011-02-10T02:19:23.692+05:302011-02-10T02:19:23.692+05:30Edit to my first post:
This is a problem involving...Edit to my first post:<br />This is a problem involving catalan numbers..(http://en.wikipedia.org/wiki/Catalan_number)<br />I think my earlier expression for expectation is most probably correct. <br /><br />earlier poster makes no mention of the expectation which is what the question asks for.<br /><br />This expectation is infinite and can also be explained as a direct consequence of the optional stopping theorem<br />(http://en.wikipedia.org/wiki/Optional_stopping_theorem)Sivahttps://www.blogger.com/profile/12469392360597269559noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-5129859075177910042011-02-10T02:09:49.341+05:302011-02-10T02:09:49.341+05:30a solution for finding probability that eventually...a solution for finding probability that eventually heads=tails in case of a biased coin.<br /><br />consider a random walk with probability p of moving right and 1-p of moving left. u start at origin O. assume wlog that p<1/2. suppose the probability that eventually u return to origin is x. there are two possibilities:<br /><br />Event E1: first step is towards right. In this case,we can assume that certainly u will return to origin as p<1/2. so probability(E1)=p.<br /><br />Event E2: first step is towards left to point A, and u return to origin O after crossing A n times. <br />probability (E2 for a fixed n)=(1-p)(p)(x-p)^n. <br /><br />hence x= probability(E1)+probability (E2)<br />i.e. x=p+ sigma (1-p)(p)(x-p)^n.<br />where sigma is from n=0 to infinity.<br /><br />on summation of geometric series and simplification, we get quadratic equation<br />(x-1)(x-2p)=0.<br /><br />so x=2p ignoring x=1.<br /><br />as we assumed p<1/2,<br />general solution is x= 2 min(p,1-p)cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-8422944288176095552011-02-10T01:39:58.697+05:302011-02-10T01:39:58.697+05:30Yes of course.. I take my comment back... I missed...Yes of course.. I take my comment back... I missed a factor of 2. <br />so instead of 2*min(p,1-p) I wrote min(p,1-p) which led to to the wrong answer. I wish I could edit my post.Sivahttps://www.blogger.com/profile/12469392360597269559noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-24007423736866358922011-02-09T23:55:24.640+05:302011-02-09T23:55:24.640+05:30@chera.. Thanks a ton!
@Siva.. I take my statement...@chera.. Thanks a ton!<br />@Siva.. I take my statement about your comment back. Your probability is not correct, and hence your solution (both the calculation and the approach) is wrong!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-29484933027920315832011-02-09T23:18:57.589+05:302011-02-09T23:18:57.589+05:30the probability that eventually H=T is one,i.e. al...the probability that eventually H=T is one,i.e. almost certain. <br /><br />and in a general case of biased coin, where the probability of head is p, probability that eventually H=T is 2*min(p,1-p).<br /><br />Proof is available at math.stackexchange.com/questions/17999/1d-random-walk-probability-to-go-back-to-origin.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-41936543526568319412011-02-09T20:16:37.867+05:302011-02-09T20:16:37.867+05:30@kalyan.. Sorry. Got my formula for stirling appro...@kalyan.. Sorry. Got my formula for stirling approximation wrong. You are correct! It diverges as T_n->n^(-.5)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-74770285998666095872011-02-09T19:03:16.027+05:302011-02-09T19:03:16.027+05:30@kalyan.. Yes, it diverges. But I think T_n->n^...@kalyan.. Yes, it diverges. But I think T_n->n^(0.5) and not n^(-0.5). Please check if I am wrong!<br /><br />@abhash.. very interesting approach..<br /><br />Let E(d) be the expected number of tosses required to get equal number of heads and tails when the current difference between their counts is d.<br /><br />E(d)= 0.5(1+E(d+1)) + 0.5(1+E(d-1)) for d>1<br />i.e. <br /><br />E(d) = 1 + 0.5*(E(d-1)+E(d+1)) for d>1<br />i.e.<br />E(d-1)=2*E(d)-E(d+1)-1 for d>1<br />and E(1) = 1+0.5*E(2)<br />E(0)=0<br /><br />We need to find the value of E: E=0.5(1+E(1))*2=1+E(1)<br /><br />@abhash: How did you solve this recurrence?<br /><br />@Siva.. Please check kalyan's solution! Your expression is not correct! Your argument, though is correct!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-88694998804415266802011-02-09T10:53:14.361+05:302011-02-09T10:53:14.361+05:30This is a problem involving catalan numbers..
E(x...This is a problem involving catalan numbers..<br /><br />E(x) = 2*sum 2n*C(2n-2)* 1/2^2n which is indeed divergent. <br /><br />The reason is that the we are dealing with a random walk. There is a good chance (1/2) in this case that the number of heads are never equal to the number of tails. The proof is fairly trivial using recursion.<br /><br />For a general coin which is not fair, the probability that the number of heads is ever equal to the number of tails is min(p,1-p). again as I said the proof is trivial by recursion.Sivahttps://www.blogger.com/profile/12469392360597269559noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-45382077284537084172011-02-08T19:29:42.199+05:302011-02-08T19:29:42.199+05:30The expected number diverges for me too.
For all ...The expected number diverges for me too.<br /><br />For all the situations where the absolute difference between the number of heads and tails is same the expected number of tosses required to reach the situation of equal number of heads and tails is same. Also, if the current difference is 'd' then with equal probability the difference may increase or decrease after the next toss. Let E(d) be the expected number of tosses required to get equal number of heads and tails when the current difference between their counts is d. So, E(d) = 1 + 0.5 * E(d-1) + E(d+1). Also, E = 1 + E(1). and E(0) = 0. Solving this, E = i + (1/i)*E(i). Since for any i E(i) will be positive. The result diverges.AAhttps://www.blogger.com/profile/15052240248744955514noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-19570575975246666892011-02-08T00:09:36.269+05:302011-02-08T00:09:36.269+05:30sorry about previous argument..In E(X) nth term T_...sorry about previous argument..In E(X) nth term T_n has probabilty = p_n = q_(2n-2)-q_2n..where q_2n=binomial(2n,n)*2^(-2n)..solving E(X)=2*p_1+4*p_2+...=2(1-q_2)+4(q_2-q_4)+...=2(1+q_2+q_4...)..now we can show as from previous comment that this diverges..so still clueless..:(kalyanhttps://www.blogger.com/profile/17407735020886348965noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-89995286980834314982011-02-07T23:49:55.548+05:302011-02-07T23:49:55.548+05:30E(X)=sum_(1 to inf) binomial(2n,n)*2^(-2n).
now as...E(X)=sum_(1 to inf) binomial(2n,n)*2^(-2n).<br />now as n->inf by stirling approximation T_n->n^(-.5)<br />which, by cauchy convergence criterion, is divergent.<br />I dunno what's wrong.kalyanhttps://www.blogger.com/profile/17407735020886348965noreply@blogger.com