tag:blogger.com,1999:blog-8303670766007382241.post1683025607080027733..comments2016-03-31T23:10:26.879-07:00Comments on Sam Roweis 1972 - 2010: from David MacKaymaneeshhttp://www.blogger.com/profile/12551871125369783000noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-8303670766007382241.post-79280594460774332142010-01-25T21:35:36.238-08:002010-01-25T21:35:36.238-08:00Since Sam's puzzle sounded to me like a rephra...Since Sam's puzzle sounded to me like a rephrasing of Shannon's source coding theorem, I gave his puzzle as an in-class quiz to my information theory & complexity class. I was expecting a solution along the lines of "The biased coin generates H(p) bits of entropy per flip, so choose N and flip the coin N times and assign the typical sequences uniformly to length N*H(p) Erik Winfreehttp://www.blogger.com/profile/02648033592777493814noreply@blogger.comtag:blogger.com,1999:blog-8303670766007382241.post-67410970972678708782010-01-25T19:05:25.814-08:002010-01-25T19:05:25.814-08:00I realize that we want completely uncorrelated fli...I realize that we want completely uncorrelated flips, but if one is willing to live with small levels of correlation, can't you instead of flipping twice each time (as in Sam's solution) but rather flip once, and use the flip k flips ago to make the other half of the pair? This halves the number of flips relative to Sam's solution but of course creates some (small if k is large) Hogghttp://www.blogger.com/profile/18398397408280534592noreply@blogger.comtag:blogger.com,1999:blog-8303670766007382241.post-57023627466908135002010-01-21T23:38:43.839-08:002010-01-21T23:38:43.839-08:00Here is another way to generalize from Sam’s hint....Here is another way to generalize from Sam’s hint. Flip the coin n times and let h be the number of heads. There are choose(n,h) possible sequences with h heads, and they are equally likely. Number them and write the index of the sequence you got in binary. Thus the problem is reduced to converting a uniformly-distributed integer into uniform bits. This gives floor(log2(choose(n,h))) bits. Tom Minkahttp://research.microsoft.com/~minka/noreply@blogger.comtag:blogger.com,1999:blog-8303670766007382241.post-23498495901105524002010-01-19T09:36:22.758-08:002010-01-19T09:36:22.758-08:00That's the impression I got as well: at the ex...That's the impression I got as well: at the extremes, this solution seems optimal since you need at least one of each draw to get a bit, which is almost what it provides (minus the HH case if P(T)~ 1, which is negligible). After a lunch discussion, John Winn came with a better solution:<br />- if HT or TH comes up, do as before;<br />- if HH or TT comes up, store it and wait until the next Nicolashttp://www.blogger.com/profile/07883528294408918659noreply@blogger.comtag:blogger.com,1999:blog-8303670766007382241.post-15550785593031245422010-01-18T15:16:39.425-08:002010-01-18T15:16:39.425-08:00I love that you posted a puzzle. Over the past fe...I love that you posted a puzzle. Over the past few days when I start to focus on how sad it is, I shift gears and work on the puzzle instead. As someone at the amazing memorial service said, "It's what Sam would have wanted."<br /><br />I've made some progress, but I'm still a bit stumped. One observation is that, as the coin probability approaches 0 or 1, the coin has Michael Littmanhttp://www.blogger.com/profile/05878303953204580887noreply@blogger.com