{"id":6781,"date":"2014-01-24T14:09:45","date_gmt":"2014-01-24T13:09:45","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=6781"},"modified":"2014-01-24T14:30:02","modified_gmt":"2014-01-24T13:30:02","slug":"random-bits","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2014\/01\/24\/random-bits\/","title":{"rendered":"Random bits"},"content":{"rendered":"<p><a href=\"http:\/\/djalil.chafai.net\/blog\/2011\/03\/25\/no-dice\/diceindice\/\" rel=\"attachment wp-att-1493\"><img loading=\"lazy\" class=\"aligncenter size-medium wp-image-1493\" alt=\"Dice\" src=\"http:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2011\/03\/diceindice-300x300.jpg\" width=\"300\" height=\"300\" srcset=\"https:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2011\/03\/diceindice-300x300.jpg 300w, https:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2011\/03\/diceindice-150x150.jpg 150w, https:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2011\/03\/diceindice.jpg 315w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p style=\"text-align: justify;\">The lowest unit of randomness is probably a random uniform bit, in other words a symmetric Bernoulli random variable taking the values \\( {0} \\) and \\( {1} \\) with probability \\( {1\/2} \\). If<\/p>\n<p style=\"text-align: center;\">\\[ U=\\sum_{n=1}^\\infty b_n2^{-n} \\]<\/p>\n<p style=\"text-align: justify;\">is the binary expansion of a random variable \\( {U} \\) taking values in the interval \\( {[0,1]} \\), then \\( {U} \\) follows the uniform law on \\( {[0,1]} \\) iff the bits \\( {{(b_n)}_{n\\geq1}} \\) are i.i.d. symmetric Bernoulli. As explained in a <a href=\"http:\/\/djalil.chafai.net\/blog\/2011\/03\/18\/uniform-bits\/\">previous post<\/a>, this observation allows for instance to extract from \\( {U} \\) a whole infinite sequence of i.i.d. uniform random variables on \\( {[0,1]} \\). But real real numbers are not accessible in current computers.<\/p>\n<p style=\"text-align: justify;\">In a computer, everything is finite, and we use a finite sequence of bits to produce a uniform discrete random variable, up to a fixed precision, typically \\( {32} \\) or \\( {64} \\) bits, which corresponds to \\( {2^{32}} \\) and \\( {2^{64}} \\) different values respectively. More generally, the simulation of the discrete uniform law on \\( {n} \\) different values amounts to the coding in bits of the integer \\( {n} \\), namely \\( {\\log_2(n)} \\) bits. In particular, the simulation of a random permutation \\( {\\sigma_n} \\) on \\( {\\{1,\\ldots,n\\}} \\) costs approximately \\( {\\log_2(n!)\\sim n\\log_2(n)} \\) bits. If we use the <a href=\"http:\/\/djalil.chafai.net\/blog\/2011\/06\/30\/random-uniform-permutations\/\"> Fisher-Yates-Knuth shuffle<\/a>, we simulate \\( {\\sigma_n} \\) using the representation in terms of product of transpositions \\( {\\sigma_n=(1,U_1)\\cdots(1,U_n)} \\) where \\( {U_1,\\ldots,U_n} \\) are independent with \\( {U_k} \\) following the uniform discrete law on \\( {\\{1,\\ldots,k\\}} \\) for every \\( {1\\leq k\\leq n} \\). Then the total cost is \\( {\\sim\\sum_{k=1}^n\\log_2(k)\\sim n\\log_2(n)} \\), as expected.<\/p>\n<p style=\"text-align: justify;\">If we start from a fixed deterministic matrix \\( {{(x_{jk})}_{1\\leq j,k\\leq n}} \\), and produce a random matrix<\/p>\n<p style=\"text-align: center;\">\\[ {(x_{\\sigma(j,k)})}_{1\\leq j,k\\leq n} \\]<\/p>\n<p style=\"text-align: justify;\">by shuffling the \\( {n^2} \\) entries with a random uniform permutation \\( {\\sigma} \\) of \\( {\\{1,\\ldots,n^2\\}} \\), then we use approximately \\( {2n^2\\log_2(n)} \\) bits. On the other hand, the production of a \\( {n\\times n} \\) random matrix with i.i.d. entries following the uniform distribution on \\( {\\{0,\\ldots,N\\}} \\) needs \\( {n^2\\log_2(N)} \\) bits (\\( {N=2} \\) for Bernoulli entries).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The lowest unit of randomness is probably a random uniform bit, in other words a symmetric Bernoulli random variable taking the values \\( {0} \\)&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/djalil.chafai.net\/blog\/2014\/01\/24\/random-bits\/\">Continue reading<span class=\"screen-reader-text\">Random bits<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":43},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/6781"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=6781"}],"version-history":[{"count":4,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/6781\/revisions"}],"predecessor-version":[{"id":6789,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/6781\/revisions\/6789"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=6781"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=6781"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=6781"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}