Exact computation of distributions by means of Markov chains.pdf Для построения статистических критериев с заданными вероятностями ошибоктребуется знание распределений используемых в этих критериях статистик. Как пра-вило, точные формулы слишком громоздки с вычислительной точки зрения. Поэто-му вместо точных формул в качестве приближений часто используют формулы изсоответствующих предельных теорем, относящихся к случаям, когда объём выборкинеограниченно возрастает. Зависимость точности таких формул от объёма выборкиобычно оценивается лишь по порядку. Поэтому представляют интерес методы точно-го вычисления распределений статистик для выборок умеренного объёма.В нескольких работах авторов было показано, что в различных комбинаторно-ве-роятностных схемах можно строить предназначенные для реализации на ЭВМ алго-ритмы точного вычисления распределений различных статистик с помощью аппаратанеоднородных по времени цепей Маркова.Так, в [1, 2] предложен способ вычисления распределений так называемых раздели-Nмых статистик в полиномиальной схеме, имеющих вид Z = Е /fc(vfc), где v i , . . . , VN -fc=iчисла появлений исходов 1 , . . . , N с вероятностями а1 , . . . , aN в T независимых ис-пытаниях, а /1 ( x ) , . . . , /N (x) -заданные функции. Примерами разделимых статистикNявляются статистика Пирсона х = Е (vfc - Tp^ )2/Tp&, где p 1 , . . . , PN - гипотетическиеk=1вероятности исходов, а также число исходов, не появившихся ни разу, числоисходов, появившихся ровно r ^ 1 раз, и т. п.nСпособ основан на том, что последовательность an = Е Vfc, n = 0 , 1 , . . . , N, обра-fc=1зует (неоднородную по времени) цепь Маркова с переходными вероятностямиP K = s +m | CTn-1 = s} = CT_s. . ч T-s-mm i -n i i an+1 + . . . + a Nan + an+1 + . . . + aN / \an + an+1 + . . . + aNа последовательность сумм Zn = E /fc(vfc), n = 0 , 1 , . . . , N , является аддитив-fc=1ным функционалом от траектории цепи {an } . Поэтому последовательность En == (an, Zn), n = 0 , 1 , . . . , N, тоже является дискретной цепью Маркова с переходнымивероятностямиP ( E n = (s + m, z + /n(m)) | En = (s, z ) } = P { a n = s + m | an-1 = s}.Это позволяет рекуррентно находить распределения E1, E 2 , . . . , En обычным умноже-нием векторов распределений на матрицы переходных вероятностей. Распределение Znсовпадает с искомым распределением разделимой статистики Z.В [4, 5] приведены результаты численного исследования распределений статисти-ки Пирсона для схем с числом исходов до нескольких сотен и числом испытаний донескольких тысяч. Эксперименты обнаружили неожиданные отличия точных распре-делений от их обычно используемых аппроксимаций. Игнорирование этих отличий мо-жет приводить к принятию неправильных решений из-за некорректной интерпретациирезультатов статистической обработки данных.В [3] описан более сложный способ построения цепей Маркова, позволяющих нахо-дить распределения чисел связных компонент и циклических точек в графах случай-ных равновероятных отображений множества из N элементов и в графах итерацийдвух таких отображений. Результаты вычислений для N ^ 2000 показали, что при та-ких N точность приближений, полученных с помощью предельных теорем, невелика.

Скачать электронную версию публикации