tag:blogger.com,1999:blog-8890204.post8050522808291360907..comments2020-06-03T19:29:40.605-04:00Comments on My Biased Coin: Happy New Academic Year: Teaching Randomized AlgorithmsMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-8890204.post-87038937050937692162019-09-06T23:07:08.644-04:002019-09-06T23:07:08.644-04:00I should have added "to keep the long term pr...I should have added "to keep the long term probability rate the same, since it can occur in overlapping clusters".Kodluhttps://www.blogger.com/profile/12418167413500125327noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-19777974652129020632019-09-06T23:06:16.283-04:002019-09-06T23:06:16.283-04:00I teach your pattern probability / expectation puz...I teach your pattern probability / expectation puzzle in my information theory class. It's got some nice combinatorics, and the fact that the expected time to first see the pattern depends on the pattern is counterintuitive at first. Non rigorously, if a pattern self overlaps, as in HHH, since it overlaps with itself if shifted by one and by two letters, it tends to take longer to appear at first "to keep the long term probability rate the same". J. H. Conway has also looked at this in terms of correlation polynomials which represent the overlap properties. Also, whoever chooses first, the second person can choose a pattern that will beat the first pattern on average, but this is non transitive, Pattern A can beat Pattern B which beats Pattern C which beats Pattern A.Kodluhttps://www.blogger.com/profile/12418167413500125327noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-12535385912354210892019-09-04T22:35:11.015-04:002019-09-04T22:35:11.015-04:00Thanks for the pointer -- secretary problem is the...Thanks for the pointer -- secretary problem is the start of next class, though maybe less puzzle-oriented.<br /><br />Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-24292085714135815802019-09-04T14:18:51.649-04:002019-09-04T14:18:51.649-04:00The secretary problem sounds like one of those pro...The secretary problem sounds like one of those problems where the math is easy and students can develop their own ideas.<br />There is also a generalization to bipartite matching that reaches the same approximation bound of 1/e. The proof by Kesselheim et al. is short and uses only elementary probability arguments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-45910420679737927132019-09-04T10:25:19.506-04:002019-09-04T10:25:19.506-04:00Hooray for your return to blogging!
I haven't...Hooray for your return to blogging!<br /><br />I haven't seen this problem before, but it is strongly reminiscent of those efficient string matching algorithms where you build a little state machine, and never look at a letter twice. I'm going to guess that either HTT, or THH are good answers because once you've seen at least one of each H and T, then you will always be matching at least one symbol in the string. I can't think of other strings which will have this property.) <br /><br />Feel free to delete this comment if I got it correct! (Or leave it up to lead others astray.)<br /><br />Philip Sternehttps://www.blogger.com/profile/17209057979470356061noreply@blogger.com