{"id":351,"date":"2022-02-14T11:25:41","date_gmt":"2022-02-14T03:25:41","guid":{"rendered":"https:\/\/www.wennroy.com\/?p=351"},"modified":"2022-03-04T14:35:24","modified_gmt":"2022-03-04T06:35:24","slug":"sampling-from-a-distribution","status":"publish","type":"post","link":"https:\/\/wennroy.com\/index.php\/2022\/02\/14\/sampling-from-a-distribution\/","title":{"rendered":"Sampling from a distribution"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><strong>The problems to be Solved<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Problem 1: <\/strong>to generate samples $\\{\\textbf x^{(r)}\\}_{r=1}^R$ from a given probability distribution $P(\\textbf x)$.<\/li><li><strong>Problem 2: <\/strong>to estimate expectations of functions under this distribution, for example,<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">$$\\boldsymbol{\\Phi} = \\int \\phi(\\textbf x)P(\\textbf x)\\mathrm{d}^N \\textbf x$$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Uniform Sampling<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Drawing random samples $\\{\\textbf x^{(r)}\\}_{r=1}^R$ <em>uniformly <\/em>from the state space and evaluating $\\mathbb P^*(\\textbf x)$ at those points. Defined $Z_R$ as,<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$Z_R = \\sum_{r=1}^R P^*(\\textbf x)$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">And estimate $\\boldsymbol{\\Phi} = \\int \\phi(\\textbf x)P(\\textbf x)\\mathrm{d}^N \\textbf x$ by,<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$\\hat{\\boldsymbol{\\Phi}} = \\sum_{r=1}^R\\phi(\\textbf x^{(r)}\\frac{P^*(\\textbf x^{(r)})}{Z_R}.$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Typical Set: <\/strong>A high-dimensional distribution is often concentrated in a small region of the state space knwon as its typical set $T$, whose volume is given by $|T|\\simeq 2^{H(\\textbf X)}$, where $H(\\textbf X)$ is the Shannon-Gibbs entropy,<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$H(\\textbf X) = \\sum_{\\textbf X}P(\\textbf x)\\log_2\\frac{1}{P(\\textbf x)}$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u82e5\u4ee5\u53ea\u6709\u4e24\u4e2a\u72b6\u6001\u70b9\u7684Ising Model\u4e3e\u4f8b\u7684\u8bdd\uff0c\u4e00\u822c\u6765\u8bf4\u6211\u4eec\u53ea\u9700\u8981\u62bd\u6837$R_{\\min}$\u4e2a\u70b9\u5c31\u53ef\u4ee5\u5f88\u597d\u7684\u4f30\u8ba1\u4e86\uff0c<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$R_{\\min}\\simeq 2^{N-H} = 2^{N &#8211; N\/2} = 2^{N\/2}$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$N$\u4e3a\u7ef4\u6570\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4f46\u7531\u4e8eSampling\u6b21\u6570\u8fd8\u662f\u592a\u5927\uff0c\u6211\u4eec\u8fd8\u662f\u8fdb\u884c\u8ba1\u7b97\uff0c\u800c\u4e14\u5728\u9ad8\u7ef4\u7684\u60c5\u51b5\u4e0b\uff0c\u5982\u679c$\\mathbb{P}(\\textbf x)$\u4e0d\u662fUniform\uff0c\u90a3\u4e48\u4e5f\u5f88\u96be\u5229\u7528\u8fd9\u4e2a\u65b9\u6cd5\u6765Sampling\u3002\u56e0\u6b64\u63d0\u51fa\u4e86\u5176\u4ed6\u65b9\u6cd5\u6765\u89e3\u51b3\uff0c\u4f8b\u5982<strong>Importance Sampling, Rejection Sampling, Metropolis Method, Gibbs Sampling etc.<\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Importance Sampling<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Importance Sampling \u4e3b\u8981\u89e3\u51b3\u7b2c\u4e8c\u4e2a\u95ee\u9898\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Find a simpler density $Q(x)$, and its $Q^*(x)$ is easy to generate.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Introduce the &#8216;weights&#8217;,<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$w_r = \\frac{P^*(x^{(r)})}{Q^*(x^{(r)})}$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">which we use to adjust the &#8220;importance&#8221; of each point in our estimator thus:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$\\hat{\\boldsymbol{\\Phi}} = \\frac{\\sum_rw_r\\phi(x^{(r)})}{\\sum_rw_r}.$$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If $Q(x)$ is non-zero for all $x$ where $P(x)$ is non-zero, it can be proved that $\\hat{\\boldsymbol{\\Phi}}$ converges to $\\boldsymbol{\\Phi}$ as $R$ increases.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Disadvantages: Fisrt, we clearly need to obtain samples in the typical set of $P$. Second, even if we obtain samples in the typical set, the weights associated with those samples are likely to vary by large factors, because the probabilities of points in a typical set, although similar to each other, still differ by factors of order $\\exp(\\sqrt{N})$.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Rejection Sampling<\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>Draw  $x\\sim Q$,$Q$ is the proposal distribution.<\/li><li>Compute $$\\alpha = \\frac{p^*(x)}{cq^*(x)}$$<\/li><li>Draw $U\\sim\\text{Unif}(0,1)$<\/li><li>Accept $x$ if $u\\leq\\alpha$<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Disadvantages: Not efficiency.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The problems to be Solved &hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[45,46],"tags":[],"class_list":["post-351","post","type-post","status-publish","format-standard","hentry","category-bayes","category-statistics"],"_links":{"self":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/351","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/comments?post=351"}],"version-history":[{"count":14,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/351\/revisions"}],"predecessor-version":[{"id":420,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/351\/revisions\/420"}],"wp:attachment":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/media?parent=351"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/categories?post=351"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/tags?post=351"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}