tag:blogger.com,1999:blog-8890204.post5177523722807254420..comments2024-10-12T07:11:38.932-04:00Comments on My Biased Coin: Programming for Non-Programming ExercisesMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8890204.post-50252670591073513862011-11-14T04:08:35.926-05:002011-11-14T04:08:35.926-05:00I like the way you look at things, and I encourage...I like the way you look at things, and I encourage Claire to actually do what she proposes.Abelhttp://www.cs.uwaterloo.ca/~amolinap/noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-1532539350781383922011-11-10T15:47:33.867-05:002011-11-10T15:47:33.867-05:00I love this problem :-)
I present it in the follo...I <b>love</b> this problem :-)<br /><br />I present it in the following form: "You and N of your friends are sitting at a round table. You have a very large bag of M&Ms and a coin. Eat an M&M, flip the coin. On heads, pass the bag and coin to the person on the left --- on tails, pass them to the person on the right. Continue this random walk until everyone has eaten at least 1 M&M.<br /><br />Easier: For each of your N friends (from #1 on your left all the way round to #N on your right), what is the probability they are the *last* person to eat an M&M?<br /><br />Harder: What if the coin isn't fair?"<br /><br /><br />My biased coin is likely to stump the simulation-only crowd, forcing them into [:shudder:] <i>algebra</i>.<br /><br /><br />Here is a related problem: "There are N balls in a bag. Initially all the balls have distinct colors. Define an 'iteration' as follows: reach into the bag and pick out a pair of balls --- color the ball in your right hand so it matches the ball in your left hand --- put them back. On average, how many iterations until all the balls are the same color?"F. Carrnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-12480093273956826882011-11-10T12:37:59.678-05:002011-11-10T12:37:59.678-05:00@mm, you've defined a symmetric ring with zero...@mm, you've defined a symmetric ring with zero or one unique sheep-containing points (depending on whether n is odd or even). Are you sure you want to phrase the question as "which sheep is" in the singular? :-) Or maybe I misunderstood the formulation.<br /><br /><br />baaa. nice post, though. i'd be one of those simulators. :)David Andersenhttps://www.blogger.com/profile/03996590425188586871noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-391277284184651092011-11-10T11:27:39.939-05:002011-11-10T11:27:39.939-05:00What a timely piece.
I am thinking precisely now...What a timely piece. <br /><br />I am thinking precisely now of changing part of our intro course for freshmen. It has a piece (that I just got done teaching) on runtime analysis, solving simple recurrences, proofs by induction, and the like. <br /><br />I'm considering replacing that by coding the recurrences, looking at the resulting data on runtime, and inferring from those data points whether the runtime is linear, quadratic, n log n, etc. Formal analysis would be deferred to later semesters.Claire Mathieuhttps://www.blogger.com/profile/10957755706440077623noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-74589805951985828012011-11-09T23:43:24.219-05:002011-11-09T23:43:24.219-05:00Anon: you can condition on the event "there e...Anon: you can condition on the event "there exists a finite time t such that at time t the wolf has eaten all sheep". This happens with probability 1.Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-32602616543461744372011-11-09T14:31:37.818-05:002011-11-09T14:31:37.818-05:00Won't the answer depend on how long this proce...Won't the answer depend on how long this process continues? Do you implicitly mean it continues forever?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-72695814626042206302011-11-09T12:54:48.770-05:002011-11-09T12:54:48.770-05:00Hmm... does the answer change if the sheep are als...Hmm... does the answer change if the sheep are also taking random walks, and the wolf eats all sheep at his location?Andy Dhttp://andysresearch.blogspot.com/noreply@blogger.com