Asymptotic properties of characterization-based symmetry and agreement tests. Asymptotically optimal Criteria based on the number of cells in generalized layouts

Object of research and relevance of the topic. In the theory of statistical analysis of discrete sequences, a special place is occupied by goodness-of-fit tests for testing a possibly complex null hypothesis, which is that for a random sequence such that

Xi e hi,i = 1, ,n, where hi = (0,1,. ,M), for any i = 1,.,n, and for any k £ 1m the probability of the event

Xi = k) does not depend on r. This means that the sequence is in some sense stationary.

In a number of applied problems, the sequence (Xr-)™ = 1 is considered to be a sequence of colors of balls when choosing without returning until exhaustion from an urn containing n - 1 > 0 balls of color k, k € 1m - We will denote the set of such selections O(n0 - 1, .,pm - 1). Let there be a total of n - 1 balls in the urn, m k=0

Let us denote by r(k) (fc) Jk) rw - Г! , . . . , sequence of numbers of balls of color A; in the sample. Consider the sequence where k)

Kk-p-GPk1.

The sequence h^ is defined using the distances between the locations of adjacent balls of color k in such a way that

Pk Kf = p. 1>=1

The set of sequences h(fc) for all k £ 1m uniquely determines the sequence. Sequences hk for different k are dependent on each other. In particular, any of them is uniquely determined by all the others. If the cardinality of the set 1m is 2, then the sequence of colors of balls is uniquely determined by the sequence of distances between the places of neighboring balls of the same fixed color. Let there be N - 1 balls of color 0 in an urn containing n - 1 balls of two different colors. We can establish a one-to-one correspondence between the set ffl(N- l,n - N) and the set 9\n,N vectors h(n, N ) = (hi,., hjf) with positive integer components such that K = P. (0.1)

The set 9П)дг corresponds to the set of all different partitions of a positive integer n into N ordered terms.

Having specified a certain probability distribution on the set of vectors £Hn,dr, we obtain the corresponding probability distribution on the set Wl(N - 1,n - N). A set is a subset of a set of vectors with non-negative integer components satisfying (0.1). Distributions of the form will be considered as probability distributions on a set of vectors in the dissertation work

P(%,N) = (n,.,rN)) = P(£„ = ru,v = l,.,N\jr^ = n), (0.2) where. ,£dr - independent non-negative integer random variables.

Distributions of the form (0.2) in /24/ are called generalized schemes for placing n particles in N cells. In particular, if the random variables £b. ,£lg in (0.2) are distributed according to Poisson’s laws with parameters Ai,., Ldr respectively, then the vector h(n,N) has a polynomial distribution with the probabilities of outcomes

Ri = . , L" ,V = \,.,N.

L\ + . . . + AN

If the random variables £ь >&v in (0-2) are identically distributed according to the geometric law where p is any in the interval 0< р < 1, то, как отмечено в /25/,/26/, получающаяся обобщенная схема размещения соответствует равномерному распределению на множестве В силу взаимнооднозначного соответствия между множеством dft(N - 1 ,п - N) и множеством tRn,N получаем равномерное распределение на множестве выборов без возвращения. При этом, вектору расстояний между местами шаров одного цвета взаимно однозначно соответствует вектор частот в обобщенной схеме размещения, и, соответственно, числу расстояний длины г - число ячеек, содержащих ровно г частиц. Для проверки по единственной последовательности гипотезы о том, что она получена как результат выбора без возвращения, и каждая такая выборка имеет одну и ту же вероятность можно проверить гипотезу о том, что вектор расстояний между местами шаров цвета 0 распределен как вектор частот в соответствующей обобщенной схеме размещения п частиц по N ячейкам.

As noted in /14/, /38/, a special place in testing hypotheses about the distribution of frequency vectors h(n, N) = (hi,., /gdr) in generalized schemes for placing n particles in N cells is occupied by criteria based on based on statistics of the form 1 m(N -l,n-N)\ N

LN(h(n,N))=Zfv(hv)

Фн = Ф(-Т7, flQ Hi II-

0.4) where fu, v = 1,2,. and φ - some real-valued functions, N

Mr = E = r), r = 0.1,. 1/=1

The quantities in /27/ were called the number of cells containing exactly g particles.

Statistics of the form (0.3) in /30/ are called separable (additively separable) statistics. If the functions /„ in (0.3) do not depend on u, then such statistics were called in /31/ symmetric separable statistics.

For any r the statistic /xr is a symmetric separable statistic. From equality

E DM = E DFg (0.5) it follows that the class of symmetric separable statistics of hv coincides with the class of linear functions of fir. Moreover, the class of functions of the form (0.4) is wider than the class of symmetric separable statistics.

But = (#o(n, N)) is a sequence of simple null hypotheses that the distribution of the vector h(n, N) is (0.2), where the random variables are,. in (0.2) are identically distributed and k) = pk,k = 0,1,2,., the parameters n, N change in the central region.

Consider some P £ (0,1) and a sequence of, generally speaking, complex alternatives

H = (H(n, N)) such that exists - the maximum number for which, for any simple hypothesis H\ € H(n, N), the inequality holds

РШ > an,N(P)) > Р

We will reject the hypothesis Hq(ti,N) if fm > asm((3). If there is a limit

Шп ~1пР(0н > an,N(P))=u(p,Н), where the probability for each N is calculated under the hypothesis Нк(п, N), then the value ^(/З, Н) is named in /38/ index of the criterion φ at the point (j3, H). The last limit may, generally speaking, not exist. Therefore, in the dissertation work, in addition to the criterion index, the value is considered

Ish (~1pP(fm > al(/?)))

JV->oo N-ooo mean, respectively, the lower and upper limits of the sequence (odg) for N -> oo,

If a criterion index exists, then the criterion's subscript coincides with it. The lower index of the criterion always exists. The higher the value of the criterion index (subscript of the criterion), the better the statistical criterion in the sense under consideration. In /38/, the problem of constructing goodness-of-fit criteria for generalized layouts with the highest value of the criterion index in the class of criteria that reject the hypothesis Ho(n,N) at /MO Ml Mt MS iV" iV""""" ~yv" " was solved ^ "where m > 0 is some fixed number, the sequence of constant edg is selected based on the given value of the power of the criterion for the sequence of alternatives, ft is a real function of m + 1 arguments.

The criterion indices are determined by the probabilities of large deviations. As was shown in /38/, the rough (up to logarithmic equivalence) asymptotics of the probabilities of large deviations of separable statistics when Cramer’s condition is satisfied for the random variable /(ξ) is determined by the corresponding Kull-Bak-Leibler-Sanov information distance (the random variable rj satisfies the condition Cramer, if for some R > 0 the moment generating function Metr] is finite in the interval \t\< Н /28/).

The question of the probabilities of large deviations of statistics from an unlimited number of fir, as well as arbitrary separable statistics that do not satisfy the Cramer condition, remained open. This did not allow us to finally solve the problem of constructing criteria for testing hypotheses in generalized placement schemes with the highest rate of tending to zero of the probability of an error of the first kind with non-approaching alternatives in the class of criteria based on statistics of the form (0.4). The relevance of the dissertation research is determined by the need to complete the solution to the specified problem.

The purpose of the dissertation work is to construct goodness-of-fit criteria with the highest value of the criterion index (subscript of the criterion) for testing hypotheses in a selection scheme without return in the class of criteria that reject the hypothesis U(n, N) for $.<>,■ ■)><*. (0-7) где ф - функция от счетного количества аргументов, и параметры п, N изменяются в центральной области.

In accordance with the purpose of the study, the following tasks were set:

Investigate the properties of entropy and information distance Kull-Bak - Leibler - Sanov for discrete distributions with a countable number of outcomes;

Investigate the probabilities of large deviations of statistics of the form (0.4);

Investigate the probabilities of large deviations of symmetric separable statistics (0.3) that do not satisfy the Cramer condition;

Find a statistic such that the goodness-of-fit criterion constructed on its basis for testing hypotheses in generalized layouts has the highest index value in the class of criteria of the form (0.7).

Scientific novelty:

Scientific and practical value. The work solves a number of questions about the behavior of the probabilities of large deviations in generalized placement schemes. The results obtained can be used in the educational process in the specialties of mathematical statistics and information theory, in the study of statistical procedures for the analysis of discrete sequences, and were used in /3/, /21/ to justify the security of one class of information systems. Provisions for defense:

Reducing the problem of testing, based on a single sequence of ball colors, the hypothesis that this sequence is obtained as a result of a choice without returning until the balls are exhausted from an urn containing balls of two colors, and each such choice has the same probability, to the construction of goodness-of-fit criteria for testing hypotheses in the corresponding generalized layout;

Continuity of the entropy and Kullback-Leibler-Sanov information distance functions on an infinite-dimensional simplex with the introduced logarithmic generalized metric;

A theorem on the rough (up to logarithmic equivalence) asymptotics of the probabilities of large deviations of symmetric separable statistics that do not satisfy the Cramer condition in the generalized placement scheme in the semi-exponential case;

Theorem on rough (up to logarithmic equivalence) asymptotics of the probabilities of large deviations for statistics of the form (0.4);

Construction of a goodness-of-fit criterion for testing hypotheses in generalized layouts with the highest index value in the class of criteria of the form (0.7).

Approbation of work. The results were presented at seminars of the Department of Discrete Mathematics of the Mathematical Institute named after. V. A. Steklov RAS, information security department of ITM&VT named after. S. A. Lebedev RAS and at:

Fifth All-Russian Symposium on Applied and Industrial Mathematics. Spring session, Kislovodsk, May 2 - 8, 2004;

Sixth International Petrozavodsk Conference "Probabilistic methods in discrete mathematics" June 10 - 16, 2004;

Second International Conference "Information Systems and Technologies (IST" 2004)", Minsk, November 8-10, 2004;

International conference "Modern Problems and new Trends in Probability Theory", Chernivtsi, Ukraine, June 19 - 26, 2005.

The main results of the work were used in the research work "Apology", carried out by ITMiVT RAS. S. A. Lebedev in the interests of the Federal Service for Technical and Export Control of the Russian Federation, and were included in the report on the implementation of the research stage /21/. Some results of the dissertation were included in the research report "Development of mathematical problems of cryptography" of the Academy of Cryptography of the Russian Federation for 2004 /22/.

The author expresses deep gratitude to the scientific supervisor, Doctor of Physical and Mathematical Sciences A. F. Ronzhin and the scientific consultant, Doctor of Physical and Mathematical Sciences, Senior Researcher A. V. Knyazev. The author expresses gratitude to Doctor of Physical and Mathematical Sciences, Professor A. M. Zubkov and Candidate of Physical and Mathematical Sciences Mathematical Sciences I. A. Kruglov for his attention to the work and a number of valuable comments.

Structure and content of the work.

The first chapter examines the properties of entropy and information distance for distributions on the set of non-negative integers.

In the first paragraph of the first chapter, notations are introduced and the necessary definitions are given. In particular, the following notation is used: x = (xq,x\, . ) - an infinite-dimensional vector with a countable number of components;

H(x) - -Ex^oXvlnx,-, truncm(x) = (x0,x1,.,xm,0,0,.)] f2* = (x, xi > 0, zy = 0.1,. , Oh"< 1}; Q = {х, х, >0,u = 0.1,., o xv = 1); = (x G O, ££L0 = 7);

Ml = o Ue>1|5 € o< Ml - 7МГ1 < 00}. Понятно, что множество £1 соответствует семейству вероятностных распределений на множестве неотрицательных целых чисел, П7 - семейству вероятностных распределений на множестве неотрицательных целых чисел с математическим ожиданием 7.

If y 6E P, then for e > 0 the set will be denoted by Oe(y)

Oe(y) - (x^< уие£ для всех v = 0,1,.}.

In the second paragraph of the first chapter, a theorem on the boundedness of the entropy of discrete distributions with limited mathematical expectation is proved.

Theorem 1. On the boundedness of the entropy of discrete distributions with bounded mathematical expectation.

For any 6 P7

H(x)

If x € fly corresponds to a geometric distribution with a mathematical definition of 7, that is, 7 x„ = (1- р)р\ v = 0.1,., where р = --,

1 + 7 then the equality holds

H(x) = F(<7).

The statement of the theorem can be viewed as the result of a formal application of the Lagrange method of conditional multipliers in the case of an infinite number of variables. The theorem that the only distribution on the set (k, k + 1, k + 2,.) with a given mathematical expectation and maximum entropy is a geometric distribution with a given mathematical expectation is given (without proof) in /47/. The author, however, has given strict proof.

The third paragraph of the first chapter gives the definition of a generalized metric - a metric that allows infinite values.

For x,y € Q the function p(x,y) is defined as the minimal e > O with the property yie~£<хи< уиее для всех и = 0,1,. Если такого е не существует, то полагается, что р(х,у) = оо.

It is proved that the function p(x,y) is a generalized metric on the family of distributions on the set of non-negative integers, as well as on the entire set Cl*. Instead of e in the definition of the metric p(x,y), you can use any other positive number other than 1. The resulting metrics will differ by a multiplicative constant. Let us denote by J(x, y) the information distance

00 £ J(x,y) = E In-.

Here and below it is assumed that 0 In 0 = 0.0 In jj = 0. The information distance is defined for such x, y that x„ = 0 for all and such that y = 0. If this condition is not met, then we will assume J(x,ij) = oo. Let L SP. Then we will denote

J (A Y) = |nf J(x,y).

The fourth paragraph of the first chapter gives the definition of compactness of functions defined on the set Q*. The compactness of a function with a countable number of arguments means that with any degree of accuracy the value of the function can be approximated by the values ​​of this function at points where only a finite number of arguments are non-zero. The compactness of the entropy and information distance functions is proved.

1. For any 0< 7 < оо функция Н(х) компактна на

2. If for some 0< 70 < оо

R e then for any 0<7<оо,г>0 the function x) = J(x,p) is compact on the set

The fifth paragraph of the first chapter discusses the properties of the information distance defined on an infinite-dimensional space. Compared to the finite-dimensional case, the situation with the continuity of the information distance function changes qualitatively. It is shown that the information distance function is not continuous on the set in any of the metrics

Pl&V) = E\Xi~Y»\, u=0

E (xv - Ui)2 v=Q

Рз(х,у) = 8Up\xu-yv\. v

The validity of the following inequalities is proved for the entropy functions H(x) and information distance J(x,p):

1. For any x, x" € fi

N(x) - N(x")\< - 1){Н{х) + Н{х")).

2. If for some x,p e P there exists e > 0 such that x 6 0 £(p), then for any x" £ Q J(x,p) - J(x",p)|< (е"М - 1){Н{х) + Н{х") + ееН(р)).

From these inequalities, taking into account Theorem 1, it follows that the entropy and information distance functions are uniformly continuous on the corresponding subsets of Q in the metric p(x,y)t, namely,

1. For any 7 such that 0< 7 < оо, функция Н(х) равномерно непрерывна на Г2 в метрике р(ж,у);

2. If for some 70, 0< 70 < оо

TO for any 0<7<оои£>0 function

L p(x) = J(x,p) is uniformly continuous on the set Π Oe(p) in the metric p(x,y).

A definition of non-extremal function is given. The non-extremal condition means that the function does not have local extrema, or the function takes the same values ​​at local minima (local maxima). The non-extrema condition weakens the requirement of the absence of local extrema. For example, the function sin x on the set of real numbers has local extrema, but satisfies the non-extremal condition.

Let for some 7 > 0, the region A is given by the condition

A = (x € VLv4>(x) > a), (0.9) where φ(x) is a real-valued function, a is some real constant, inf φ(x)< а < inf ф(х).

The question was studied under what conditions on the function φ when changing the parameters n,N in the central region, ^ -; 7, for all sufficiently large values ​​there are non-negative integers ko, k\,., kn such that k0 + ki + . + kn = N, k\ + 2k2. + control panel - N and

F(ko k\ kp

-£,0,0 ,.)>a.

It is proved that for this it is sufficient to require that the function φ be non-extremal, compact and continuous in the metric p(x,y), and also that for at least one point x satisfying (0.9), for some e > 0 there exists a finite moment degrees 1 + e and x„ > 0 for any v = 0.1.

In the second chapter, we study the rough (up to logarithmic equivalence) asymptotics of the probability of large deviations of functions from D = (^0) ■ ) Ts "n, 0, .) - the number of cells with a given filling in the central region of change of parameters N, n. Rough The asymptotics of the probabilities of large deviations are sufficient to study the indices of the agreement criteria.

Let the random variables ^ in (0.2) be identically distributed and

P(z) - generating function of a random variable - converges in a circle of radius 1< R < оо. Следуя /38/, для 0 < z < R обозначим через £(z) случайную величину такую, что

Ml+£ = £ i1+ex„< 00.

0.10) k] = Pk, k = 0.1,.

Let's denote

If there is a solution to the equation m Z(z) = ъ then it is unique /38/. Throughout what follows we will assume that pk > O,A; = 0.1,.

The first paragraph of the first paragraph of the second chapter contains the asymptotics of logarithms of probabilities of the form

1pP(/x0 = ko,.,tsp = kp).

The following theorem is proved.

Theorem 2. Rough local theorem on the probabilities of large deviations. Let n, N -» oo so that jj ->7.0<7 < оо, существует z7 - корень уравнения M£(z) = 7, с. в. £(г7) имеет положительную дисперсию. Тогда для любого k G Cl(n,N)

1nP(D = k) = JftpK)) + O(^lniV).

The statement of the theorem follows directly from the formula for the joint distribution fii,. fin in /26/ and the following estimate: if non-negative integer values ​​, Нп satisfy the condition

Hi + 2d2 + + PNn = n, then the number of non-zero values ​​among them is 0(l/n). This is a rough estimate and does not claim to be new. The number of non-zero CGs in generalized layout schemes does not exceed the value of the maximum filling of cells, which in the central region, with a probability tending to 1, does not exceed the value O(lnn) /25/, /27/. Nevertheless, the resulting estimate 0(y/n) is satisfied with probability 1 and is sufficient to obtain rough asymptotics.

In the second paragraph of the first paragraph of the second chapter, the value of the limit is found where adg is a sequence of real numbers converging to some a G R, φ(x) is a real-valued function. The following theorem is proved.

Theorem 3. Rough integral theorem on the probabilities of large deviations. Let the conditions of Theorem 2 be satisfied, for some r > 0, C > 0 the real function φ(x) is compact and uniformly continuous in the metric p on the set

A = 0r+<;(p(z7)) П Ц7+с] и удовлетворяет условию неэкстремальности на множестве fly. Если для некоторой константы а такой, что inf ф(х) < а < sup ф(х). xeily существует вектор ра € fi7 П 0r(p(z7)); такой, что

Ф(ra) > a and j(( (x) >a,xe P7),p(2;7)) = 7(pa,p(*y)) mo for any sequence a^ converging to a,