, 1

Московский инженерно-физический институт (государственный университет)

1Математический институт им. РАН, Москва

Алгоритм точного вычисления допредельного распределения статистики Пирсона
для равновероятной полиномиальной схемы

В данной работе рассматривается реализация алгоритма точного вычисления допредельных распределений статистик на примере статистики Пирсона для равновероятной схемы, приводятся временные характеристики работы алгоритма.

В работах [1 - 2] описаны способы вычисления допредельных распределений целочисленных разделимых статистик для произвольных полиномиальных схем. Эти способы были использованы в программах, реализующих точное вычисление распределения статистики Пирсона для равновероятной полиномиальной схемы с N исходами. Пусть - частоты исходов в n испытаниях. Статистика Пирсона имеет вид:

,

где обозначает ближайшее целое к x. Эта формула сводит вычисление распределения статистики Пирсона к вычислению распределения целочисленной разделимой статистики . Его можно найти, проводя последовательные вычисления вероятностей по рекуррентной формуле

,

где , , ,.

Для точной реализации вычислений по приведенной схеме требуется разместить в оперативной памяти две таблицы размером . Но вероятности значений статистики Пирсона, далеких от ее среднего, пренебрежимо малы, поэтому на практике можно ограничиться вычислением вероятностей лишь для существенной части значений статистики Пирсона, что позволяет сократить как время вычисления, так и объем занимаемой оперативной памяти, сохраняя при этом необходимую точность.

Приведем временные характеристики этого алгоритма, полученные для программной реализации на языке C++. Расчеты производились на компьютере Pentium IV с частотой процессора 3 ГГц и объемом оперативной памяти 1 Гб. В таблице приведено время вычисления (в секундах) распределения статистики Пирсона при заданных параметрах.

n/N

1

2

3

4

5

6

7

8

9

10

N

10

0

0

0.015

0.047

0.078

0.188

0.343

0.61

0.937

1.36

20

0.015

0.078

0.375

1.157

2.703

3.734

4.641

5.781

6.891

7.734

30

0.047

0.531

2.563

5.125

7.078

9.11

11.312

13.688

16.015

18.563

40

0.156

2.031

6.375

9.594

13.328

17.25

21.641

26.172

31.297

36.765

50

0.516

6.109

11.11

16.625

22.734

29.406

37.297

45.828

55.157

64.734

60

1.141

9.671

16.954

25.343

35.141

46.5

59.437

72.5

86.735

139.422

70

2.218

13.704

23.906

36.39

52

68.813

86.844

148.578

172.531

196.859

80

4.047

18.313

32.203

50.766

71.687

94.75

169.922

200.172

231.484

262.266

90

7.172

23.593

42.891

67.578

95.844

125.281

220.719

260.547

301.25

341.312

100

11.375

29.953

56.016

88.234

123.235

229.828

279.922

328.625

376.765

424.485

Таким образом, данный алгоритм позволяет вычислять распределение статистики Пирсона для количества исходов порядка нескольких сотен.

В дальнейшем планируется разработка и реализация алгоритмов вычисления распределений различных разделимых статистик в неравновероятных схемах.

Список литературы

1.  Зубков формулы для распределений функционалов от дискретных случайных величин // Обозрение прикладной и промышленной математики, 1996. Т. 3, вып. 4. С. 256-573.

2.  Зубков расчета распределений сумм случайных величин // Труды по дискретной математике, Т. 5. М.: Физматлит, 2002. С. 51-60.