4
$\begingroup$

recently I have a problem about the multinomial distribution. Here, for positive integer $n$,

$ t_{n}=\sum_{i=1}^{n}a^{i}\sum_{i_{1},\ldots i_{n}}\left(\begin{array}{c} i\\ i_{1},\ldots i_{n} \end{array}\right)p_{1}^{i_{1}}\ldots p_{n}^{i_{n}} $ where $a\in\left(0,1\right)$. But the second summation has two conditions: $ \begin{cases} i_{1}+i_{2}+\cdots+i_{n}=i\\ i_{1}+2i_{2}+\cdots+ni_{n}=n \end{cases} $

In this case, can you obtain an easier expression for $t_n$. Actually, what I need is this:

I know $\sum_{i=1}^{\infty}p_{i}=1$, and $\lim_{n\rightarrow\infty}\frac{p_{n+1}}{p_{n}}=c\in\left(0,1\right)$. Under these conditions, I need to get the limit of $t_{n}$ ratio, i.e., $\lim_{n\rightarrow\infty}\frac{t_{n+1}}{t_{n}}$.

From the above expression, can I get the expression of $\lim_{n\rightarrow\infty}\frac{t_{n+1}}{t_{n}}$? Thank you in advance.

1 Answers 1

4

The problem can (and, I think, must) be moved into the realm of generating functions and power series.

We can set up the power series $ \begin{split} F(a,u) =&\sum_{n=0}^\infty t_nu^n =\sum_{k,n\ge 0} a^k u^n \sum_{\substack{i_1,i_2,\ldots\\ \sum i_j=k\\ \sum ji_j=n}} {k\choose i_1,i_2,\ldots} p_1^{i_1}p_2^{i_2}\cdots \\ =&\sum_{k=0}^\infty a^k\cdot(p_1u+p_2u^2+\cdots)^k \\ =&\frac{1}{1-ap(u)} \quad\text{where}\quad p(u)=p_1u+p_2u^2+\cdots \end{split} $ where for convenience we set $t_0=1$. We may note that this allows for a recursive expression for $t_n$ by noting that $\sum t_nu^n=1+ap(u)\cdot\sum t_nu^n$ which, if we pull of the $u^n$ term on both sides yields $ t_n=a\cdot\sum_{j=0}^n p_jt_{n-j} \quad\text{for}\quad n\ge1. $

The stated conditions on the $p_i$ tell us that $p(0)=0$, $p(1)=1$ and $p(u)$ has convergence radius $1/c$.

The properties of $t_n$ are determined by the convergence radius of the series $F(a,u)$ in terms of $u$ (which will depend on $a$).

We now find the smallest positive solution $r_a>0$ to $ap(r_a)=1$. The denominator $1-ap(u)$ of $F(a,u)$ will then become zero at $u=r_a$, and so this limits the convergence radius. Since the coefficients $p_i\ge0$, we can be sure there is no other solution $z\in\mathbb{C}$ to $ap(z)=1$ with $|z|. So, we get $\lim_{n\rightarrow\infty}\frac{t_{n+1}}{t_n} =\frac{1}{r_a} \quad\text{where}\quad ap(r_a)=1. $ In fact, using theorem 2 in Bender, 1978, (or there are probably also ways of proving this without the theorem), and assuming $ap(z)=1$ has no other solution for $|z|\le r_a$ than $z=r_a$ (I suspect $p_1>0$ is sufficient to ensure this), we have $ t_n\sim\frac{ap'(r_a)}{r_a^{n+1}} \quad\text{where}\quad f_n\sim g_n\stackrel{\text{def}}{\iff}\lim_{n\rightarrow\infty}\frac{f_n}{g_n}=1 $ since $F(a,u)\cdot(1-ap(u))/(r-u)=1/(r-u)$ allows us to express the asymptotics of the coefficients $t_n$ of $F(a,u)$ in terms of the coefficients of the power series of $1/(r-u)$.

The only remaining problem is what happens if $ap(r_a)=1$ has no solution for $0. This can happen if $p(u)$ is bounded as $u\rightarrow 1/c$ from below. However, since $p(u)$ has convergence radius $1/c$, $F(a,u)$ cannot have higher convergence radius, so if this is the case we end up with convergence radius $1/c$ in $u$ for $F(a,u)$ as well. This ensures $\limsup\sqrt[n]{t_n}=1/c$, but proving that $t_{n+1}/t_n\rightarrow 1/c$ would be a bit more technical (and have some additional requirements).


Just a few examples and counterexamples where things become more difficult.

1) Let $m>1$ be a natural number, and assume $p_{mk}=p'_k$ while $p_j=0$ for all $j$ not divisible by $m$. Then, $t_n=0$ for all $n$ not divisible by $m$.

I suspect the main results (based on $ap(r_a)=1$) should hold for as long as no such $m>1$ exists. If such a $m>1$ does exist, the same result will apply to the sequence $t'_{k}=t_{mk}$ expressed in terms of $p'_k=p_{mk}$.

2) Let $p_k=\alpha c^k/k^m$ where $\alpha$ is a normalisation constant and $m>1$. Then, $p(u)$ will have convergence radius $1/c$, but $p(1/c)=\alpha\zeta(m)$. If $m>2$, we even get $p'(1/c)=\alpha\zeta(m-1)/c<\infty$.

3) This counterexamples violates the condition that $p_{n+1}/p_n\rightarrow c$, but I'll leave it in place anyway. Let $p_{2^n}=\alpha c^{2^n}/(n+1)^m$, while other $p_k$ are zero, and where $\alpha$ is a normalisation constant. The $t_k$, while still declining, will no longer be strictly decreasing, but instead have have jumps to higher values at each $k=2^n$ in line with the non-zero $p_k$.


Here are some references I've had use for previously. At second thought, I'm not sure how strongly they are needed for this case, but I'll let them be. The main one gives several useful results, including more accurate description of the asymptotic properties of the $t_n$ in multiple cases:

Bender, E.A. 1974. Asymptotic methods in enumeration. SIAM Rev. 16, 485–515.

A notification of a technical error in this article occurs here:

Canfield, E. 1984. Remarks on an asymptotic method in combinatorics. J. Combin. Theory Ser. A 37, 348–352.

Here's another reference I used once when applying this method. I believe it may help ensure that the techincal problem Canfield pointed out is not an issue (under certain conditions), but don't remember too well so I'm not sure if it will apply to this case.

Meir, A., and Moon, J. 1989. On an asymptotic method in enumeration. J. Combin. Theory Ser. A 51, 77–89.

  • 0
    @Chang Actually, once intimately familiar with the use of generating functions, and I've been using generating functions a lot over the years, setting up $F(a,u)$ is a pretty obvious and straight forward exercise. Generating functions are extremely powerful tools which often allow complex sums or combinatorial problems to be reduced to simple algebra or analysis on the functions (as functions or formal power series).2012-09-18