1
$\begingroup$

Looking at this video starting at 1:45, the author claims to be using a second-order approximation for a Markov text generation. He has one letter which he outputs followed by another letter which tells him which state to go to - so in other words, he might first pick AC, so he outputs A and then goes to state C, where he picks CB, so he outputs C and goes to state B, etc. So he has a uni-gram output followed by a uni-gram transition piece of information.

But from my understanding, a second-order approximation would be like this, with a bigram followed by a unigram as the "transition" state.

This is the same character-level order-2 n-gram analysis of the (very brief) text “condescendences” as above, but this time keeping track of all characters that follow each n-gram:

co n

on d

nd e, e

de s, n

es c, (end of text)

sc e

ce n, s

en d, c

nc e

The table above doesn’t just give us some interesting statistical data. It also allows us to reconstruct the underlying text—or, at least, generate a text that is statistically similar to the original text. Here’s how we’ll do it: (1) start with the initial n-gram (co)—those are the first two characters of our output. (2) Now, look at the last n characters of output, where n is the order of the n-grams in our table, and find those characters in the “n-grams” column. (3) Choose randomly among the possibilities in the corresponding “next” column, and append that letter to the output. (Sometimes, as with co, there’s only one possibility). (4) If you chose “end of text,” then the algorithm is over. Otherwise, repeat the process starting with (2).

I'm extremely confused because both these sources consider themselves to be of order 2 in approximation, but it seems to me that the second source is of a higher order than the first. Is this true, or am I just completely misunderstanding what's happening?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ N-Gram and Markov Order-N are different. N-Gram is the number of letters in the pattern (gram) with no statistical information about what might follow it. There is no 0-gram set of patterns.(well an empty set) . Where an Order-N Markov chain is the Number of dependent context that leads to symbol choices that follow it. IE: Order-0 Markov has no previous context, thus is just the Statics of the symbols to choose from. Order-1 Markov chain has 1 symbol of previous context and what choices follows it. Order-2 Markov chain has a 2-Gram and what symbol follows it ... $\endgroup$
    – Phillip Williams
    Jul 2, 2017 at 7:07
  • $\begingroup$ @PhillipWilliams thank you - but I'm curious why the first example (the video) he considers it second order. Shouldn't that be first order? $\endgroup$
    – rb612
    Jul 2, 2017 at 8:27
  • 1
    $\begingroup$ What some people call order 1, other people call order 2. $\endgroup$
    – Yuval Filmus
    Jul 2, 2017 at 9:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.