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:
nd e, e
de s, n
es c, (end of text)
ce n, s
en d, c
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?