tag:blogger.com,1999:blog-4115025577315673827.post173918010159002025..comments2019-10-21T14:10:54.375+05:30Comments on CSE Blog - quant, math, computer science puzzles: 100 sided die probability problemUnknownnoreply@blogger.comBlogger20125tag:blogger.com,1999:blog-4115025577315673827.post-27790540723586148812016-11-14T12:39:08.607+05:302016-11-14T12:39:08.607+05:30First one needs to figure out a strategy to maximi...First one needs to figure out a strategy to maximize his gain the game. This strategy will be : "play until you get equal to or greater than the expected value of the game."<br />Now, only thing remains is to actually find the expected value of the game.<br />So, let's say the expected value is K.<br />Then expected revenue (excluding the cost of playing) will be (K+100)/2. This is very simple.<br />Now, we need to figure out the cost of playing, that means the expected number of turns before the first success multiplied by cost of playing one turn. Now since we will succeed once we get any number greater or equal to K, probability of success is (100-(K-1))/100 .<br />So, expected value (K) = ((100+K)/2) - ((100-(K-1))/100) .<br />This will give you a quadratic equation, solving which you will get K=114.65 and K=86.35 . Obviously 114.65 is not the answer. So, the answer is greatest integer above 86.35 ie. 87 Unknownhttps://www.blogger.com/profile/00406646205011668928noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-62988904468821151022014-10-05T13:50:13.751+05:302014-10-05T13:50:13.751+05:30@JDGM , I have a doubt with your 4th point : "...@JDGM , I have a doubt with your 4th point : " Round strategy does not change round to round as everything is the same except the amount of money in your "wallet", which has no effect on the round being played" <br /><br /><br />A person playing the game wants to take home more money than what he brought,why will someone play more than 51 games as he already lost 50 bucks and the expected profit is (50.5-50) = 0.5.I think the optimal strategy for stopping the game changes for each round,the strategy should be calculated by dynamic approach (working backward from 51st round).....<br /><br />Correct me if i'm wrong !!!! Am i missing something very basic ?? rajesh iitmhttps://www.blogger.com/profile/04472744824090370564noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-5775546238151543712014-06-22T19:21:16.815+05:302014-06-22T19:21:16.815+05:30ThanksThanksPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-79541975816088036752014-06-22T19:19:51.442+05:302014-06-22T19:19:51.442+05:30Lets assume that expected value of the game = E
At...Lets assume that expected value of the game = E<br />At any turn, we roll the dice again we get a number less than E-1<br /><br />Assuming that the die gives a uniform value in [0,100]<br /><br />E = (100-E-1)/100*((100+E-1)/2) + (E-1)*((E-1))/100<br />E = (101-E)*(99+E)/200 + (E-1)^2/100<br />200E = E^2-4E+2 + 9999 + 2E <br />E^2-202E+10001=0<br /><br />Solving for E, and E<100, <br />we get, E=86.85<br /><br />Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86233333493365985042014-06-22T18:53:36.458+05:302014-06-22T18:53:36.458+05:30Thanks. Interesting solutionThanks. Interesting solutionPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55980010477592839852014-06-22T18:52:33.349+05:302014-06-22T18:52:33.349+05:30This is awesome. ThanksThis is awesome. ThanksPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-24815119726456516182014-06-22T18:52:10.618+05:302014-06-22T18:52:10.618+05:30Bang on. ThanksBang on. ThanksPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55883090673973036772014-06-22T18:50:40.968+05:302014-06-22T18:50:40.968+05:30Thanks. I was doing the same mistake.Thanks. I was doing the same mistake.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-23649035666738158962014-06-22T18:50:20.747+05:302014-06-22T18:50:20.747+05:30"Expected value of a roll is 50.5
Expected va..."Expected value of a roll is 50.5<br />Expected value of a roll after the first roll is 49.5 (since we need to pay 1)" Thats wrong. You do not have to stop. The optionality gives a higher value to each rollPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-54966598458577786682014-05-27T01:11:03.288+05:302014-05-27T01:11:03.288+05:30I'm getting the value of the game to be 87.35
...I'm getting the value of the game to be 87.35<br />And the strategy to stop when you get more than 86.35<br /><br />Here's a quick simulation in Excel for this:<br />https://drive.google.com/file/d/0B1YlEqf_n9Kod1hjZXREN0F6M3M/edit?usp=sharingdumb phoenixhttps://www.blogger.com/profile/00055674176590701098noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-20653819219862114872014-01-11T23:44:52.736+05:302014-01-11T23:44:52.736+05:30your stopping rule is not optimal.your stopping rule is not optimal.Fu Shihttps://www.blogger.com/profile/02166408545917628856noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86087667700416295372014-01-11T23:43:42.274+05:302014-01-11T23:43:42.274+05:30We can agree that stopping rule is to hit above so...We can agree that stopping rule is to hit above some threshold m. <br />Let N = total number played, then N is geometrically distributed with p = (100 - m)/100.<br />Let T(m, N) = total earning after N plays with stopping threshold m (this means we hit >= m for all first N - 1 plays).<br /> Denote T(m, N) as T whenever unambiguous.<br />Then<br /><br />E(T) = E(E(T|N)) = E[(100 + (m+1))/2 - (N - 1)] = (101+m)/2 - E(N) + 1 = (101+m)/2 - 100/(100-m) + 1 = f(m)<br /><br />set f'(m) = 1/2 - 100/(100 - m)^2 to 0 to get m = 100 - sqrt(200), check floor(m) and ceil(m) to obtain the optimal stopping thresh = 86, so you stop if you hit >86. Plug this into the expectation to get the answer.Fu Shihttps://www.blogger.com/profile/02166408545917628856noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-66641700859878240562013-10-01T22:12:16.151+05:302013-10-01T22:12:16.151+05:30If there were no provisions for playing again, one...If there were no provisions for playing again, one would have an expectation of 50.5 from the roll. Since you have to pay 1 dollar to roll again, your expected winning from any subsequent roll is 50.5-1 or 49.5. So only if you have rolled a number less than 49.5 would you be willing to roll again. This means that if you get a number from 1 to 49 (probability 0.49) you would roll again, but if you got a number from 50 to 100 (probability 0.51) you wouldn't roll again. <br /><br />Let the expected winnings from the game be X.<br /><br />E(X) = 0.49 * (Expected value from playing the game again) + 0.51 * 75<br />E(X) = 0.49*(-1 +E(X)) + 0.51*75<br /><br />Solving, we get, <br />E(X) ~ 74.02<br /><br />I'd be very thankful is someone could point out where I'm going wrong.<br /><br />Sushant Choudharyhttps://www.blogger.com/profile/01112421306254066971noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86371633019014374762013-04-11T23:59:49.998+05:302013-04-11T23:59:49.998+05:30Answer: 1223/14 ~ 87,36
Defining the problem:
Th...Answer: 1223/14 ~ 87,36<br /><br />Defining the problem:<br /><br />The average value of the entire game obviously depends on the strategy used. We can't include *every* possible scenario, because infinitely many of them would be losing scenarios (e.g. continuing to play even after you get 100 and infinitely many other silly scenarios). So we must choose a strategy that determines when to stop playing, and it must be the *optimal* strategy (i.e. resulting in the maximum average value) for there to be only one final answer to the problem.<br /><br />If we decide to stop as soon as we get the number K or above, the average winning number is A = (100+K)/2. The average net result is A minus the number of rolls we pay for. The chance of succeding in the first roll is P(X>=K) and the chance of losing the first roll and succeding on the second is P(X=K) and so on...<br /><br />The average value of the game is:<br /><br />P(X>=K)*A + P(X=K)*(A-1) + P(X=K)*(A-2) + ...<br /><br />This looks messy, so let's define p = P(X=K) = 1-p, so we get:<br /><br />(1-p)*A + p*(1-p)*(A-1) + p^2*(1-p)*(A-2) + ...<br /><br />or<br /><br />(1-p) * (A + p*(A-1) + p^2*(A-2) + ...)<br /><br />or<br /><br />(1-p) * (A*p^0 + A*p^1 + A*p^2 + ... - 1*p - 2*p^2 - 3*p^3)<br /><br />or<br /><br />(1-p) * ( A*(p^0 + p^1 + p^2 + ...) - (p + 2*p^2 + 3*p^3 + ...) )<br /><br /><br />This still looks messy, but fortunately we can reduce the two infinite series:<br /><br />(p^0 + p^1 + p^2 + ...) converges to 1/(1-p)<br />(p + 2*p^2 + 3*p^3 + ...) converges to p/(1-p)^2<br /><br />so we get:<br /><br />(1-p) * ( A*(1/(1-p)) - p/(1-p)^2 )<br /><br />or<br /><br />A - p/(1-p) or if you like: A - P(X=K)<br /><br />Now that looks better! Plugging various numbers into this formula shows that 87 is indeed the optimal number, giving us the expected value:<br /><br />93.5 - 86/100 / (14/100) = 93.5 - 86/14 = 2618/14 -86/14 = 2536/14 = 87,36<br /><br /><br />This calculation is much easier to do numerically in a spreadsheet with the following columns:<br /><br />Roll no. | Money spent | P(win) | P(lose) | Contribution to expected value<br /> 1 | 0 | 0.14 | 0.86 | P(win)*(93.5 - Money spent) = 0.14*93.5<br /> 2 | 1 | 0.86*0.14~0.12 | 0.74 | P(win)*(93.5 - Money spent) = 0.12*92.5<br /> 3 | 2 | 0.74*0.12~0.104 | 0.6336 | P(win)*(93.5 - Money spent) = 0.104*91.5<br /><br />Here P(win) and P(lose) are the probabilities of losing N-1 rolls followed by winning/losing the Nth roll. Do this for about 80-100 rows and calculate the sum of the "contributions" row.Sebastianhttps://www.blogger.com/profile/13751004267351019826noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-33793929065455194692013-04-09T08:57:19.951+05:302013-04-09T08:57:19.951+05:30Oh, I have just seen why there was an apparent dis...Oh, I have just seen why there was an apparent discrepancy with Félix's numbers...<br /><br />I finished at finding the exact value of X in the strategy for a <i>continuous</i> "100-sided" dice, instead of converting it to the discrete case (which gives X=87) and plugging that back into the series to calculate the expected value of the game i.e. the actual answer we were looking for. Doing that gives me 1223/14, which is the same as Félix when you add the extra 1 for getting a free first roll.<br /><br /><b>The answer is 1223/14.</b>JDGMhttps://www.blogger.com/profile/11829357060109505064noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-52101001386414760622013-04-09T04:47:11.119+05:302013-04-09T04:47:11.119+05:30Félix has it.
I simmed this with 100 players each...Félix has it.<br /><br />I simmed this with 100 players each using a different "Keep playing until I roll X or greater" strategy (<a href="http://pastebin.com/DDN365BW" rel="nofollow">code</a> here, put it in a compiler <a href="http://www.compileonline.com/compile_cpp_online.php" rel="nofollow">here</a>), and <i>then</i> thought about the "why?".<br /><br />Here's my process for actually proving it:<br /><br />1. There are 2¹⁰⁰ possible strategies for a round: "If I get a {1, 2, …, 100}, I will {keep playing, stop playing}".<br /><br />2. Any strategy which keeps playing on a certain roll, but stops playing on a lower roll than that (e.g. "If I get a 50 I will stop playing, if I get a 70 I will keep playing") is strictly inferior to the same strategy with those values switched.<br /><br />3. Therefore, the only strategy for a round is "If I get X or higher I will stop, otherwise I will keep playing".<br /><br />4. Round strategy does not change round to round as everything is the same except the amount of money in your "wallet", which has no effect on the round being played.<br /><br />5. Therefore, the only strategy for the whole game is "If I get X or higher I will stop, otherwise I will keep playing".<br /><br />6. The expected return for that strategy is:<br /><br />Σ(n=1 to infinity):<br />P(roll≥X on nᵗʰ round) * Predicted $ win<br />- P(roll<X on nᵗʰ round * $1<br /><br />It's a geometric series:<br /><br />Σ(n=1 to infinity):<br />((X-1)/100)ⁿ⁻¹((101-X)/100) * (100+X)/2<br />- ((X-1)/100)ⁿ * 1<br /><br />Simplifying and maximising for 0 < X <= 100, I get X = 101-10√2) ≈ 86.85786.<br /><br />That's not quite what Félix got with his method. But, erm... ah well. The answer is still 87.JDGMhttps://www.blogger.com/profile/11829357060109505064noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-56934030095948255362013-04-08T05:27:18.076+05:302013-04-08T05:27:18.076+05:30Expected value of a roll is 50.5
Expected value of...Expected value of a roll is 50.5<br />Expected value of a roll after the first roll is 49.5 (since we need to pay 1)<br />The player stops if he gets any value >49.5, and continues if he gets a value <49.5<br />For the values 1 to 49, we can substitute with the expected value of 49.5<br />So expected value of the game = [49*49.5 + 50+51+...+100]/100 = 62.505Arnabhttps://www.blogger.com/profile/13734216328461677608noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55913899169547500762013-04-07T06:24:36.288+05:302013-04-07T06:24:36.288+05:30"If expected value of the game = E At any tu..."If expected value of the game = E At any turn, we roll the dice again we get a number less than [E-1]"<br />---- This is not correct because interpretation of Expected Value is not correct.Vivek Ranjan Nemahttps://www.blogger.com/profile/04863121359660229833noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-64720228707146791402013-04-07T05:00:19.718+05:302013-04-07T05:00:19.718+05:30The winning strategy is to play until you hit 87 o...The winning strategy is to play until you hit 87 or higher.<br />The expected value when you do is 93.5 (mean of 87 to 100).<br />The expectation of the needed number of rolls is 100 / 14, which means the end gain expectation is<br />E = 93.5 - 100 / 14<br />E = 1209 / 14<br />E ~= 86.357<br /><br />(or plus 1 if the initial roll is free)Félix de Chaumont Quitryhttps://www.blogger.com/profile/02724420621332283916noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-91874297786597865722013-04-06T22:17:42.658+05:302013-04-06T22:17:42.658+05:30If expected value of the game = E
At any turn, we ...If expected value of the game = E<br />At any turn, we roll the dice again we get a number less than [E-1]<br />[x] denotes the greatest integer less than or equal to x.<br /><br />Probability of getting a number greater than [E-1] = (1 - [E-1])/100<br />Given that we rolled greater than [E-1], expected value of the prize = ([E]+100)/2<br /><br />Expected number of rolls until we take the prize = 1/Probability of winning<br /><br />So, we have to pay these many dollars until we win. Expected value of winning is:<br />(expected value of prize given that we win - expected number of rolls)<br /><br />This expression should be equal to E.<br /><br />Either I did something wrong up there, or I'm solving the equation wrong. I got E=102, which does not make sense. :-|Saumya Guptahttps://www.blogger.com/profile/08604113046326932442noreply@blogger.com