Solved – Sum of coefficients of multinomial distribution

The present question is a specific case where you are dealing with a quantity that is a linear function of a multinomial random variable. It is possible to solve your problem exactly, by enumerating the multinomial combinations that satisfy the required inequality, and summing the distribution over that range. In the case where $N$ is large this may become computationally infeasible. In this case it is possible to obtain an approximate distribution using the normal approximation to the multinomial. A generalised version of this approximation is shown below, and then this is applied to your specific example.

General approximation problem: Suppose we have a sequence of exchangeable random variables with range $1, 2, …, m$. For any $n in mathbb{N}$ we can form the count vector $boldsymbol{X} equiv boldsymbol{X} (n) equiv (X_1, X_2, …, X_m)$, which counts the number of occurences of each outcome in the first $n$ values of the sequence. Since the underlying sequence is exchangeable, the count vector is distributed as:

$$begin{array} boldsymbol{X} text{ ~ Mu}(n, boldsymbol{theta}) & & boldsymbol{theta} = lim_{n rightarrow infty} boldsymbol{X}(n)/n. end{array}$$

Now, suppose we have some vector of non-negative weights $boldsymbol{w} = (w_1, w_2, …, w_m)$ and we use these weights to define the linear function:

$$A(n) equiv sum_{i=1}^m w_i X_i.$$

Since the weights are non-negative, this new quantity is non-decreasing in $n$. We then define the number $N(a) equiv min { n in mathbb{N} | A(n) geqslant a }$, which is the smallest number of observations required to obtain a specified minimum value for our linear function. We want to approximate the distribution of $N(a)$ in the case where this value is (stochastically) large.

Solving the general approximation problem: Firstly, we note that since $A(n)$ is non-decreasing in $n$ (which holds because we have assumed that all the weights are non-negative), we have:

$$mathbb{P} (N(a) geqslant n) = mathbb{P} (N(a) > n – 1) = mathbb{P} (A(n-1) < a).$$

Hence, the distribution of $N$ is directly related to the distribution of $A$. Assuming that the former quantity is large, we can approximate the distribution of the latter by replacing the discrete random vector $boldsymbol{X}$ with a continuous approximation from the multivariate normal distribution. This leads to a normal approximation for the linear quantitiy $A(n)$, and we can calculate the moments of this quantity directly. To do this, we use the fact that $mathbb{E}(X_i) = n theta_i$, $mathbb{V}(X_i) = n theta_i (1 – theta_i)$ and $mathbb{C}(X_i, X_j) = -n theta_i theta_j$ for $i neq j$. With some basic algebra, this gives us:

$$mu equiv mathbb{E}left(frac{1}{n} A(n)right) = sum_{i=1}^m w_i theta_i,$$

$$sigma^2 equiv mathbb{V}left(frac{1}{sqrt{n}} A(n)right) = sum_{i=1}^m w_i theta_i – left(sum_{i=1}^m w_i theta_iright)^2 = mu (1 – mu).$$

Taking the normal approximation to the multinomial now gives us the approximate distribution $A(n) text{ ~ N} (n mu, n mu (1 – mu))$. Applying this approximation yields:

$$mathbb{P} (N(a) geqslant n) = mathbb{P} (A(n-1) < a) approx Phi left(frac{a – (n-1) mu}{sqrt{(n-1) mu (1 – mu)}}right).$$

(The symbol $Phi$ is the standard notation for the standard normal distribution function.) It is possible to apply this approximation to find probabilities pertaining to the quantity $N(a)$ for a specified value of $a$. This is a basic approximation which has not attempted to incorporate continuity correction on the values of the underlying multinomial count values. It is obtained by taking a normal approximation using the same first two central moments as the exact linear function.

Application to your problem: In your problem you have probabilities $boldsymbol{theta} = (tfrac{1}{2}, tfrac{1}{6}, tfrac{1}{3})$, weights $boldsymbol{w} = (0, ln 2, ln 3)$, and cut-off value $a = ln 100000$. You therefore have (rounding to six decimal points) $mu = tfrac{1}{6}ln 2 + tfrac{1}{3}ln 3 = 0.481729$. Applying the above approximation we have (rounding to six decimal points):

$$mathbb{P}(N(a) geqslant 25) approx Phi left(frac{ln 100000 – 24 cdot 0.481729}{sqrt{24} cdot 0.499666}right) =Phi (-0.019838) = 0.492086.$$

By application of the exact multinomial distribution, summing over all combinations satisfying the requirement $mathbb{P}(A(24) < a)$, it can be shown that the exact result is $mathbb{P}(N(a) geqslant 25) = 0.483500$. Hence, we can see that the approximation is quite close to the exact answer in the present case.

Hopefully this answer gives you an answer to your specific question, while also placing it within a more general framework of probabilistic results that apply to linear functions of multinomial random vectors. The present method should allow you to obtain approximate solutions to problems of the general type you are facing, allowing for variation in the specific numbers in your example.