|
==Example==
Consider for example a sequence of [[random variable]]s, each of which takes a value from the ternary [[alphabet]] {{math|{{mset|''a'', ''b'', ''c''}}}}. Specifically, consider the string ''{{not a typomath|aaabcaaabcaaabcaaabc...aaabc''aaabcaaabcaaabcaaabc…aaabc''}}'' constructed from infinite concatenations of the sub-string ''{{not a typomath|''aaabc''}}''.
The VOM model of maximal order 2 can approximate the above string using ''only'' the following five [[conditional probability]] components: {{math|Pr(''a'' |{{!}} ''aa'') {{=}} 0.5}}, {{math|Pr(''b'' |{{!}} ''aa'') {{=}} 0.5}}, {{math|Pr(''c'' |{{!}} ''b'') {{=}} 1.0}}, {{math|Pr(''a'' |{{!}} ''c''){{=}} 1.0}}, {{math|Pr(''a'' |{{!}} ''ca'') {{=}} 1.0}}.
In this example, {{math|Pr(''c''|{{!}}''ab'') {{=}} Pr(''c''|{{!}}''b'') {{=}} 1.0}}; therefore, the shorter context {{math|''b''}} is sufficient to determine the next character. Similarly, the VOM model of maximal order 3 can generate the string exactly using only five conditional probability components, which are all equal to 1.0.
To construct the [[Markov chain]] of order 1 for the next character in that string, one must estimate the following 9 conditional probability components: {{math|Pr(''a'' |{{!}} ''a'')}}, {{math|Pr(''a'' |{{!}} ''b'')}}, {{math|Pr(''a'' |{{!}} ''c'')}}, {{math|Pr(''b'' |{{!}} ''a'')}}, {{math|Pr(''b'' |{{!}} ''b'')}}, {{math|Pr(''b'' |{{!}} ''c'')}}, {{math|Pr(''c'' |{{!}} ''a'')}}, {{math|Pr(''c'' |{{!}} ''b'')}}, {{math|Pr(''c'' |{{!}} ''c'')}}. To construct the Markov chain of order 2 for the next character, one must estimate 27 conditional probability components: {{math|Pr(''a'' |{{!}} ''aa'')}}, {{math|Pr(''a'' |{{!}} ''ab'')}}, ...{{math|…}}, {{math|Pr(''c'' |{{!}} ''cc'')}}. And to construct the Markov chain of order three for the next character one must estimate the following 81 conditional probability components: {{math|Pr(''a'' |{{!}} ''aaa'')}}, {{math|Pr(''a'' |{{!}} ''aab'')}}, ...{{math|…}}, {{math|Pr(''c'' |{{!}} ''ccc'')}}.
In practical settings there is seldom sufficient data to accurately estimate the [[exponential growth|exponentially increasing]] number of conditional probability components as the order of the Markov chain increases.
|
