2010–05–25 01^{23}

Multinomial expressions summation asymptotic approximations.

by

Jörgen Backelin

Abstract The asymptotic behaviour with respect to n of sums of type

∑_{i_{1},...,i_{r}} ∏_{j=1}^{r} v_{j}^{i_{j}} \binom{n}{i_{1}, …, i_{r}} ρ^{−f(i_{1},...,i_{r})}

is determined, where the w_{j} are positive weights, and f(i_{1}, …, i_{r}) is the sum of some of the monomials i_{k}i_{m} (1 ≤ k < m ≤ r).

Summary.

In the study of probabilistic tournaments, questions arise about the asym= ptotic behaviour of the following type:

Consider a (simple and undirected) graph G = ([r], E) (for some positive integer r). Define a quadratic form f(x_{1}, …, x_{r}) as the sum of the monomials x_{j}x_{l} (1 ≤ j < l ≤ r), such that {j, l} ∈ E, and for every positive integer n form the multinomial coefficient sum

S(n) = ∑_{i_{1},...,i_{r}} \binom{n}{i_{1}, …, i_{r}} \frac{1}{2}^{−f(i_{1},...,i_{r})}

(sum over non-negative integers i_{1}, …, i_{r}, such that the multinomial coefficients are defined). The answer turns out to be that

S(n) ∼ C · α(G)^{n}

where α(G) is the independence number of G, and C is the number of independent sets of size α(G) in G.

It turns out that it is easier to prove a generalisation of this, where each term also has a weight factor ∏_{j} v_{j}^{i_{j}}, where the v_{i} are positive weights for the polynomial p. In this case, the independence number αG should be replaced by the maximal weight of an independent set in G, and C by the number of independent sets of maximal weight. This is formulated as the proposition infra, which also encompasses an estimate of the error term.

Remarks. The investigation was motivated by combinatorial problems, and the proof methods are elementary and purely combinatoric. However, i am indepted to Anders Martin-Lf and August Tsikh for pointing out that the results seem be related to those studied by analytic means, e.g., by Laplace’s method. The results e. g. may be interpreted in terms of the radius of convergence for the analytic function ∑ S(n)x^{n}.

Ola Hössjer pointed out that the sum can be interpreted as an expected value, which gives the moment generating function interpretation. E(rho^{S}), where S is weighted U-statistic, and that this also might lead to some generalisations.

Notation. In this note, “natural number” is taken to mean “non-negative integer”, and consequently N = {0, 1, 2, …}. The set of positive integers is denoted Z_{+}, and likewise R_{+} is the set of positive real numbers.

2010–05–25 01^{23} Multinomial expressions approximations

Multinotation will be used in an unstrict manner, with multiitems denoted by lowercase boldface letters, corresponding to slanted letters for their members; e.g., the same i may stand for either (i_{1}, …, i_{r}) or i_{1}, …, i_{r}, depending on the context, and v^{i} then may stand for the product ∏_{j} v_{j}^{i_{j}}. Likewise, the range of a sum mostly will be indicated and partly implied by the context; the reader should have no difficulty in filling in the details.

For any set S, its power set is P(S) =^{def} {D : D ⊆ S}. Set difference, denoted \, operates on P(S); A \ B = {x ∈ A : x ∉ B}.

The support of any real-valued function f : S ⟶ R is the set

supp F = {x ∈ A : f(x) ≠ 0} .

Interpreting an i ∈ R^{r} as a function from [r] to R, naturally we get supp i = {j : i_{j} ≠ 0}.

For any natural number n, [n] = {i ∈ N : 0 < i ≤ n}. All graphs considered are simple, undirected, and finite. Thus, we may write such a graph G as a pair (V, E), where |V | =^{def} (cardinality of V) < ∞, and

E ⊆ \binom{V}{2} =^{def} \{e ∈ P(V) : |e| = 2\} .

An independent set S in G is a subset of V, such that E ∩ \binom{S}{2} = ∅. An independent set which is maximal under set inclusion is called a basis. The set of all bases of G is denoted B(G), and is a subset of P(V). The independence number of G is

α(G) = max_{B∈B(G)}|B| .

Preliminaries. We shall investigate some sums involving multinomial coefficients (always assuming that the lower indices, here i_{1}, …, i_{r}, are natural numbers whose sum is the top one, n)

\binom{n}{i} = \binom{n}{i_{1}, …, i_{r}} = n! ∏_{j=1}^{r}(i_{j}!)^{−1} ,

and we start by reminding of some well-known properties of these. First, the multinomial theorem states that for any constants v_{1}, …, v_{r},

(1)  ∑_{i} \binom{n}{i}v^{i} = ∑_{i_{1},...,i_{r}} \binom{n}{i_{1}, …, i_{r}}v_{1}^{i_{1}} ⋯ v_{r}^{i_{r}} = (v_{1} + … + v_{r})^{n} .

Moreover, directly from the definition, for r ≥ 2 we may express the multinomial coefficient as a product of a simpler one and of a binomial coefficient: putting i = i′, i_{r} (i.e., letting i′ = (i_{1}, …, i_{r−1})),

(2)  \binom{n}{i} = \binom{n}{i_{r}}\binom{n − i_{r}}{i′} .

A weighted graph (V, E, ψ) is a graph G = (V, E) together with a (vertex) weight function ψ : V ⟶ R_{+}. By abuse of notation, the weighted graph also is called G. The weight function extends naturally to P(V) by

ψ(S) = ∑_{v∈S} ψ(v) .

Let K(G) be the maximal weight of a basis, and N(G) be the number of times this quantity is reached, i.e.,

K(G) = max_{B∈B(G)} ψ(B) , N(G) = |{B ∈ B(G) : ψ(B) = K(G)}| .

For G = (V, E), a subset C of V is a vertex cover, if e ∩ C ≠ ∅ for each edge e ∈ E. Equivalently, C is a vertex cover if and only if its complement V \ C is independent. Let C(G) be the set of all vertex covers which are minimal under set inclusion. Clearly,

C ∈ C(G) ⟺ V \ C ∈ B(G) .

Main result. The formulation given here is the one I found easiest to prove directly. Actually, in the original problem, there were no weights (or unit weights) on the vertices; I give this as a corollary. There is also a slight extension, where essentially the uniform ρ is replaced by different ρ for different edges {i, j}; this is given as a remark, after the proof.

Lemma. Let G = ([r], E, ψ) be a weighted graph, with weights v_{j} = ψ(j). Furthermore, let ρ be a fixed number strictly between 0 and 1. Finally, for each natural number n, put

S(n) = S_{G,v,ρ}(n) = ∑_{i} \binom{n}{i}ρ^{f(i)}v^{i} ,

where the sum is taken over those i = (i_{1}, …, i_{r}) ∈ N^{r} for which the multinomial coefficient \binom{n}{i} is defined and non-zero, and

f(i) = f_{G}(i) = ∑_{{v_{j},v_{l}}∈E} i_{j}i_{l} .

Then S(n) ∼ N(G)K(G)^{n}, i.e.,

lim_{n→∞} \frac{S(n)}{K(G)^{n}} = N(G) .

More precisely, there is some c > 0, such that S(n) − NK(G)^{n} = o((K(G) − c)^{n}), i.e., such that

lim_{n→∞} \frac{S(n) − N(G)K(G)^{n}}{(K(G) − c)^{n}} = 0 .

Corollary. With G = ([r], E), ρ, and f as above,

∑_{i} \binom{n}{i}ρ^{f(i)} ∼ |\{B ∈ B(G) : |B| = α(G)\}| · α(G)^{n} .

Proof outline. As seen in the statement, the precise value of ρ is unimportant. Indeed, the idea is to sum the “ρ-free” terms separately and to prove the asymptotic behaviour for them; and then to prove that the contribution of the other terms may be ignored. Thus, put K = K(G), N = N(G), and write

S(n) = T (n) + U(n) ,

where

T (n) = ∑_{i:f(i)=0} \binom{n}{i} ∏_{j=1}^{r} v_{j}^{n_{j}}

i.e, “T (n) is S(n) for the case ρ = 0”. The refined claim is that

(3)  T (n) ∼ NK^{n} ,
(4)  T (n) − NK^{n} = o((K − c)^{n}), and
(5)  U(n) = o((K − c)^{n}) ,

for some suitable constant c > 0.

The idea of the proof is first to prove (3) and (4) in full generality directly. With these facts established, clearly, the truth of the lemma for a particular weighted graph is equivalent to the claim (5) for that graph. Moreover, each U(n) ≥ 0, whence upper estimates will be enough to establish the result for a particular graph, in either the lemma or the (5) formulation. We proceed to do this by induction with respect to r, working with the lemma in the induction step proof, but applying (5) in the inductive assumption.

For (3) and (4), note, that f(i) = 0 if and only if supp i is an independent set, i.e., the complement of the support is a vertex cover, i.e., if and only if there is some C ∈ C(G), such that

v_{j} ∈ C ⟹ i_{j} = 0 .

By the multinomial theorem, the sum of the terms in T (n) taken over all i which are zero on a fixed C ∈ C of cardinality r − t, whence without loss of generality we may assume C = {t + 1, …, r}, is

∑_{(i_{1},...,i_{t})} \binom{n}{i_{1}, …, i_{t}} ∏_{j=1}^{t} v_{j}^{i_{j}} = W^{n} ,

where W = v_{1} + … v_{r} is the weight of the basis V \ C. The full sum T (n) by means of the principle of inclusion-exclusion is expressible by 2^{|C|} − 1 similar terms, whence the growth rate is determined by the c terms corresponding to the B(G) elements of maximal weight r − s. Each one of these terms equals K^{n}; all other terms will be of the form ±L^{n} with L < K, and thus will not contribute to the limit in (3). For (4), taking any c such that K − c is strictly greater than the second largest weight of independent sets will do.

Thus, indeed, (3) and (4) hold in full generality.

We now prove the lemma and equivalently (5) by induction with respect to r.

For r = 1, E = ∅, B(G) = {[1]}, K = v_{1}, N = 1, and indeed S(n) = T (n) = v_{1}^{n} = 1 · K^{n}.

Now, assume that r ≥ 2, and that the lemma and (5) hold for each graph with a strictly smaller number of vertices. Fix an arbitrary weighted graph G = ([r], E) with weights v, and a ρ. In order to prove the lemma for this G and ρ, we distinguish two cases, depending on the minimal valency in G.

First, if there is an isolated vertex in G, without loss of generality the last vertex, r, then r is contained in each basis of G. Put G′ = ([r − 1], E) with weights v′ = v_{1}, …, v_{r−1}; then N(G′) = N and K(G′) = K − v_{r}, for any i = i′, i_{r} we have f′(i′) = f(i) for f′ = f_{G′}, and by the inductive assumption there is a c′ > 0, such that

(6)  S′(n′) = S_{G′,v′,ρ}(n′) = ∑_{i′} \binom{n′}{i′}ρ^{f′(i′)}(v′)^{i′} ∼ N(K − v_{r})^{n′}

and

(7)  S′(n′) − N(K − v_{r})^{n′} = o((K − v_{r} − c′)^{n′}) ,

for n′ = i_{1} + … + i_{r−1}. Now, by (2), each term in S(n) may be rewritten as a product of an i_{r}-depending and an i_{r}-independent factor: \binom{n}{i}ρ^{f(i)}v^{i} = \binom{n}{i_{r}}v_{r}^{i_{r}} · \binom{n−i_{r}}{i′}ρ^{f′(i′)}(v′)^{i′}, which sums up to

S(n) = ∑_{i_{r}} \binom{n}{i_{r}}v_{r}^{i_{r}}S′(n − i_{r}) ;

and by (1), indeed

∑_{i_{r}} \binom{n}{i_{r}}v_{r}^{i_{r}}N(K − v_{r})^{n−i_{r}} = NK^{n} .

It just remains to give an upper estimate of the growth of ∑_{i_{r}} \binom{n}{i_{r}}v_{r}^{i_{r}}(S′(n − i_{r}) − N(K − v_{r})^{n−i_{r}}). Fix any c with 0 < c < min(c′, K − v_{r}); it is clearly sufficient to prove that for any ε > 0, there is an n_{0}, such that for any n > n_{0} we have

(8)  ∑_{i_{r}} \binom{n}{i_{r}}v_{r}^{i_{r}}(S′(n − i_{r}) − N(K − v_{r})^{n−i_{r}}) < ε(K − c)^{n} .

Now, by (7), there is an n′_{0}, such that

S′(n′) − N(K − v_{r})^{n′} < \frac{ε}{2}(K − v_{r} − c′)^{n′} < \frac{ε}{2}(K − v_{r} − c)^{n′}

for n′ ≥ n′_{0}. Hence, certainly, for n > n′_{0}, and putting ν = n − i_{r},

∑_{i_{r}} \binom{n}{i_{r}}v_{r}^{i_{r}}(S′(n − i_{r}) − N(K − v_{r})^{n−i_{r}})

< ∑_{i_{r}=0}^{n−n′_{0}} \binom{n}{i_{r}}v_{r}^{i_{r}} \frac{ε}{2}N(K − c − v_{r})^{n−i_{r}}) + ∑_{i_{r}=n−n′_{0}+1}^{n} \binom{n}{i_{r}}v_{r}^{i_{r}}S′(n − i_{r})

= ∑_{i_{r}=0}^{n} \binom{n}{i_{r}}v_{r}^{i_{r}} \frac{ε}{2}N(K − c − v_{r})^{n−i_{r}}) + ∑_{ν=0}^{n′_{0}−1} \binom{n}{ν}v_{r}^{−ν}S′(ν) · v_{r}^{n}

= \frac{ε}{2}(K − c)^{n} + g(n)v_{r}^{n} .

for a polynomial g of degree n′_{0} − 1. We thus have established “half of (8)”; for the other half, note that v_{r} = K − (K − v_{r}) < K − c, whence indeed

g(n) < \frac{ε}{2}(\frac{K − c}{v_{r}})^{n}

for all n greater than some n′′_{0}. Putting n_{0} = max(n′_{0}, n′′_{0}) directly yields (8), and we are through with the induction step in this case.

Finally, we should prove the lemma and (5) for G, in case G has no isolated vertices; i.e., if ⋃ E = [r]. In other words, each i_{j} appears as a factor in at least one of the terms in f(i). By choosing one such term for each j, and noting that no term could be chosen more than twice, for any natural numbers m and n we get

(9)  f(i) ≥ mn for all i with min_{j} i ≥ 2m and ∑_{j} i_{j} = n .

Employing that ρ < 1, we may apply this for some fixed m, such that ρ^{m} < K (∑_{j} v_{j})^{−1}. With this choice, we shall show that U(n) is bounded by a sum of 2mr + 1 terms, such that each one of the resulting 2mr + 1 sequences satisfies an (8) type of bound. By summing (and since U(n) is non-negative), indeed then (5) follows.

Thus, note that each i either has min i ≥ 2m, or for at least one j has i_{j} ∈ {0, …, 2m − 1}. Thus,

U(n) ≤ W (n) + ∑_{j=1}^{r} ∑_{k=0}^{2m−1} W_{jk}(n)

where

W (n) = ∑_{min i≥2m} \binom{n}{i}ρ^{f(i)}v^{i} ,

while, for each j and k,

W_{jk}(n) = ∑_{i_{j}=k} ; f(i)>0 \binom{n}{i}ρ^{f(i)}v^{i} .

By the assumption for m, indeed a^{m}(∑_{j} v_{j}) < K − c for some positive c, by (1) yielding

W (n) < ∑_{i} \binom{n}{i}ρ^{mn}v^{i} = (ρ^{m}(v_{1} + … v_{r}))^{n} = o((K − c)^{n}) .

For the remaining series, without loss of generality, it is enough to consider the W_{rk}. Put G′ = ([r − 1], E′) and f′ = f_{G′}, where E′ = E ∩ \binom{[r−1]}{2}. We consider a slightly modified vertex weighting v′ = (v′_{1}, …, v′_{r−1}), defined as follows:

v′_{j} = \{ \begin{matrix}ρ^{k}v_{j} & if \{j, r\} ∈ E; \\ v_{j} & else \end{matrix} .

Put K′ = K(G, v′), N′ = N(G, v′), and choose a c′ > 0, such that indeed S′(n) − N′(K′)^{n} = o((K′ − c′)^{n}), with S′ as in (6). Finally, define T′ and U′ in analogy with T and U, such that S′(n) = T′(n) + U′(n).

Treat k = 0 separately:

— For k = 0, v′ is the restriction of v; we may have K′ = K; but, even in this case,

W_{r0}(n) = U′(n) = o((K′ − c′)^{n})

is small enough.

— For k > 0, since any basis of maximal weight in G must contain either r or at least one neighbour j of r, and since v_{r} > 0 and v_{j} > v′_{j}, respectively, we get K′ < K. Moreover, applying the definitions and (2),

W_{rk}(n) = v_{r}^{k}\binom{n}{k}S′(n − k) .

Thus, choosing a c > 0 such that K − c > K′, indeed

W_{rk}(n) = O(n^{r}(K′)^{n}) = o((K − c)^{n}) .

Thus (5) is proven in this case too, whence the induction step and thus the entire lemma is proven.

Remark. The various factors v_{j}^{n_{j}} and ρ^{n_{i}n_{j}} may be treated in a more uniform manner, by noting that they may be rewritten exp((ln v_{j})n_{j}) and exp((ln ρ)n_{i}n_{j}), respectively. This motivates the following slightly extended formulation:

Let h(x_{1}, …, x_{r}) be an (in general inhomogenic) quadratic form, h(x) = b + ∑_{i} d_{i}x_{i} + ∑_{i<j} e_{ij}x_{i}x_{j}, with no variable squares terms, and such that all the second degree coefficients e_{ij} are nonpositive. Define a weighted graph G = ([r], E, ψ) by

E = {{i, j} : e_{ij} < 0} ,

and

ψ(j) = e^{d_{j}} .

Then, with N(G) and K(G) as before, the sum

S(n) = ∑_{i} \binom{n}{i}e^{h(i)} ∼ e^{b}N(G)K(G)^{n} ,

and there is a c > 0 with S(n) − e^{b}N(G)K(G)^{n} = o((K(G) − c)^{n}).

Actually, as an extension, this is rather virtual. The conclusions in the lemma do not depend on ρ; and (apart from the negligible constant e^{b}) the S(n) in the extension are squeezed between the lemma items with ρ = exp(min e_{ij}), and those with ρ = exp(max e_{ij} : e_{ij} ≠ 0).