
{"id":9096397,"date":"2017-03-23T20:27:15","date_gmt":"2017-03-24T06:27:15","guid":{"rendered":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/?p=9096397"},"modified":"2017-03-29T16:32:51","modified_gmt":"2017-03-30T02:32:51","slug":"hidden-markov-model-with-two-states","status":"publish","type":"post","link":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/hidden-markov-model-with-two-states\/","title":{"rendered":"Few paths, fewer words, and the maximum probability of writing 001 in a two-state Hidden Markov Model being $8\/27$"},"content":{"rendered":"<link rel  = \"stylesheet\" type = \"text\/css\" href = \"https:\/\/math.hawaii.edu\/~bjoern\/styles\/extra-style.css\"\/>\nThe aim of this note is to give the simplest possible non-trivial calculation of the parameters of a HMM that maximize the probability of emitting a certain string.<\/p>\n<p>Let $\\{0,1\\}$ be our alphabet.<br \/>\nLet $p$ be the probability of emitting 1 in state $s_0$.<br \/>\nLet $q$ be the probability of emitting 1 in state $s_1$.<br \/>\nLet $\\epsilon$ be the probability of transitioning from $s_0$ to $s_1$.<br \/>\nLet $\\delta$ be the probability of transitioning from $s_1$ to $s_0$.<br \/>\nLet $S(t)$ be the state after transitioning $t$ times, a random variable.<br \/>\nThe probability of emitting the string 001 when starting in state $s_0$ is then<br \/>\n$$<br \/>\nf(p,q,\\epsilon,\\delta)=\\Pr(001; S(1)=s_0=S(2))+\\Pr(001; S(1)=s_0, S(2)=s_1)$$<br \/>\n$$+\\Pr(001; S(1)=s_1, S(2)=s_0)+\\Pr(001; S(1)=s_1=S(2))$$<br \/>\n$$=\\overline p^2 p \\overline\\epsilon^2 + \\overline p^2q\\overline\\epsilon\\epsilon + \\overline p\\overline q p\\epsilon\\delta + \\overline p\\overline q q \\epsilon\\overline\\delta.<br \/>\n$$<br \/>\nWhich choice of parameters $p, q, \\epsilon, \\delta$ will maximize this probability?<br \/>\nTo answer this we first note that<br \/>\n$$\\frac{\\partial f}{\\partial\\delta}=0\\iff p=1, q=1, \\epsilon=0\\text{ or }p=q.$$<br \/>\nGoing through these possibilities we keep finding values of $f$ bounded above by $\\overline p^2p\\le 4\/27$:<\/p>\n<ol>\n<li>$p=1$ immediately gives $f=0$.<\/li>\n<li>$q=1$ gives $f=\\overline p^2 p \\overline\\epsilon^2 + \\overline p^2\\overline\\epsilon\\epsilon=\\overline p^2p\\overline\\epsilon.$<\/li>\n<li>$\\epsilon=0$ gives $f=\\overline p^2 p.$<\/li>\n<li>$p=q$ gives $f=\\overline p^2 p \\overline\\epsilon^2 + \\overline p^2p\\overline\\epsilon\\epsilon + \\overline p^2 p\\epsilon\\delta + \\overline p^2 p (\\epsilon\\overline\\delta)=\\overline p^2p(\\overline\\epsilon^2 + \\overline\\epsilon\\epsilon + \\epsilon\\delta +  \\epsilon\\overline\\delta)=\\overline p^2p.$<\/li>\n<\/ol>\n<p>We next consider boundary values for $\\delta$.<\/p>\n<ol>\n<li>$\\delta=0$. We may assume $p=0$, since there is no use in considering a positive probability of emitting a 1 in state $s_0$ if there is no chance of ever returning to that state. Then upon calculation of $\\partial f\/\\partial q$ we find that $\\epsilon=2\\overline q$, which gives $f=2q^2\\overline q$. This is maximized at $q=2\/3$ which corresponds to $\\epsilon=2\/3$ as well, and gives a value $f=8\/27>1\/4$.\n<p>This $8\/27$ is decomposable as a sum of two disjoint scenarios of probability $4\/27$:<\/p>\n<ol>\n<li>\nOne is that after writing the first 0 we stay in state $s_0$, write another 0, and then transition to state $s_1$ to write a 1.\n<\/li>\n<li>The other is that after writing the first 0 we move to state $s_1$, write the 2nd zero there, and stay there to write the 3rd letter, 1.<\/li>\n<\/ol>\n<\/li>\n<li>$\\delta=1$. Then $f=\\overline p^2 p \\overline\\epsilon^2 + \\overline p^2q\\overline\\epsilon\\epsilon + \\overline p\\overline q p\\epsilon<br \/>\n=\\overline p(\\overline p p \\overline\\epsilon^2 + \\overline pq\\overline\\epsilon\\epsilon +\\overline q p\\epsilon)$.<br \/>\nThen $0=\\partial f\/\\partial q = \\overline p\\epsilon(\\overline p\\overline\\epsilon &#8211; p)$ if $p=\\frac{\\overline\\epsilon}{1+\\overline\\epsilon}$. This gives $f=\\frac{\\overline\\epsilon}{(1+\\overline\\epsilon)^3}$ (turns out not to depend on $q$) which is maximized for $\\epsilon=1\/2$ with value $f=4\/27$. So we consider boundary values for $q$:<\/p>\n<ol>\n<li>$q=0$. Then $f=\\overline pp(\\overline p\\overline\\epsilon^2+\\epsilon)\\le \\frac14\\cdot 1$.\n<\/li>\n<li>$q=1$. Then $f=\\overline p^2p\\overline\\epsilon^2+\\overline p^2\\overline\\epsilon\\epsilon$ and $\\partial f\/\\partial\\epsilon=\\overline p^2(1-2\\epsilon-2p\\overline\\epsilon)=0$ if $\\overline p=1\/(2\\overline\\epsilon)$, which gives $f=\\overline p\/4\\le 1\/4$.\n<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<p>Now note how much easier this is if we only consider a single path. Then clearly $1\/4$ is the maximum possible, via 3 different paths, because of the presence of terms of the form $a\\overline a$.<br \/>\nReplacing such occurrences by $1\/4$ we upper bound $f$ by<br \/>\n$$\\frac14\\left(\\overline p \\overline\\epsilon^2 + \\overline p^2q + \\overline q\\epsilon\\delta + \\overline p \\epsilon\\overline\\delta\\right).<br \/>\n$$<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The aim of this note is to give the simplest possible non-trivial calculation of the parameters of a HMM that maximize the probability of emitting a certain string. Let $\\{0,1\\}$ be our alphabet. Let $p$ be the probability of emitting 1 in state $s_0$. Let $q$ be the probability of emitting 1 in state $s_1$. &hellip; <a href=\"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/hidden-markov-model-with-two-states\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Few paths, fewer words, and the maximum probability of writing 001 in a two-state Hidden Markov Model being $8\/27$<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":9096426,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[39],"tags":[],"class_list":["post-9096397","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-calculations"],"_links":{"self":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/9096397","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/comments?post=9096397"}],"version-history":[{"count":32,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/9096397\/revisions"}],"predecessor-version":[{"id":9096431,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/9096397\/revisions\/9096431"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/media\/9096426"}],"wp:attachment":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/media?parent=9096397"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/categories?post=9096397"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/tags?post=9096397"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}