{"id":120,"date":"2025-11-26T11:02:32","date_gmt":"2025-11-26T16:02:32","guid":{"rendered":"https:\/\/www.clarku.edu\/mathematics\/?p=120"},"modified":"2025-12-09T12:02:36","modified_gmt":"2025-12-09T17:02:36","slug":"counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms","status":"publish","type":"post","link":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/","title":{"rendered":"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms"},"content":{"rendered":"\n<p class=\"is-style-default\"><strong>Trung Ngo<\/strong><\/p>\n\n\n<div style=\"color:inherit\" class=\"eyebrow  has-text-align-left\">Mentor: Michael Satz<\/div>\n\n\n\n<p class=\"has-small-font-size\">Can you imagine a set that is finite but impossible to practically count even with a supercomputer? One way to build such a set is to define it as a subset all permutations of the integers 1 through N. The hard-to-count set may not be particularly large, but the parent set (which has N! elements) may well be too large for an exhaustive check-and-count approach. Monte-Carlo Markov chain methods introduce randomness to estimate the sizes and other features of such complicated combinatorial sets. Trung Ngo applied four algorithms to one such counting problem. The algorithms were implemented in Python and tested and analyzed for performance, convergence, and accuracy.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Trung Ngo Can you imagine a set that is finite but impossible to practically count even with a supercomputer? One way to build such a set is to define it as a subset all permutations of the integers 1 through N. The hard-to-count set may not be particularly large, but the parent set (which has [&hellip;]<\/p>\n","protected":false},"author":15,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_links_to":"","_links_to_target":""},"categories":[8],"tags":[],"class_list":["post-120","post","type-post","status-publish","format-standard","hentry","category-student-research"],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v28.1 (Yoast SEO v28.5) - https:\/\/yoast.com\/product\/yoast-seo-premium-wordpress\/ -->\n<title>Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms | Mathematics | Clark University<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms\" \/>\n<meta property=\"og:description\" content=\"Trung Ngo Can you imagine a set that is finite but impossible to practically count even with a supercomputer? One way to build such a set is to define it as a subset all permutations of the integers 1 through N. The hard-to-count set may not be particularly large, but the parent set (which has [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/\" \/>\n<meta property=\"og:site_name\" content=\"Mathematics\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/ClarkUniversityWorcester\" \/>\n<meta property=\"article:published_time\" content=\"2025-11-26T16:02:32+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-12-09T17:02:36+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@clarkuniversity\" \/>\n<meta name=\"twitter:site\" content=\"@clarkuniversity\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Jordan Aubin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\\\/\"},\"headline\":\"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms\",\"datePublished\":\"2025-11-26T16:02:32+00:00\",\"dateModified\":\"2025-12-09T17:02:36+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\\\/\"},\"wordCount\":118,\"articleSection\":[\"Student Research\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\\\/\",\"url\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\\\/\",\"name\":\"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms | Mathematics | Clark University\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/#website\"},\"datePublished\":\"2025-11-26T16:02:32+00:00\",\"dateModified\":\"2025-12-09T17:02:36+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/#\\\/schema\\\/person\\\/73c3626fe9ff937cd35eb2269f0ed7a2\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/wp-json\\\/wp\\\/v2\\\/posts\\\/120#breadcrumbs\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":0,\"name\":\"ClarkU\",\"item\":\"https:\\\/\\\/www.clarku.edu\\\/\"},{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Mathematics\",\"item\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/#website\",\"url\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/\",\"name\":\"Mathematics\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.clarku.edu\\\/mathematics\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms | Mathematics | Clark University","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/","og_locale":"en_US","og_type":"article","og_title":"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms","og_description":"Trung Ngo Can you imagine a set that is finite but impossible to practically count even with a supercomputer? One way to build such a set is to define it as a subset all permutations of the integers 1 through N. The hard-to-count set may not be particularly large, but the parent set (which has [&hellip;]","og_url":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/","og_site_name":"Mathematics","article_publisher":"https:\/\/www.facebook.com\/ClarkUniversityWorcester","article_published_time":"2025-11-26T16:02:32+00:00","article_modified_time":"2025-12-09T17:02:36+00:00","twitter_card":"summary_large_image","twitter_creator":"@clarkuniversity","twitter_site":"@clarkuniversity","twitter_misc":{"Written by":"Jordan Aubin","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/#article","isPartOf":{"@id":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/"},"headline":"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms","datePublished":"2025-11-26T16:02:32+00:00","dateModified":"2025-12-09T17:02:36+00:00","mainEntityOfPage":{"@id":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/"},"wordCount":118,"articleSection":["Student Research"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/","url":"https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/","name":"Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms | Mathematics | Clark University","isPartOf":{"@id":"https:\/\/www.clarku.edu\/mathematics\/#website"},"datePublished":"2025-11-26T16:02:32+00:00","dateModified":"2025-12-09T17:02:36+00:00","author":{"@id":"https:\/\/www.clarku.edu\/mathematics\/#\/schema\/person\/73c3626fe9ff937cd35eb2269f0ed7a2"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.clarku.edu\/mathematics\/counting-complicated-combinatorial-sets-using-markov-chain-monte-carlo-algorithms\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/posts\/120#breadcrumbs","itemListElement":[{"@type":"ListItem","position":0,"name":"ClarkU","item":"https:\/\/www.clarku.edu\/"},{"@type":"ListItem","position":1,"name":"Mathematics","item":"https:\/\/www.clarku.edu\/mathematics"}]},{"@type":"WebSite","@id":"https:\/\/www.clarku.edu\/mathematics\/#website","url":"https:\/\/www.clarku.edu\/mathematics\/","name":"Mathematics","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.clarku.edu\/mathematics\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"fimg_url":false,"_links":{"self":[{"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/posts\/120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/users\/15"}],"replies":[{"embeddable":true,"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/comments?post=120"}],"version-history":[{"count":5,"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/posts\/120\/revisions"}],"predecessor-version":[{"id":192,"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/posts\/120\/revisions\/192"}],"wp:attachment":[{"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/media?parent=120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/categories?post=120"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.clarku.edu\/mathematics\/wp-json\/wp\/v2\/tags?post=120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}