{"id":2261,"date":"2019-05-05T16:57:13","date_gmt":"2019-05-05T23:57:13","guid":{"rendered":"http:\/\/zackmdavis.net\/blog\/?p=2261"},"modified":"2019-05-05T17:00:09","modified_gmt":"2019-05-06T00:00:09","slug":"the-typical-set","status":"publish","type":"post","link":"http:\/\/zackmdavis.net\/blog\/2019\/05\/the-typical-set\/","title":{"rendered":"The Typical Set"},"content":{"rendered":"<p>(Part of <a href=\"http:\/\/zackmdavis.net\/blog\/2019\/05\/may-is-math-and-wellness-month\/\">Math and Wellness Month<\/a>.)<\/p>\n<p>Say you have a biased coin that comes up Heads 80% of the time. (I like to imagine that the Heads side has a portrait of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bernoulli_process\">Bernoulli<\/a>.) Flip it 100 times. The na\u00efve way to report the outcome\u2014just report the sequences of Headses and Tailses\u2014costs 100 bits. But maybe you don't have 100 <a href=\"https:\/\/mlp.fandom.com\/wiki\/Bits\">bits<\/a>. What to do?<\/p>\n<p>One thing to notice is that because it was a biased coin, some bit sequences are <em>vastly<\/em> more probable than others: \"all Tails\" has probability 0.2<sup>100<\/sup> \u2248 1.268 \u00b7 10<sup>\u221270<\/sup>, whereas \"all Heads\" has probability 0.8<sup>100<\/sup> \u2248 2.037 \u00b7 10<sup>\u221210<\/sup>, differing by a factor of <em>sixty orders of magnitude<\/em>!!<\/p>\n<p>Even though \"all Heads\" is the uniquely most probable sequence, you'd still be pretty surprised to see it\u2014there's only <em>one<\/em> such possible outcome, and it only happens a 2.037 \u00b7 10<sup>\u221210<\/sup>th of the time. You <em>probably<\/em> expect to get a sequence with <em>about<\/em> twenty Tails in it, and there are <em>lots<\/em> of those, even though each individual one is less probable than \"all Heads.\"<\/p>\n<p>Call the number of times we flip our Bernoulli coin <em>N<\/em>, and call the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Entropy_(information_theory)\">entropy<\/a> of the coinflip <em>H<\/em>. (For the 80\/20 biased coin, <em>H<\/em> is \u2155 lg 5 + 4\/5 lg 5\/4 \u2248 0.7219.)<\/p>\n<p>It turns out for sufficiently large <em>N<\/em> (I know, one of <em>those<\/em> theorems, right?), <em>almost all<\/em> of the probability mass is going to live in a subset of 2<sup>NH<\/sup> outcomes, each of which have a probability close to 2<sup>\u2212NH<\/sup> (and you'll notice that 2<sup>NH<\/sup> \u00b7 2<sup>\u2212NH<\/sup> = 1).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>(Part of Math and Wellness Month.) Say you have a biased coin that comes up Heads 80% of the time. (I like to imagine that the Heads side has a portrait of Bernoulli.) Flip it 100 times. The na\u00efve way &hellip; <a href=\"http:\/\/zackmdavis.net\/blog\/2019\/05\/the-typical-set\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[7],"tags":[94],"_links":{"self":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/2261"}],"collection":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/comments?post=2261"}],"version-history":[{"count":2,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/2261\/revisions"}],"predecessor-version":[{"id":2263,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/2261\/revisions\/2263"}],"wp:attachment":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/media?parent=2261"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/categories?post=2261"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/tags?post=2261"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}