Как работают Яндекс.Рефераты?

Ну, я бы не стал противопоставлять марковские цепи и описанный в начале способ. И то, и то можно представить как марковские цепи, скорее всего они и используются.

Что-то вроде такого (навскидку, сырая гипотеза, конечно): для каждой тематики тренируется цепь на текстах из неё, с учетом стемминга, может быть отдельных состояний для учета частей речи и предложения, благо их немного и это только линейно увеличит число состояний. Порядок -- слов штук 5. Может еще навернули пару уровней для генерации сложноподчиненных предложений. Генерация текста происходит по натренированной цепи с модификатором выхода, учитывающим текущий (тренируемый или нет) род, падеж, whatever для данного словосочетания/подлежащего. Последнее - это, в принципе, шаг генерации выхода по скрытому состоянии HMM, т.е. с самого начала можно тренировать и эти параметры, но, наверное, не нужно.

Думаю, там основная работа - это не тренировка цепи, а ручной подбор множества состояний и правила для учета особых ситуаций, работа над качеством тренировочной выборки, и т.п. и т.д.