tag:blogger.com,1999:blog-4115025577315673827.post6881471305924300353..comments2020-06-29T15:37:49.459+05:30Comments on CSE Blog - quant, math, computer science puzzles: Expected Number of Attempts - Broken Coffee MachinePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-4115025577315673827.post-84357966586134646152020-03-23T00:01:28.359+05:302020-03-23T00:01:28.359+05:30This is the same problem as:
https://prase.cz/kalv...This is the same problem as:<br />https://prase.cz/kalva/putnam/psoln/psol583.htmlKnkhttps://www.blogger.com/profile/14932847973299944142noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-61873465861801412542017-05-01T06:29:29.575+05:302017-05-01T06:29:29.575+05:30The integration result is wrong. The formula does ...The integration result is wrong. The formula does not work!. Unknownhttps://www.blogger.com/profile/14197186380704466013noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-40492327698502639582017-02-03T11:37:50.839+05:302017-02-03T11:37:50.839+05:30say (i+1)th is time when its fill cup but is proba...say (i+1)th is time when its fill cup but is probability of filling at (i+1)th time is a sure event? i mean probability will be p(x1+x2+..x_i < 1)*(probability of filling at i+1 th time). time multiplied term is not 1 always.....jaswant singhhttps://www.blogger.com/profile/11733611833623394037noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-29036776663027548082017-02-03T11:13:42.895+05:302017-02-03T11:13:42.895+05:30The amount of coffee filled currently should not d...The amount of coffee filled currently should not depend on how much coffee previously filled in the cup. So Markov model may not be a good option. I think 2 is correct answer since expected amount in one fill is 50%.<br />jaswant singhhttps://www.blogger.com/profile/11733611833623394037noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-15706283117977152002016-01-23T07:52:52.570+05:302016-01-23T07:52:52.570+05:30Q(v,k) = Prob. of x1+x2+...xk adding < v for 0&...Q(v,k) = Prob. of x1+x2+...xk adding < v for 0<=v<1<br />P.T. Q(v,k) = v^k/k!.<br />Proof by induction. True for k=1<br />Q(v,k+1) can be defined as:<br />for every value x of k+1'th variable, integration over probability that last k vars add up to (v-x)<br />=> Q(v,k+1) = Int(0->v)[Q(v-x,k).dx] = Int(0->v)[(v-x)^k/k!.dx] = v^(k+1)/(k+1)!<br />Hence proved by induction.<br />The value to be proved it Q(1,n) = 1/n!Stainless...https://www.blogger.com/profile/13692804410410651536noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-80682527575721993002015-10-26T16:42:26.843+05:302015-10-26T16:42:26.843+05:30Increadable. I expected in to be 2 because automat...Increadable. I expected in to be 2 because automata is expected to dispense 1/3 of cup in average. Yet, simulation http://scastie.org/12772 says that 2.7 is right!valjokhttps://www.blogger.com/profile/05913343468893339183noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-10331826101702446532015-10-26T15:47:28.151+05:302015-10-26T15:47:28.151+05:30An interesting thing to note is that E[% full afte...An interesting thing to note is that E[% full after pushing the button twice)]=100 Christian Chapmanhttps://www.blogger.com/profile/06804758591556577882noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-85600780844697099982015-08-22T18:35:43.358+05:302015-08-22T18:35:43.358+05:30Sorry @Aashish Kumar, it's a typo. You are rig...Sorry @Aashish Kumar, it's a typo. You are right Pr(S(n) < x) =x^n/n!. Thanks for pointing it out !Anonymoushttps://www.blogger.com/profile/17116418424004212784noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-32357515523907401872015-08-21T22:43:41.142+05:302015-08-21T22:43:41.142+05:30Great post!!, one quick question. You have mention...Great post!!, one quick question. You have mentioned that Pr(S(n) < x) =x/n!. Shouldn't it be Pr(S(n) < x) =x^n/n!Anonymoushttps://www.blogger.com/profile/10164648415516700793noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-17866672145487409632015-08-13T21:53:10.976+05:302015-08-13T21:53:10.976+05:30Let the fraction of the cup of coffee that gets fi...Let the fraction of the cup of coffee that gets filled at any i_th fill be denoted by a random variable X which is given to be uniformly distributed between [0,1].<br />Now, Let S(n) denote the sum of these n uniform random variables. <br />The Cumulative distribution function of this random variable S(n) i.e. Pr(S(n) < x) =x/n!. For details, see https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution. <br /><br />The probability of the event that the cup gets filled at the nth fill conditioned on the event that in the nth fill, fraction x of cup is provided by the machine is. <br />Pr{ S(n) >= 1 and at nth fill 'x' fraction of cup gets filled } = Pr { S(n-1) >= 1-x && S(n-1) < 1 | at nth fill 'x' fraction of cup gets filled }<br />Clearly, the above event i.e. S(n-1) >= 1-x && S(n-1) < 1 ensures that cup gets filled in the nth fill given that the nth fill provides us with x fraction of cup of coffee. <br />Pr{ S(n-1) >= 1-x && S(n-1) < 1 } = {1 - (1-x)^(n-1)} / { (n-1) ! } (Using CDF of sum of uniform random variables)<br />Pr{ at nth fill 'x' fraction of cup gets filled } = pdf{X = x}dx. This is the probability that the fraction of the cup that gets filled is within x to x+dx <br />To get the total probability that Pr {S(n) >= 1}, we need to integrate over all fractions 'x' from 0 to 1.<br />Pr{ S(n) >= 1 } = integral[0,1] of Pr{ 1-x <= S(n-1) <= 1 }*(1) dx since pdf {X=x} = 1. (Uniform distribution).<br />Pr{ 1-x <= S(n-1) <= 1 } = (1 - (1-x)^(n-1) ) / ( (n-1) ! )<br />Pr{ S(n) >= 1 } = (1/n(n-2)! )<br />Its not hard to check Summation { n=2 to inf } (1/n(n-2)! ) = 1.<br />Therefore, expected no of fills required = Summation {n=2 to inf } 1/(n-2)! = e.Anonymoushttps://www.blogger.com/profile/17116418424004212784noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-49403422695091007382015-06-16T19:46:26.149+05:302015-06-16T19:46:26.149+05:30Let f(x) be the expected number of fills required ...Let f(x) be the expected number of fills required to fill the glass upto (>x) fraction (DEFINED ON x<=1). Consider 2 cases on the fraction y of the next fill. If (y(y-x)) fraction more, having already filled once and thus, EXPECT to take 1 + f(x-y) fills in total. If (y>x), we just needed 1 fill. Thus, f(x) = integral [y=0 to x] of (1 + f(x-y)) dy + integral [y=x to 1] of 1 dy. Differentiating this with respect to x, we have: f'(x)= f(x) which gives f(x) = c.e^x; c can be evaluated to be 1, by substituting in the original equation. Thus, the answer is f(1) = e.Anonymoushttps://www.blogger.com/profile/18313929688691542872noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-83569984269466001532015-06-16T19:31:14.901+05:302015-06-16T19:31:14.901+05:30You are right. The boundary condition at 0 is argu...You are right. The boundary condition at 0 is arguable. You can instead say that (lim x->0) E(x) = 1. Also, letting E(x) = c*e^x, the constant c can be found by substituting in the original equation, which by the way has some error. (Refer to the corrected solution in the comment below.)Anonymoushttps://www.blogger.com/profile/18313929688691542872noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-32431139211136806372015-01-20T21:55:15.728+05:302015-01-20T21:55:15.728+05:30Can you explain the logic behind this - P(x1+x2......Can you explain the logic behind this - P(x1+x2...x_n < 1) = 1/n! ?piyushmaheshhttps://www.blogger.com/profile/11078759951817026087noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-71029486998879970372015-01-18T23:18:28.683+05:302015-01-18T23:18:28.683+05:30@Kushal: Why E(0)=1? Shouldn't the expected nu...@Kushal: Why E(0)=1? Shouldn't the expected number of trips to fill the cup up to 0th fraction (i.e empty) be 0?Anonymoushttps://www.blogger.com/profile/11982347702551354473noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-32170329221764848702014-12-29T10:39:15.623+05:302014-12-29T10:39:15.623+05:30Let f(x) denote the expected time to fill a glass ...Let f(x) denote the expected time to fill a glass with x liters. We can model this as a Markov chain and find the expected time to reach an absorbing state. Anonymoushttps://www.blogger.com/profile/12641742133746623129noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-80124514317113191842014-12-17T01:25:43.617+05:302014-12-17T01:25:43.617+05:30Using continuous probability. Let E(x)=expected nu...Using continuous probability. Let E(x)=expected number of trips required to fill up the cup upto x-th fraction. <br />Then E(x)=Integral fo (E(x-i)*(1-i)di) with i=0 to x,<br />We obtain at this integral by considering that first we need to fill upto a fraction x-i and then the machine a fraction greater than i the probability of which is 1-i.<br />Using substitution x=1-t, we obtain E(x)= Integral of (E(t)dt) with t from 0 to x.<br />Using second Fundamental theorem of calculus. dE(x)/dx=E(x), Integration with limits from x=0 to 1 and the boundary condition that E(0)=1, we get E(1)=e.Anonymoushttps://www.blogger.com/profile/12087461542612216465noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-78774961528095962522014-12-11T06:27:37.788+05:302014-12-11T06:27:37.788+05:30x_i : The fraction of cup , the coffee machine fil...x_i : The fraction of cup , the coffee machine fills in ith filling<br />This is uniformly distributed variable varying from 0 to 1<br /><br />We would fill for i+1 th time if x1+x2+..x_i < 1<br />P(x1+x2...x_n < 1) = 1/n!<br />So<br />answer = 1 + P(x1<1) + P(x1+x2<1) + P(x1+x2+x3<1)....<br /> = 1 + 1/1! + 1/2! + 1/3! ....<br /> = e<br />stphttps://www.blogger.com/profile/08966664548209965371noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-61605058621342522422014-12-10T14:41:39.376+05:302014-12-10T14:41:39.376+05:30btw we fill the cup only once...we press the butto...btw we fill the cup only once...we press the button 3 times!Animesh Saxenahttps://www.blogger.com/profile/09266667751076680009noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-63880846668126319102014-12-10T10:32:00.336+05:302014-12-10T10:32:00.336+05:302.7 or 3 times2.7 or 3 timesAnimesh Saxenahttps://www.blogger.com/profile/09266667751076680009noreply@blogger.com