# Calculation of Precise Constants in a Probability Model of Zipf’s Law Generation and Asymptotics of Sums of Multinomial Coefficients

Authors: Vladimir Bochkarev; Eduard Lerner
Journal: International Journal of Mathematics and Mathematical Sciences
 (2017)

---

## Abstract

Letω0,ω1,…,ωn be a full set of outcomes (symbols) and let positive pi, i=0,…,n, be their probabilities (∑i=0npi=1). Let us treat ω0 as a stop symbol; it can occur in sequences of symbols (we call them words) only once, at the very end. The probability of a word is defined as the product of probabilities of its symbols. We consider the list of all possible words sorted in the nonincreasing order of their probabilities. Let pr be the probability of the rth word in this list. We prove that if at least one of the ratios log⁡pi/log⁡pj, i,j∈1,…,n, is irrational, then the limit limr→∞pr/r-1/γ exists and differs from zero; here γ is the root of the equation ∑i=1npiγ=1. The limit constant can be expressed (rather easily) in terms of the entropy of the distribution (p1γ,…,pnγ).


---

## Body

## 1. Introduction: The Statement of the Main Theorem

### 1.1. Brief Literature Overview

The wide presence of power laws in real networks, biology, economics, and linguistics can be explained in the framework of various mathematical models (see, e.g., [1, 2]). According to Zipf’s law [3], in a list of word forms ordered by the frequency of occurrence, the frequency of the rth word form obeys a power function of r (the value r is called the rank of the word form). One can easily explain this law with the help of the so-called monkey model.Recall that the word forms “the”; “of”; and “and” are used most frequently in English texts. According to Zipf’s law, the word “the” is used in the texts twice as much as “of” and three times as much as “and”; in other words the word form occurrence frequency obeys the power function of rankr (the position number of the word form in an ordered frequency list) whose exponent is approximately -1. It should be noted that further surveys showed that Zipf’s law is roughly realised only for the most frequent words. At present, the researches try to describe the main part of the lexicon using the power law with an exponent -α, where α>1. Zipf explained his law on the basis of the principle of least effort. In accordance with this principle, the authors aim to minimise the length of the text, which is required to convey their thoughts, even if this introduces ambiguities. On the other hand, readers want to minimize the effort required to understand the text [4].Another explanation of Zipf’s law was suggested by Mandelbrot who slightly modified the law by introducing translation constant [5] into the argument of the power function. The important thing for our case is that later he hypothesized the existence of more simple explanation of the Zipf law associated with a simple probability model when all symbols in the text (including white-space) appear independently of each other with certain probability. Moreover, he analysed the Markovian dependence between these symbols and wrote out the correct (in a typical case) formula on the basis of special cases to determine the parameter α by the transition probabilities matrix in the Markov model [6].First, we will consider the model thoroughly described by Miller [7] and Li [8] for a special case of Mandelbrot’s experiment in which the monkey types the keys with uniform probability. To learn some other important references on the monkey model, we recommend to read the recent article by Richard Perline and Ron Perline [9] (see also references in the next subsection).


### 1.2. Statement of the Main Theorem and Its Connection with Other Results

Assume that a monkey types any of 26 Latin letters or the space on a keyboard with the same probability of1/27. We understand a word as a sequence of symbols typed by the monkey before the space. Let us sort the list of possible words with respect to probabilities of their occurrence (the empty word, whose probability equals 1/27, will go first in this list followed by 26 one-letter words whose probabilities equal 1/272 and then by 262 possible two-letters words and so on). We can prove (see [7, 8]) that the probability p(r) of a word with the rank of r satisfies the inequality(1)c1r-α<pr<c2r-α,where α=log⁡27/log⁡26 and c1,c2>0 (here and below we use the symbol log if the base of the logarithm is not significant; but for the natural logarithm we use the symbol ln).Relatively recently inequality (1) was generalized to the case of nonequiprobable letters. Let p0 be the probability that the monkey types the space, let pi, i=1,…,n, denote probabilities of choosing the ith letter from the set of n letters (pi>0, ∑i=0npi=1), and let pr be, as above, the probability of a word with a rank of r. Then, as is proved in [10, 11], the following inequality analogous to (1) takes place; namely, ∃c1,c2:0<c1<c2, such that(2)c1r-α<pr<c2r-α,whereα=1γand γ is the root of the equation ∑i=1npiγ=1 (evidently, 0<γ<1). Note that inequality (2) is equivalent to the boundedness of the difference -log⁡pr-αlog⁡r.In the case when the probability of each letter is not fixed but depends on the previous one, words represent trajectories of a Markov chain with the absorbing stateω0 and transient states ω1,…,ωn. Then the value p(r) is the probability of the rth trajectory in the list of possible trajectories sorted in the nonincreasing order of probabilities. In this case, the asymptotic behavior of p(r) does not necessarily have a power order. Namely, in this case one of the two alternatives takes place [12, 13]. The first variant is that there exists the limit(3)limr→∞-log⁡prr1/m=c,c>0,where m is some positive integer constant value that depends on the structure of the transition probability matrix and the structure of states, where the initial distribution of the Markov chain is concentrated. The second variant is that independently of the initial distribution there exists the following nonzero limit (the so-calledweak power law):(4)limr→∞-log⁡prlog⁡r.This limit equals 1/γ, where γ is now defined with the help of the substochastic matrix P of transition probabilities where the row and the column that correspond to the absorbing state ω0 are deleted. Namely, raising all elements of the mentioned matrix to the power of γ would equate its spectral radius to 1.These results were obtained independently in [12, 14] and later refined in [13]. Namely, as appeared, the first alternative means the subexponential order of the asymptotics; that is, in this case ∃c1,c2:0<c1<c2, such that(5)c1exp⁡-cr-1/m<pr<c2exp⁡-cr-1/m.The case of the second alternative is much more difficult. If the matrixP does not have the block-diagonal structure with coinciding powers such that raising elements of blocks to these powers makes the spectral radius equal 1, then one can replace the weak power law with astrong one. Namely, in this case the asymptotic behavior of p(r) has the power order; that is, inequality (2) is valid (with “matrix” γ defined above). Therefore, inequality (2) takes place in a “typical” case of letter probabilities.However, one more natural question still remains without an answer.Inequality (2) means that the asymptotic form has a powerorder but does not imply theexact power asymptotics. In a general case, as follows from the first example given in this section, useful properties can be established neither when letters in words are Markov-dependent nor when they are independent. However, as we prove later in this paper, in a “typical” case, for words composed of independent letters, the asymptotic behavior of the function p(r) is exact power. The following theorem is valid.Theorem 1 (main).
Let at least one of the ratioslog⁡pi/log⁡pj, i,j∈{1,…,n}, be irrational and let γ be the root of the equation ∑i=1npiγ=1. Then the limit(6)limr→∞pr-γ/p0-γrexists and equals Hpγ, where Hpγ is the entropy of pγ=p1γ,…,pnγ; that is, Hpγ=-γ∑i=1npiγln⁡pi.Here and below we always write the function under consideration in the numerator and do the norming (defined analytically) function in the denominator of the fraction, whose limit is to be calculated. In intermediate calculations it may be more convenient to do the opposite, but since this results only in the trivial raising of the limit constant to the power of-1, we sacrifice the convenience of calculations for the clarity of statements of results. Evidently, the theorem asserts that under certain assumptions there exists the nonzero limit pr/r-α (where α=1/γ) as r→∞. It is equal to p0Hpγ-1/γ.Let us describe the structure of the remaining part of the paper. In Section2 we state the main theorem in terms of multinomial coefficients (of the Pascal pyramid). The proof of the theorem is reduced to the estimation of the limit behavior of the sum of these coefficients over some simplex. In Section 3 we prove an analog of this theorem with an integral in place of the sum. In this section we essentially use the Stirling formula which allows us to reduce calculations to the evaluation of a multivariate Gaussian integral. We establish an explicit formula for the determinant of the matrix of the quadratic form that defines the integrand. Finally, in Section 4 we prove that the ratio of the integral to the sum tends to 1. Here we use the general properties of the Riemann integral and uniformly distributed sequences. In conclusion we discuss possible generalizations and unsolved problems.


## 1.1. Brief Literature Overview

The wide presence of power laws in real networks, biology, economics, and linguistics can be explained in the framework of various mathematical models (see, e.g., [1, 2]). According to Zipf’s law [3], in a list of word forms ordered by the frequency of occurrence, the frequency of the rth word form obeys a power function of r (the value r is called the rank of the word form). One can easily explain this law with the help of the so-called monkey model.Recall that the word forms “the”; “of”; and “and” are used most frequently in English texts. According to Zipf’s law, the word “the” is used in the texts twice as much as “of” and three times as much as “and”; in other words the word form occurrence frequency obeys the power function of rankr (the position number of the word form in an ordered frequency list) whose exponent is approximately -1. It should be noted that further surveys showed that Zipf’s law is roughly realised only for the most frequent words. At present, the researches try to describe the main part of the lexicon using the power law with an exponent -α, where α>1. Zipf explained his law on the basis of the principle of least effort. In accordance with this principle, the authors aim to minimise the length of the text, which is required to convey their thoughts, even if this introduces ambiguities. On the other hand, readers want to minimize the effort required to understand the text [4].Another explanation of Zipf’s law was suggested by Mandelbrot who slightly modified the law by introducing translation constant [5] into the argument of the power function. The important thing for our case is that later he hypothesized the existence of more simple explanation of the Zipf law associated with a simple probability model when all symbols in the text (including white-space) appear independently of each other with certain probability. Moreover, he analysed the Markovian dependence between these symbols and wrote out the correct (in a typical case) formula on the basis of special cases to determine the parameter α by the transition probabilities matrix in the Markov model [6].First, we will consider the model thoroughly described by Miller [7] and Li [8] for a special case of Mandelbrot’s experiment in which the monkey types the keys with uniform probability. To learn some other important references on the monkey model, we recommend to read the recent article by Richard Perline and Ron Perline [9] (see also references in the next subsection).


## 1.2. Statement of the Main Theorem and Its Connection with Other Results

Assume that a monkey types any of 26 Latin letters or the space on a keyboard with the same probability of1/27. We understand a word as a sequence of symbols typed by the monkey before the space. Let us sort the list of possible words with respect to probabilities of their occurrence (the empty word, whose probability equals 1/27, will go first in this list followed by 26 one-letter words whose probabilities equal 1/272 and then by 262 possible two-letters words and so on). We can prove (see [7, 8]) that the probability p(r) of a word with the rank of r satisfies the inequality(1)c1r-α<pr<c2r-α,where α=log⁡27/log⁡26 and c1,c2>0 (here and below we use the symbol log if the base of the logarithm is not significant; but for the natural logarithm we use the symbol ln).Relatively recently inequality (1) was generalized to the case of nonequiprobable letters. Let p0 be the probability that the monkey types the space, let pi, i=1,…,n, denote probabilities of choosing the ith letter from the set of n letters (pi>0, ∑i=0npi=1), and let pr be, as above, the probability of a word with a rank of r. Then, as is proved in [10, 11], the following inequality analogous to (1) takes place; namely, ∃c1,c2:0<c1<c2, such that(2)c1r-α<pr<c2r-α,whereα=1γand γ is the root of the equation ∑i=1npiγ=1 (evidently, 0<γ<1). Note that inequality (2) is equivalent to the boundedness of the difference -log⁡pr-αlog⁡r.In the case when the probability of each letter is not fixed but depends on the previous one, words represent trajectories of a Markov chain with the absorbing stateω0 and transient states ω1,…,ωn. Then the value p(r) is the probability of the rth trajectory in the list of possible trajectories sorted in the nonincreasing order of probabilities. In this case, the asymptotic behavior of p(r) does not necessarily have a power order. Namely, in this case one of the two alternatives takes place [12, 13]. The first variant is that there exists the limit(3)limr→∞-log⁡prr1/m=c,c>0,where m is some positive integer constant value that depends on the structure of the transition probability matrix and the structure of states, where the initial distribution of the Markov chain is concentrated. The second variant is that independently of the initial distribution there exists the following nonzero limit (the so-calledweak power law):(4)limr→∞-log⁡prlog⁡r.This limit equals 1/γ, where γ is now defined with the help of the substochastic matrix P of transition probabilities where the row and the column that correspond to the absorbing state ω0 are deleted. Namely, raising all elements of the mentioned matrix to the power of γ would equate its spectral radius to 1.These results were obtained independently in [12, 14] and later refined in [13]. Namely, as appeared, the first alternative means the subexponential order of the asymptotics; that is, in this case ∃c1,c2:0<c1<c2, such that(5)c1exp⁡-cr-1/m<pr<c2exp⁡-cr-1/m.The case of the second alternative is much more difficult. If the matrixP does not have the block-diagonal structure with coinciding powers such that raising elements of blocks to these powers makes the spectral radius equal 1, then one can replace the weak power law with astrong one. Namely, in this case the asymptotic behavior of p(r) has the power order; that is, inequality (2) is valid (with “matrix” γ defined above). Therefore, inequality (2) takes place in a “typical” case of letter probabilities.However, one more natural question still remains without an answer.Inequality (2) means that the asymptotic form has a powerorder but does not imply theexact power asymptotics. In a general case, as follows from the first example given in this section, useful properties can be established neither when letters in words are Markov-dependent nor when they are independent. However, as we prove later in this paper, in a “typical” case, for words composed of independent letters, the asymptotic behavior of the function p(r) is exact power. The following theorem is valid.Theorem 1 (main).
Let at least one of the ratioslog⁡pi/log⁡pj, i,j∈{1,…,n}, be irrational and let γ be the root of the equation ∑i=1npiγ=1. Then the limit(6)limr→∞pr-γ/p0-γrexists and equals Hpγ, where Hpγ is the entropy of pγ=p1γ,…,pnγ; that is, Hpγ=-γ∑i=1npiγln⁡pi.Here and below we always write the function under consideration in the numerator and do the norming (defined analytically) function in the denominator of the fraction, whose limit is to be calculated. In intermediate calculations it may be more convenient to do the opposite, but since this results only in the trivial raising of the limit constant to the power of-1, we sacrifice the convenience of calculations for the clarity of statements of results. Evidently, the theorem asserts that under certain assumptions there exists the nonzero limit pr/r-α (where α=1/γ) as r→∞. It is equal to p0Hpγ-1/γ.Let us describe the structure of the remaining part of the paper. In Section2 we state the main theorem in terms of multinomial coefficients (of the Pascal pyramid). The proof of the theorem is reduced to the estimation of the limit behavior of the sum of these coefficients over some simplex. In Section 3 we prove an analog of this theorem with an integral in place of the sum. In this section we essentially use the Stirling formula which allows us to reduce calculations to the evaluation of a multivariate Gaussian integral. We establish an explicit formula for the determinant of the matrix of the quadratic form that defines the integrand. Finally, in Section 4 we prove that the ratio of the integral to the sum tends to 1. Here we use the general properties of the Riemann integral and uniformly distributed sequences. In conclusion we discuss possible generalizations and unsolved problems.


## 2. Equivalent Statements of the Main Theorem and the Pascal Pyramid

Let us first note that ifp0→0, then γ→1. Reducing the nominator of fraction (6) by p0-γ, we write the following statement in this case:Theorem 2 (the case ofγ=1).
Letpi>0 be the probability of the symbol ωi, i=1,…,n, while ∑i=1npi=1 (there is no stop symbol). Assume that at least one of the ratios log⁡pi/log⁡pj, i,j∈1,…,n, is irrational. Let us consider all possible finite words (including the empty one) and sort them in the nonincreasing order of probabilities (we equate the probability of the empty word to 1 and calculate the probability of any other word as the product of probabilities of its letters). Let pr be the probability of the rth word in the list (the word with therank of r). Then the limit limr→∞pr/r-1 exists and equals H-1p, where Hp is the entropy of the vector p=p1,…,pn; that is, Hp=-∑i=1npiln⁡pi.In the statement of Theorem2, as well as in Theorem 1, we use the bold font for the vector whose components are denoted by the same letter with the index ranging from 1 to n. In what follows we use the bold font for analogous denotations without mentioning this fact.One can easily see that Theorem2 is not just a particular case of Theorem 1, but these theorems are equivalent. Namely, the replacement of probabilities piγ with new ones pi turns the general case into the particular one. Therefore, in what follows we neglect p0, assuming (without loss of generality) that ∑i=1npi=1.Fix some probabilityq∈0,1 and denote by Qq the rank of the last word whose probability is not less than q in the list of all words sorted in the nonincreasing order of their probabilities. Let us redefine the function pr for noninteger r as pr=pr (here · is the integer part of a number). Evidently, functions q=pr and r=Qqq∈0,1,r≥1 are inverse (more exactly, quasi-inverse); namely, the graph of one of the hyperbola-shaped, decreasing stepwise functions turns into another one when axes r and q switch roles (in the first case, q is the argument and r is the value and vice versa in the second case).It can be clearly seen thatlimr→∞cpr/r-1=1 is equivalent to(7)limq→0⁡c-1Qqq-1=1.Therefore the equality in the assertion of Theorem 2 is equivalent to that(8)limq→0⁡Qqq-1=H-1p.Denote the logarithm of the denominator in the last fraction byz=-ln⁡q (i.e., q=e-z) and let Q~(z)=Qe-z. In view of considerations in the above paragraph the equality in the assertion of Theorem 2 is equivalent to that(9)limz→∞ln⁡Q~z-z=-ln⁡Hp.Recall the proof of inequality (2) in [11]. It is reduced to the proof of the boundedness of the difference ln⁡Q~(z)-z for the introduced function Q~(z) with z≥0. Nonnegative values of z form the definition domain of the function Q~(z) because q≤1⇔z≥0. For convenience we redefine the function Q~(z) by putting Q~(z)=0 for z<0.Letai=-ln⁡pi. Considering all possible variants of the last letters in words, whose quantity equals the value of the function Q~, we obtain the functional equation Q~(z)=Q~(z-a1)+⋯+Q~z-an+χz, where χ is the Heaviside step (i.e., the function that vanishes with negative values of the argument and equals 1 with nonnegative values). For z≥M=max⁡a1,…,an we get the following recurrent correlation:(10)Qnz=Qnz-a1+⋯+Qnz-an,where Qn(z)=Q~(z)+1/(n-1).The equality∑i=1npi=1 implies that the function constexp⁡z satisfies (10). Since the function Qn(z) takes a finite number of positive values within [0,M] interval, there exist positive c1 and c2 such that(11)c1exp⁡z<Qnz<c2exp⁡zfor all 0≤z≤M.Replacing terms in the right-hand side of the recurrent correlation (10) with their lower (upper) bounds, we extend the solution set of inequality (11) to the domain 0≤z≤M+m, where m=min⁡a1,…,an. Repeating this procedure several times, in a finite number of steps we prove that the inequality is valid for any arbitrarily large z. Performing the logarithmic transformation of the inequality, we conclude that ln⁡Qn(z)-z is bounded, and then so is the difference ln⁡Q~(z)-z.Let us return to Theorem2. As was mentioned above, Theorem 2 asserts (under certain assumptions) not only the boundedness of ln⁡Q~(z)-z but also the validity of equality (9). Let us recall the combinatory sense of the function Q~; it is mentioned in [11]. Evidently, all words that contain k1 letters of the 1st kind, k2 letters of the 2nd kind, …, and kn letters of the nth kind have one and the same probability of Pr(k)=p1k1⋯pnkn (i.e., -ln⁡Pr(k)=∑i=1nkiai); ranks of these words are consecutive. The quantity of such words is defined by the multinomial coefficient(12)Mk=k1+⋯+kn!k1!⋯kn!.Considering the nonnegative part of then-dimensional integer grid and associating the point k1,…,kn with the number Mk1,…,kn, we get one of the variants of the Pascal pyramid. By the definition of the function Q~ the value Q~z equals the sum of multinomial coefficients Mk over all integer vectors k that lie inside the n-dimensional simplex Sz=x:x≥0,∑i=1naixi≤z:(13)Q~z=∑k∈SzMk.As a result, we obtain one more equivalent statement of the main theorem, which we are going to prove.Theorem 3 (the multinomial statement).
Letai, i=1,…,n, be arbitrary positive numbers such that at least one of the ratios ai/aj, i,j∈{1,…,n}, be irrational and ∑i=1npi=1, where pi=exp⁡(-ai). Let a function Q~ obey formula (13). Then(14)limz→∞Q~zexp⁡z=H-1p,where H(p)=∑i=1naipi.


## 3. The Proof of an Analog of Theorem3 with Integration instead of Summation

### 3.1. Reduction of the Integration to the Calculation of a Gaussian Integral

The functionMk1,…,kn is defined for integer nonnegative vectors k. Let us redefine it for noninteger vectors by replacing (in this case) x! in Definition (12) with Γ(x+1). In what follows we use the denotation Mx1,…,xn (or Mx) for the corresponding function which is continuous for nonnegative xi. Further we consider this function and study its properties only for such (nonnegative) xi.In this section we prove the following theorem.Theorem 4 (on the integral).
Letai, i=1,…,n, be arbitrary positive numbers such that ∑i=1npi=1, where pi=exp⁡(-ai). Let a function f(z) obey the formula f(z)=∫x∈S(z)M(x)dx, where dx=∏i=1ndxi. Then(15)limz→∞fzexp⁡z=H-1p.Proof. Let us first recall some evident properties of the integrand. Note that the existence of the (Riemann) integral of f(z) over the compact set Sz evidently follows from the continuity of Mx in the domain under consideration.If all components of the vectorx1,…,xn, possibly, except one component xi, equal zero, then by definition we have Mx1,…,xn≡1. Let us prove that otherwise the function Mx1,…,xn is strictly increasing in xi. Since the gamma function is positive definite, it suffices to prove that in this case the partial derivative of ln⁡M(x1,…,xn) with respect to xi is positive. It equals(16)ln⁡Γ′x1+⋯+xn+1-ln⁡Γ′xi+1.The positiveness of this difference follows from the fact that the function ln⁡Γ′ is increasing; this property, in turn, follows from the logarithmic convexity of the gamma function (it is well known [15] that ln⁡Γ′′x=∑i=0∞1/i+x2>0 with x>0).The proved assertion implies that the functionMx attains its maximum in the domain Sz at the boundary a,x=z, where a,x=∑i=1naixi. Let us calculate the exact asymptotics of the maximal value of the function Mx in the domain Sz with z→∞. For the vector x we denote by x the sum of its components and parameterize x by the value x and ratios qi=xi/x:(17)xi=qix,qi≥0,i=1,…,n,∑i=1nqi=1.Let us use one simplest corollary of the Stirling formula [15], namely, the fact that with a nonnegative argument the value of the difference ln⁡Γ(x+1)-(xln⁡x-x+ln⁡(x+1)/2) is bounded. We obtain that, with any x>0,(18)ln⁡Mx1,…,xn=xHq+Oln⁡x+1,where H(q)=-∑i=1nqiln⁡qi (this correlation is closely connected with the so-called entropy inequality for multinomial coefficients).We seek for the maximum of this function withz→∞ under one additional condition (namely, the requirement that the maximum is attained at the boundary) a,x=z, where ai=-ln⁡pi, 0<pi<1, and ∑i=1npi=1. Since ai>0, we get O(ln⁡x+1)=Oln⁡z. Moreover, the condition a,x=z with mentioned xi gives the correlation(19)x=zHq;p-1,where H(q;p)=∑i=1naiqi=-∑i=1nqiln⁡pi. Substituting this expression in (18), we conclude that the maximum of ln⁡M (accurate to Oln⁡z) is attained at a vector q such that the fraction H(q)/H(q;p) takes on the maximal value. Recall that the difference H(q;p)-Hq takes on only nonnegative values and is called the Kullback–Leibler distance (divergence) D(q∣p) between distributions q and p (see [16]). The minimum of this difference is attained at only one value of q=p; evidently, an analogous assertion is also true for H(q;p)/H(q): if q≠p(20)HqHq;p<1.Consequently, the maximum of the function ln⁡Mx in the domain Sz is attained (accurate to Oln⁡z) at the intersection of the hyperplane a,x=z with the straight line xi=pix, i=1,…,n, where it equals z+Oln⁡z.Let us now immediately prove Theorem4. Note first that by using the L’Hopital rule we can reduce the proof to that of the formula obtained by differentiating f(z)/exp⁡(z) numerator and denominator with respect to z and to the proof of the equality(21)limz→∞f^zexp⁡z=H-1p,where f^(z)=∫x≥0Mxδz-a,xdx and δ· is the delta function.Letε be a real arbitrarily small positive value. Denote by Λε the sector consisting of points x, xi=qix, and ∑iqi=1, such that(22)pi-ε<qi<pi+ε,i=1,…,n.With fixed z on the hyperplane a,x=z correlations (18) and (19) take the form(23)ln⁡Mx=zHqHq;p+Oln⁡z.Let us now strengthen inequality (20); namely, let us prove that if for q correlations (22) are violated, then(24)HqHq;p<1-C1pε2,where C1(p) is a positive constant independent of q.SinceHq;p is a convex combination of -ln⁡pi, it evidently is bounded:(25)0<mini-ln⁡pi≤Hq;p≤maxi-ln⁡pi.Consequently, formula (24) is equivalent to the inequality(26)Hq;p-Hq=Dq∣p>C2pε2.The latter correlation follows from the well-known property of the Kullback-Leibler divergence(27)Dq∣p≥14∑i=1npi-qi2(see, e.g., lemma  3.6.10 in [16]).The proved inequality (24) (in view of formula (23)) implies that outside the domain Λε the function Mx is exponentially small in comparison to the maximal value inside the domain which equals exp⁡(z). More precisely, with x∉Λε and a,x=z, we get(28)Mx<exp⁡1-Cε2zfor  someC>0.Note that the condition of the exponential smallness in comparison to exp⁡z remains valid, even if ε depends on z and tends to 0 as z increases, though not too fast. In what follows we assume that(29)ε=εz=z-1/2+δ,whereδ>0is  sufficiently  small.One can easily see that the same exponential upper bound as in (28) also takes place not only for M function but also for its integral over the domain whose volume grows according to a power law:(30)∫x∉Λεz,x≥0Mxδz-a,xdx<exp⁡1-Cε2zwith z→∞. Therefore in limit (21) we can treat f^(z) as the integral(31)∫x∈ΛεzMxδz-a,xdx.Let us define the asymptotics (18) of the function Mx in the domain Λεz more precisely. Let us use the standard Stirling formula, namely, the fact that with x→∞ it holds that ln⁡Γx+1=xln⁡(x)-x+ln⁡x/2+ln⁡(2π)/2+R(x), where 0<R(x)<1/(12x). We obtain that, in the domain Λε(z),(32)Mx=12πn-1exp⁡xHq+ln⁡x2-∑i=1nln⁡xi2+O1z.Here, as usual, x=∑i=1nxi; qi=xi/x. Therefore, we conclude that when considering the asymptotics of function (31) we can treat Mx as follows:(33)M~x=12πn-1expxHq+lnx2-∑i=1nln⁡xi2.In the latter formula we can write the exponent as(34)ln⁡xi2=xln⁡x+ln⁡x2-∑i=1nxiln⁡xi+ln⁡xi2.Let us write the Taylor expansion up to second-order terms near the maximum point in the plane a,x=z, that is, near the point x′=pz/H(p) (in what follows we denote by xi′ coordinates of the point x′ and do by x′ the sum of these coordinates which evidently equals zHp-1).First of all, note that(35)M~x′=12πx′n-1∏i=1npiexp⁡z.One can easily calculate second derivatives of expression (34):(36)∂2∂xi∂xj∂2∂xi∂xj=x-1-2x2-1,ifi≠j,x-1-2x2-1-xi-1+2xi2-1,else.(note that we do not use first derivatives in the Taylor expansion near the maximum point).Ifx∈Λε, then by formula (19) we have x-x′=zHq;p-1-Hp-1=zOε (in the latter inequality we use the continuity of the function Hq;p-1). Consequently,(37)xi-xi′=xqi-x′pi=x′+zOεpi+Oε-x′pi=zOε.In particular, with chosenε=εz we have xi-xi′=O(z1/2+δ). We obtain that, in the domain Λεz, (38)M~x=12πx′n-1∏i=1npiexp⁡z×exp⁡∑i,j=1nxi-xi′xj-xj′2x′-∑i=1nxi-xi′22pix′+Oz-1/2+3δ.Here the term O(z-1/2+3δ) contains both the remainder of terms of the series whose order exceeds 2 and the value of O(z-1+2δ) added by some omitted second-order terms. With z→∞ we can neglect the term of O(z-1/2+3δ). Therefore, in integral (31) in place of Mx we should substitute the function M^x which differs from M~x in the fact that its exponent does not contain the term of O(z-1/2+3δ).Let us change variables in the integral as follows:yi=xi-xi′/x′. Since the degree of homogeneity of the delta-function equals -1, we obtain that limit (21) coincides with(39)12πn-1∏i=1npi∫Rnδa,yexp⁡-By,y2dy,where B is n×n matrix, whose all elements equal -1, except diagonal components which are greater by 1/pi.


### 3.2. Calculation of the Determinant

Lemma 5.
Letn≥2. Consider n×n matrix B, where all nondiagonal elements equal 1, while bii=1+ki. Then(1)
the determinant of this matrix equals(40)∏i=1nki1+∑j=1n1kj;(2)
the algebraic complement of the element with indicesi,j,i≠j, equals(41)-∏l∈n∖i,jkl,wheren=1,…,n.Corollary 6.
The matrixB in formula (39) is degenerate.Proof of Lemma5.
Note that the first item of Lemma5 defines the value of the algebraic complement of the diagonal element of such a matrix. Let us prove the theorem by induction.
Withn=2 in the formula in item (2) we get the product over the empty set; it is accepted that this product equals 1. The formula in item (1) remains valid with n=1. In the induction step we assume that the formula in item (1) is proved for all dimensions less than n and has to be proved for the case when the dimension equals n, while the formula in item (2) is proved for all dimensions not greater than n and has to be proved for (n+1)×(n+1) matrix.
For proving item (1) we can use the expansion by the last row. Multiplying the algebraic complement by the diagonal element kn+1, we get the sum(42)∏i=1nki1+∑j=1n-11kj+∏i=1n-1ki1+∑j=1n-11kj=∏i=1nki1+∑j=1n-11kj+∏i=1n-1ki+∑j=1n-1∏l∈n∖n,jkl.The expansion by the entire last row, taking into account the induction hypothesis for item (2), make the third part in row (42) vanish. First two terms in formula (42) together give the desired sum.
In order to prove item (2), let us expand the determinant considered in this item (algebraic complement of the element with (i,j) indices of the matrix B with (n+1)×(n+1) dimension) by the row whose number in the initial matrix of B was equal to j. Generally speaking, for clarity, we use the same indices as in the numeration of the initial matrix. Since the algebraic complement considered in this item and the occurring algebraic complement for the element with indices (j,i) (obtained by the expansion by a row of the determinant under consideration) have opposite signs, the value added by the element with indices (j,i) equals(43)-∏r∈n+1∖i,jkr1+∑l∈n+1∖i,j1kl(here we have used the induction hypothesis for item (1)). The difference from the desired formula consists in the last term which equals (taking into account the first multiplier)(44)-∑l∈n+1∖i,j∏r∈n+1∖i,j,lkr.It vanishes, when taking into account the contribution of the remaining n-1 elements in the jth row of the considered matrix.Lemma 7.
LetB1 be the matrix mentioned in Lemma 5 (its dimension is n×n, n≥2). Assume that bii=1-1/pi, i=1,…,n, where pi are arbitrary nonzero numbers. Denote by B2 a matrix of the same dimension in the form aTa, where a=(a1,…,an) is an arbitrary numeric row and T is the transposition sign. Let s be an arbitrary real number. Then (45)det⁡sB2-B1=det⁡-B1+s∑i=1naipi2-∑j=1npj-1∑i=1nai2pi∏l=1npl.Corollary 8.
Let a vectorp=(p1,…,pn) satisfy additional constraints pi>0, ∑i=1npi=1 (i.e., -B1=B), while ai=-ln⁡pi. Then(46)sdet⁡s-1B2-B1=Hp∏l=1npl.Proof of Lemma7.
By the differentiation rule for determinants, the derivative of the determinant ofn×n matrix equals the sum of determinants of n matrices such that in the ith one all elements of the ith row are replaced with their derivatives. We obtain that ∂2det⁡sB2-B1/∂s2 is the sum of determinants of matrices each one of which contains either the zero row or two various rows of the matrix B2. Since rank B2=1, we get ∂2det⁡sB2-B1/∂s2=0.
Thus,det⁡sB2-B1 is a linear function of s, whose free term evidently equals det⁡(-B1). It is clear that for calculating the coefficient det⁡sB2-B1 at s it suffices to summate products of each element of the matrix B2 by the algebraic complement of the corresponding element of the matrix -B1. If an element has indices (i,j), i≠j, then by item (2) of Lemma 5 this product equals aiajpipj/∏l=1npl.
Let us explain the positive sign in the last formula. We calculate an algebraic complement of the-B1 matrix element. The matrix has n×n dimension, and therefore the found algebraic complement differs from the algebraic complement of the corresponding B1 matrix element for -1n-1 times. According to item (2) of Lemma 5, the algebraic complement of the corresponding B1 matrix element is a “minus” product of n-2 multipliers ki. In the given case each of ki factors is negative (equals -1/pi) which results in positive sign of the last formula in the above paragraph.
Assume that this formula is valid for all(i,j). Then we get the sum(47)∑i,j=1naiajpipj∏l=1npl=∑i=1naipi2∏l=1npl.However by item (1) of Lemma 5 the algebraic complement of the diagonal element bii of the matrix -B1 equals(48)-1n-1∏j:j≠i-1pj+∑j:j≠i∏l∉i,j-1pl(here and below we omit the evident requirement that values of all indices belong to the set [n]).
Multiplying the first term in parentheses, that is,∏j:j≠i(-1/pj), by -1n-1ai2 and summing over all i, we get ∑i=1nai2pi/∏l=1npl. Let us multiply the resting term in parentheses (48) by -1n-1ai2, sum over all i, and subtract the value(49)∑i=1nai2pi2∏l=1nplfrom the obtained result (note that the subtrahend was “illegally” included in formula (47)). It gives the overall contribution of the second term in formula (48), which equals(50)-∑j=1npj∑i=1nai2pi∏l=1npl.Taking into account all the calculation elements of the determinant det(sB2-B1) allows completing the proof of Lemma 7.For completing the proof of Theorem4 let us use Corollary 8. Let us replace the δ-function in integral (39) (as was proved earlier, this integral equals the limit considered in Theorem 4): δ(t)=limσ→01/2πσexp{-t2/2σ2}. Treating the limit multiplied by the coefficient at the exponent as a multiplier in the integral, we come to the limit of the Gaussian integral(51)limσ→0∫Rnexp⁡-σ-2B2+By,y/2dyσ2πn∏i=1npi,that is,(52)limσ→01σ∏i=1npidet⁡σ-2B2+B;Immediately applying Corollary 8, we get desired H-1(p). This completes the proof.


## 3.1. Reduction of the Integration to the Calculation of a Gaussian Integral

The functionMk1,…,kn is defined for integer nonnegative vectors k. Let us redefine it for noninteger vectors by replacing (in this case) x! in Definition (12) with Γ(x+1). In what follows we use the denotation Mx1,…,xn (or Mx) for the corresponding function which is continuous for nonnegative xi. Further we consider this function and study its properties only for such (nonnegative) xi.In this section we prove the following theorem.Theorem 4 (on the integral).
Letai, i=1,…,n, be arbitrary positive numbers such that ∑i=1npi=1, where pi=exp⁡(-ai). Let a function f(z) obey the formula f(z)=∫x∈S(z)M(x)dx, where dx=∏i=1ndxi. Then(15)limz→∞fzexp⁡z=H-1p.Proof. Let us first recall some evident properties of the integrand. Note that the existence of the (Riemann) integral of f(z) over the compact set Sz evidently follows from the continuity of Mx in the domain under consideration.If all components of the vectorx1,…,xn, possibly, except one component xi, equal zero, then by definition we have Mx1,…,xn≡1. Let us prove that otherwise the function Mx1,…,xn is strictly increasing in xi. Since the gamma function is positive definite, it suffices to prove that in this case the partial derivative of ln⁡M(x1,…,xn) with respect to xi is positive. It equals(16)ln⁡Γ′x1+⋯+xn+1-ln⁡Γ′xi+1.The positiveness of this difference follows from the fact that the function ln⁡Γ′ is increasing; this property, in turn, follows from the logarithmic convexity of the gamma function (it is well known [15] that ln⁡Γ′′x=∑i=0∞1/i+x2>0 with x>0).The proved assertion implies that the functionMx attains its maximum in the domain Sz at the boundary a,x=z, where a,x=∑i=1naixi. Let us calculate the exact asymptotics of the maximal value of the function Mx in the domain Sz with z→∞. For the vector x we denote by x the sum of its components and parameterize x by the value x and ratios qi=xi/x:(17)xi=qix,qi≥0,i=1,…,n,∑i=1nqi=1.Let us use one simplest corollary of the Stirling formula [15], namely, the fact that with a nonnegative argument the value of the difference ln⁡Γ(x+1)-(xln⁡x-x+ln⁡(x+1)/2) is bounded. We obtain that, with any x>0,(18)ln⁡Mx1,…,xn=xHq+Oln⁡x+1,where H(q)=-∑i=1nqiln⁡qi (this correlation is closely connected with the so-called entropy inequality for multinomial coefficients).We seek for the maximum of this function withz→∞ under one additional condition (namely, the requirement that the maximum is attained at the boundary) a,x=z, where ai=-ln⁡pi, 0<pi<1, and ∑i=1npi=1. Since ai>0, we get O(ln⁡x+1)=Oln⁡z. Moreover, the condition a,x=z with mentioned xi gives the correlation(19)x=zHq;p-1,where H(q;p)=∑i=1naiqi=-∑i=1nqiln⁡pi. Substituting this expression in (18), we conclude that the maximum of ln⁡M (accurate to Oln⁡z) is attained at a vector q such that the fraction H(q)/H(q;p) takes on the maximal value. Recall that the difference H(q;p)-Hq takes on only nonnegative values and is called the Kullback–Leibler distance (divergence) D(q∣p) between distributions q and p (see [16]). The minimum of this difference is attained at only one value of q=p; evidently, an analogous assertion is also true for H(q;p)/H(q): if q≠p(20)HqHq;p<1.Consequently, the maximum of the function ln⁡Mx in the domain Sz is attained (accurate to Oln⁡z) at the intersection of the hyperplane a,x=z with the straight line xi=pix, i=1,…,n, where it equals z+Oln⁡z.Let us now immediately prove Theorem4. Note first that by using the L’Hopital rule we can reduce the proof to that of the formula obtained by differentiating f(z)/exp⁡(z) numerator and denominator with respect to z and to the proof of the equality(21)limz→∞f^zexp⁡z=H-1p,where f^(z)=∫x≥0Mxδz-a,xdx and δ· is the delta function.Letε be a real arbitrarily small positive value. Denote by Λε the sector consisting of points x, xi=qix, and ∑iqi=1, such that(22)pi-ε<qi<pi+ε,i=1,…,n.With fixed z on the hyperplane a,x=z correlations (18) and (19) take the form(23)ln⁡Mx=zHqHq;p+Oln⁡z.Let us now strengthen inequality (20); namely, let us prove that if for q correlations (22) are violated, then(24)HqHq;p<1-C1pε2,where C1(p) is a positive constant independent of q.SinceHq;p is a convex combination of -ln⁡pi, it evidently is bounded:(25)0<mini-ln⁡pi≤Hq;p≤maxi-ln⁡pi.Consequently, formula (24) is equivalent to the inequality(26)Hq;p-Hq=Dq∣p>C2pε2.The latter correlation follows from the well-known property of the Kullback-Leibler divergence(27)Dq∣p≥14∑i=1npi-qi2(see, e.g., lemma  3.6.10 in [16]).The proved inequality (24) (in view of formula (23)) implies that outside the domain Λε the function Mx is exponentially small in comparison to the maximal value inside the domain which equals exp⁡(z). More precisely, with x∉Λε and a,x=z, we get(28)Mx<exp⁡1-Cε2zfor  someC>0.Note that the condition of the exponential smallness in comparison to exp⁡z remains valid, even if ε depends on z and tends to 0 as z increases, though not too fast. In what follows we assume that(29)ε=εz=z-1/2+δ,whereδ>0is  sufficiently  small.One can easily see that the same exponential upper bound as in (28) also takes place not only for M function but also for its integral over the domain whose volume grows according to a power law:(30)∫x∉Λεz,x≥0Mxδz-a,xdx<exp⁡1-Cε2zwith z→∞. Therefore in limit (21) we can treat f^(z) as the integral(31)∫x∈ΛεzMxδz-a,xdx.Let us define the asymptotics (18) of the function Mx in the domain Λεz more precisely. Let us use the standard Stirling formula, namely, the fact that with x→∞ it holds that ln⁡Γx+1=xln⁡(x)-x+ln⁡x/2+ln⁡(2π)/2+R(x), where 0<R(x)<1/(12x). We obtain that, in the domain Λε(z),(32)Mx=12πn-1exp⁡xHq+ln⁡x2-∑i=1nln⁡xi2+O1z.Here, as usual, x=∑i=1nxi; qi=xi/x. Therefore, we conclude that when considering the asymptotics of function (31) we can treat Mx as follows:(33)M~x=12πn-1expxHq+lnx2-∑i=1nln⁡xi2.In the latter formula we can write the exponent as(34)ln⁡xi2=xln⁡x+ln⁡x2-∑i=1nxiln⁡xi+ln⁡xi2.Let us write the Taylor expansion up to second-order terms near the maximum point in the plane a,x=z, that is, near the point x′=pz/H(p) (in what follows we denote by xi′ coordinates of the point x′ and do by x′ the sum of these coordinates which evidently equals zHp-1).First of all, note that(35)M~x′=12πx′n-1∏i=1npiexp⁡z.One can easily calculate second derivatives of expression (34):(36)∂2∂xi∂xj∂2∂xi∂xj=x-1-2x2-1,ifi≠j,x-1-2x2-1-xi-1+2xi2-1,else.(note that we do not use first derivatives in the Taylor expansion near the maximum point).Ifx∈Λε, then by formula (19) we have x-x′=zHq;p-1-Hp-1=zOε (in the latter inequality we use the continuity of the function Hq;p-1). Consequently,(37)xi-xi′=xqi-x′pi=x′+zOεpi+Oε-x′pi=zOε.In particular, with chosenε=εz we have xi-xi′=O(z1/2+δ). We obtain that, in the domain Λεz, (38)M~x=12πx′n-1∏i=1npiexp⁡z×exp⁡∑i,j=1nxi-xi′xj-xj′2x′-∑i=1nxi-xi′22pix′+Oz-1/2+3δ.Here the term O(z-1/2+3δ) contains both the remainder of terms of the series whose order exceeds 2 and the value of O(z-1+2δ) added by some omitted second-order terms. With z→∞ we can neglect the term of O(z-1/2+3δ). Therefore, in integral (31) in place of Mx we should substitute the function M^x which differs from M~x in the fact that its exponent does not contain the term of O(z-1/2+3δ).Let us change variables in the integral as follows:yi=xi-xi′/x′. Since the degree of homogeneity of the delta-function equals -1, we obtain that limit (21) coincides with(39)12πn-1∏i=1npi∫Rnδa,yexp⁡-By,y2dy,where B is n×n matrix, whose all elements equal -1, except diagonal components which are greater by 1/pi.


## 3.2. Calculation of the Determinant

Lemma 5.
Letn≥2. Consider n×n matrix B, where all nondiagonal elements equal 1, while bii=1+ki. Then(1)
the determinant of this matrix equals(40)∏i=1nki1+∑j=1n1kj;(2)
the algebraic complement of the element with indicesi,j,i≠j, equals(41)-∏l∈n∖i,jkl,wheren=1,…,n.Corollary 6.
The matrixB in formula (39) is degenerate.Proof of Lemma5.
Note that the first item of Lemma5 defines the value of the algebraic complement of the diagonal element of such a matrix. Let us prove the theorem by induction.
Withn=2 in the formula in item (2) we get the product over the empty set; it is accepted that this product equals 1. The formula in item (1) remains valid with n=1. In the induction step we assume that the formula in item (1) is proved for all dimensions less than n and has to be proved for the case when the dimension equals n, while the formula in item (2) is proved for all dimensions not greater than n and has to be proved for (n+1)×(n+1) matrix.
For proving item (1) we can use the expansion by the last row. Multiplying the algebraic complement by the diagonal element kn+1, we get the sum(42)∏i=1nki1+∑j=1n-11kj+∏i=1n-1ki1+∑j=1n-11kj=∏i=1nki1+∑j=1n-11kj+∏i=1n-1ki+∑j=1n-1∏l∈n∖n,jkl.The expansion by the entire last row, taking into account the induction hypothesis for item (2), make the third part in row (42) vanish. First two terms in formula (42) together give the desired sum.
In order to prove item (2), let us expand the determinant considered in this item (algebraic complement of the element with (i,j) indices of the matrix B with (n+1)×(n+1) dimension) by the row whose number in the initial matrix of B was equal to j. Generally speaking, for clarity, we use the same indices as in the numeration of the initial matrix. Since the algebraic complement considered in this item and the occurring algebraic complement for the element with indices (j,i) (obtained by the expansion by a row of the determinant under consideration) have opposite signs, the value added by the element with indices (j,i) equals(43)-∏r∈n+1∖i,jkr1+∑l∈n+1∖i,j1kl(here we have used the induction hypothesis for item (1)). The difference from the desired formula consists in the last term which equals (taking into account the first multiplier)(44)-∑l∈n+1∖i,j∏r∈n+1∖i,j,lkr.It vanishes, when taking into account the contribution of the remaining n-1 elements in the jth row of the considered matrix.Lemma 7.
LetB1 be the matrix mentioned in Lemma 5 (its dimension is n×n, n≥2). Assume that bii=1-1/pi, i=1,…,n, where pi are arbitrary nonzero numbers. Denote by B2 a matrix of the same dimension in the form aTa, where a=(a1,…,an) is an arbitrary numeric row and T is the transposition sign. Let s be an arbitrary real number. Then (45)det⁡sB2-B1=det⁡-B1+s∑i=1naipi2-∑j=1npj-1∑i=1nai2pi∏l=1npl.Corollary 8.
Let a vectorp=(p1,…,pn) satisfy additional constraints pi>0, ∑i=1npi=1 (i.e., -B1=B), while ai=-ln⁡pi. Then(46)sdet⁡s-1B2-B1=Hp∏l=1npl.Proof of Lemma7.
By the differentiation rule for determinants, the derivative of the determinant ofn×n matrix equals the sum of determinants of n matrices such that in the ith one all elements of the ith row are replaced with their derivatives. We obtain that ∂2det⁡sB2-B1/∂s2 is the sum of determinants of matrices each one of which contains either the zero row or two various rows of the matrix B2. Since rank B2=1, we get ∂2det⁡sB2-B1/∂s2=0.
Thus,det⁡sB2-B1 is a linear function of s, whose free term evidently equals det⁡(-B1). It is clear that for calculating the coefficient det⁡sB2-B1 at s it suffices to summate products of each element of the matrix B2 by the algebraic complement of the corresponding element of the matrix -B1. If an element has indices (i,j), i≠j, then by item (2) of Lemma 5 this product equals aiajpipj/∏l=1npl.
Let us explain the positive sign in the last formula. We calculate an algebraic complement of the-B1 matrix element. The matrix has n×n dimension, and therefore the found algebraic complement differs from the algebraic complement of the corresponding B1 matrix element for -1n-1 times. According to item (2) of Lemma 5, the algebraic complement of the corresponding B1 matrix element is a “minus” product of n-2 multipliers ki. In the given case each of ki factors is negative (equals -1/pi) which results in positive sign of the last formula in the above paragraph.
Assume that this formula is valid for all(i,j). Then we get the sum(47)∑i,j=1naiajpipj∏l=1npl=∑i=1naipi2∏l=1npl.However by item (1) of Lemma 5 the algebraic complement of the diagonal element bii of the matrix -B1 equals(48)-1n-1∏j:j≠i-1pj+∑j:j≠i∏l∉i,j-1pl(here and below we omit the evident requirement that values of all indices belong to the set [n]).
Multiplying the first term in parentheses, that is,∏j:j≠i(-1/pj), by -1n-1ai2 and summing over all i, we get ∑i=1nai2pi/∏l=1npl. Let us multiply the resting term in parentheses (48) by -1n-1ai2, sum over all i, and subtract the value(49)∑i=1nai2pi2∏l=1nplfrom the obtained result (note that the subtrahend was “illegally” included in formula (47)). It gives the overall contribution of the second term in formula (48), which equals(50)-∑j=1npj∑i=1nai2pi∏l=1npl.Taking into account all the calculation elements of the determinant det(sB2-B1) allows completing the proof of Lemma 7.For completing the proof of Theorem4 let us use Corollary 8. Let us replace the δ-function in integral (39) (as was proved earlier, this integral equals the limit considered in Theorem 4): δ(t)=limσ→01/2πσexp{-t2/2σ2}. Treating the limit multiplied by the coefficient at the exponent as a multiplier in the integral, we come to the limit of the Gaussian integral(51)limσ→0∫Rnexp⁡-σ-2B2+By,y/2dyσ2πn∏i=1npi,that is,(52)limσ→01σ∏i=1npidet⁡σ-2B2+B;Immediately applying Corollary 8, we get desired H-1(p). This completes the proof.


## 4. The Ratio between the Sum and the Integral

What remains is to prove that, under assumptions of Theorem3, the ratio of the integral of the function M calculated over the domain S(z) to the sum of values of this function at integer points of this domain tends to 1 as z→∞. For comparing the integral of the function and the sum of its values in the same domain one usually applies the Koksma-Hlawka inequality (see [17]). Note that usually one considers the integral over a fixed domain (as a rule, the cube 0,1n), whereas the domain in the case under consideration is varying. However, we intend only to prove the convergence of the fraction to 1 and do not need to estimate the asymptotic difference between the integral and the sum, which simplifies the task.Evidently, it suffices to calculate the limit of the ratio for an arbitrary infinite increasing sequencez1,z2,…, such that zi→∞.Theorem 9.
LetΩ1,Ω2,… be a sequence of Jordan measurable sets such that Ωi⊂Ωi+1 for all i=1,2,…. Assume that f(x), x∈Ω, where Ω=⋃iΩi, is an integrable and bounded on each of the domains Ωi function such that f(x)≥0 and ∫f(x)dΩi→∞ as i→∞. Assume also that K is a countable set of points from Ω such that each of the sets Ki=K∩Ωi is finite. Then if for any sufficiently small α>0 there exists a partition of Ω onto a countable number of Jordan measurable sets Xj=Xj(α), j=1,2,…, such that Ωi=⋃j=1niXj for some ni=ni(α), while(53)supx∈Xj⁡fxinfx∈Xj⁡fx<1+αstarting  with  somej,(54)K∩XjμXj⟶1asj⟶∞,then in this case there exists the limit(55)limi→∞∫fxdΩi∑x∈Kifx=1.Proof.
Evidently,(56)μXjinfx∈Xjfx≤∫fxdXj≤μXjsupx∈Xjfx.Therefore, in view of (53) we conclude that starting with some j it holds that(57)∫fxdXj/μXj∑x∈K∩Xjfx/K∩Xj∈1-α,1+αwith α<1. In accordance with (54) we conclude that μXj/|K∩Xj|∈(1-α,1+α) for all j, except a finite number of values of the index. Therefore, there exists l such that, with all j>nl,(58)∫fxdXj∑x∈K∩Xjfx∈1-α2,1+α2.Representing this correlation as a double inequality and summing it over all j from nl+1 to ni, we obtain(59)∫fxdΩi∖Ωl∑x∈Ki∖Klfx∈1-α2,1+α2with i>l.
Note that by condition the numerator in the latter fraction (different from the integral∫f(x)dΩi by a constant value) tends to infinity. Then the same is true for the denominator. Note that the denominator differs from ∑x∈Kif(x) by a constant value.
Therefore we conclude that all limit points of the sequence∫f(x)dΩi/∑x∈Kif(x) lie inside the interval (1-α2,1+α2). Due to the arbitrariness of the choice of positive α Theorem 9 is proved.Corollary 10 (completion of the proof of Theorem1).
Letf(z) be the function mentioned in assumptions of Theorem 4 and let Q~(z) obey formula (13). Then if at least one of the ratios ai/ak, i,k∈{1,…,n}, i≠k, is irrational, then(60)limz→∞fzQ~z=1.Proof. For clarity we denote by z the parameter that defines the boundary of the considered domain, and do by ζ the corresponding parameter of the hyperplane that contains a certain interior point x of this domain; that is, ζ(x)=a,x.First of all, note that considerations in Section3.1 imply that both in the sum and in the integral we can replace S(z) with the domain(61)Λ^z=Sz∩Λεζ,whereεζ=ζ-1/2+δ,and replace the function M(x) with M~(x) defined by formula (34). Therefore, we need to prove that(62)∫x∈Λ^zM~xdx∑k∈Λ^zM~k⟶1(or that the difference of logarithms of the numerator and denominator tends to zero).In view of Theorem4 the logarithm of the numerator in the latter fraction is a uniformly continuous function of z, while the logarithm of the denominator evidently is a nondecreasing function. Therefore for proving the existence of the limit with z→∞ it suffices to prove the existence of the limit for a sequence in the form zn=κn, n=1,2,…, where κ is an arbitrarily small positive value (as the difference between the numerator and denominator of the logarithms in an arbitrary point slightly differs from the value of difference in the nearest points zn in this sequence). Namely, just for this fixed sequence we consider the ratio from the right-hand side of (62).In order to apply Theorem9, for an arbitrary sufficiently small positive α we construct a partition of Λε(ζ) onto domains Xj satisfying assumptions of the theorem. Namely, we construct this partition by dividing of an infinite quantity of “flapjacks” located between neighboring hyperplanes in the forms ζ(x)=cr and ζ(x)=cr+1, r=1,2,…, where cr+1=cr+Const, onto a finite number of domains Xj.Evidently, for anyα≤2κ we can choose a sequence cr such that(63)cr+1-cr=Const<α2;for  anyn∃r:zn=cr.To this end, it suffices to put cr=Constr, where Const=κ/⌈2κ/α⌉ (here ⌈·⌉ is an upward rounding to the nearest integer).LetCr={x:cr≤ζ(x)<cr+1}. Denote by Fr the rth “flapjack” Cr∩Λε(ζ). We are going to “cut” Fr onto a finite number of domains Xj. We numerate the countable number of domains Xj, j=1,2,…, so as to make domains Xj obtained by “cutting” Fr with the least r have lesser numbers, while the order of numbering inside the partition of Fr plays no role.Sinceε(ζ)=oζ, with x,y∈Fr, it holds that yi=xi+o(xi) (cf. with (37)). Consequently, with r→∞ we get ln⁡yi-ln⁡xi→0 and ln⁡y-ln⁡x→0.By formula (33),(64)ln⁡M~x=const+gx+ln⁡x2-∑i=1nln⁡xi2,where (65)gx=xHq=∑i=1nxiln⁡xi-∑i=1nxiln⁡∑j=1nxi.We get gradg=ln⁡q=ln⁡q1,…,ln⁡qn and (66)∂2g∂xi∂xj=O1x,i,j∈1,…,n.Using expansion in a series ln⁡M~ with evaluation of the second-order terms and considerations of the previous paragraph we obtain the following important observation. If x,y∈Fr and(67)xi-yi=ox=ocr,i=1,…,n,then with sufficiently large r it holds that(68)ln⁡M~x-ln⁡M~y<ln⁡q,x-y+α10.Sinceq→p as r→∞, with sufficiently large r it holds that(69)ln⁡q,x-y<a,x-y+α20<cr+1-cr+α20.As a result, we obtain that with sufficiently small α, starting with some r, it holds that(70)M~xM~y<1+α.Therefore, dividingFr onto domains Xj so as to fulfill correlation (67) for all points x,y that belong to one domain, we guarantee the validity of assumption (53) in Theorem 9. Note that it suffices to fulfill condition (67) for all indices i except one, because the validity of this condition for the remaining index follows from the fact that x,y∈Cr.Finally, let us use the irrationality ofai∗/ak∗ for some i∗≠k∗. Let us denote by Ik∗ the set {1,…,n}∖{k∗} and do by Ii∗k∗ the set {1,…,n}∖{i∗,k∗}. We are going to prove that, defining domains Xj by inequalities(71)lji≤xi<Lji,i∈Ik∗,whereLji-lji>constcr1/2-δ,we fulfill condition (54) (with K=Zn). Here, as usual, δ is a sufficiently small real positive value, though in this case we can choose δ as any number in the interval (0,1/2) (roughly speaking, it is sufficient that the radius of the pieces Xj used to divide “flapjacks” Fr tends to infinity at r→∞).Evidently, we can divide “almost all”Fr onto domains Xj so as to simultaneously fulfill inequalities (67) and conditions (71) on l and L (the remaining “cuttings” on the edges of the domain Fr which occur due to the inconsistency between the inequality lji≤xi<Lji,i∈Ik∗ and the definition of the boundary of the domain Λε(z) are asymptotically small).Evidently,μXj=∏i∈Ik∗(Lji-lji)×(cr+1-cr)/ak∗. Since the difference (Lji-lji) grows as j→∞,the asymptotics of the number of ways for choosing integer xi such that lji≤xi<Lji for i∈Ii∗k∗ coincide with ∏i∈Ii∗k∗(Lji-lji). Here and below we understand the asymptotics as a function of j such that the ratio of the considered quantity to this function tends to 1 as j→∞. In order to complete the proof of Corollary 10, what remains is to prove the following lemma.Lemma 11.
Let the ratioai∗/ak∗ be irrational and (Lji∗-lji∗)→∞. Assume also that the ratio (cr+1-cr)/ak∗ equals a constant value lesser than 1 which is independent of r. Then for fixed xi,i∈Ii∗k∗, the asymptotics of the number of ways to choose integer xi, i∈i∗,k∗, such that lji∗≤xi∗<Lji∗ and cr≤ζ(x)<cr+1 simultaneously, equal (Lji-lji)×(cr+1-cr)/ak∗.Proof of Lemma11.
In what follows we need standard denotations for the fractional part·, floor ·, and ceil · of a number.
Letc′=∑i∈Ii∗k∗aixi, dr=cr-c′/ak∗, Dr=(cr+1-c′)/ak∗, and θ=ai∗/ak∗. The condition cr≤ζ(x)<cr+1 is equivalent to the condition(72)θxi∗+xk∗∈dr,Dr.
If the differenceDr-dr (it equals cr+1-cr/ak∗) is less than 1 (this inequality obviously holds for sufficiently small α) then with fixed xi∗ the integer value xk∗ satisfying condition (72) is defined uniquely, provided that it exists. Therefore, we need to estimate the quantity of values xi∗ in the interval lji∗,Lji∗ such that θxi∗∈dr,Dr; here the latter correlation is understood in the sense of an interval on the unit circle, and the length of the considered interval is independent of r.
Recall the definition of a well-distributed sequence [17, section 1.5].Let(yn)n=1,2,…, be a sequence of real numbers. For integers N≥1 and k≥0 and a subset E of 0,1, let AE,N,k be the number of terms among yk+1,yk+2,…,yk+N that are lying in E.The sequenceynn=1,2,…, is said to bewell-distributed mod  1 if for all pairs a, b of real numbers with 0≤a<b≤1 we have(73)limN→∞⁡Aa,b;N,kN=b-auniformlyink=0,1,2,….Example. The sequence nθn=1,2,…, with θ irrational is well-distributed mod  1.The latter fact would have proved Lemma11, if the interval of the unit circle dr,Dr was independent of r. Let us clarify this property in the case of the inequality {Dr}>dr. In what follows we always assume that this inequality is valid (evidently, as in the definition of the well-distribution property, this leads to no loss of generality). Really, if k equals lji∗-1 and N does the difference ⌊Lji∗⌋-lji∗+1, then we obtain the uniform (in j) convergence(74)limN→∞Ad,D;N,lji∗-1N=D-d,which is equivalent to the assertion of the lemma with the fixed value of {dr}, {Dr}.Note that if with fixedj equality (74) is valid for any subinterval in [0,1), then we say that the corresponding sequence isuniformly distributed modulo 1. This property follows from the property of thewell-distribution modulo 1. It is well known that (see [17, section 2.1]) for any sequence uniformly distributed modulo 1 the convergence is uniform with respect to all subintervals in [0,1). Consequently, we get the uniform (in j) convergence(75)limN→∞Adr,Dr;N,lji∗-1N=Δ,where theconstantΔ equals Dr-dr. Therefore,(76)limj→∞Adr,Dr;Lji∗-lji∗+1,lji∗-1Lji∗-lji∗Δ=1,which coincides with the lemma assertion in a general case. This completes the proof.


## 5. Conclusion

We have proved that in the monkey model the probability of words in the sorted list has theexact power asymptotics, provided that the ratio of logarithms of probabilities of certain letters is irrational.Note that this condition is not only sufficient but also necessary. Really, otherwise logarithms of probabilitiesai=-ln⁡pi, i=1,…,n, allow the representation ai=miv, where mi are natural numbers and v is independent of i. In this case formula (10) defines a linear recurrent correlation on a grid with the step of v. This does not affect the initial constancy of the function Q~ in cells of the grid with the mentioned step with any value of the argument. Such constancy piecewise of the function Q~ contradicts the existence of a finite limit for the ratio of p(r)/r-γ.It should be noted that using the expression for terms of linear recurring sequences via the corresponding powers of roots of the characteristic equation allows clear analysis of rate of convergence to the power law of the functionQ~ (with a step of v on the grid) in this degenerate case. It would be more interesting to conduct such studies for more general case to which the main theorem of this paper is devoted.A generalization of results obtained in this paper to the case of the Markov dependence is of even more interest. In this case an analog of the vectorpγ is a substochastic matrix of transition probabilities where the row and column that correspond to the absorbing state are deleted, and all elements of this matrix are raised to a power of γ such that its spectral radius equals 1. Denote this matrix by Pγ. In the case considered above all rows of the matrix Pγ coincide with pγ. In a typical case, when the strong power law takes place (see Introduction), the matrix P is irreducible and the matrix transposed with respect to Pγ has a positive eigenvector that corresponds to the unit eigenvalue. Let us norm this vector so as to make the sum of its components equal 1 and denote the result by w. In the case of the Markov chain with the transition probability matrix Pγ this vector defines an ergodic distribution.If all rows of the considered matrix coincide withpγ, then one can easily see that w coincides with pγ. It is possible that, in the case of the Markov dependence with the irreducible matrix P, an analog of Theorem 1 takes place. The role of the entropy of the vector pγ in this case plays the conditional entropy of the matrix Pγ rows with the weights equal to the corresponding components of the vector w. We will discuss this fact in another publication.It should be noted that mean values defined by other type recurrent relations occur in the process of analyzing the digital trees (cf. formula (10) and the recurrent relation for AN, where N is a natural number, in [18, p. 404]). Nevertheless, the results for these values almost wholly coincide with Theorem 2 (see [19]). These results were obtained using the Mellin transform. The Mellin transform may also be useful for our case but it is a discussible problem.



---

*Source: 9143747-2017-05-07.xml*