Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted
+50

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|<r_a$. 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<r_a<1/c$. 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.

share|improve this answer
    
Thank you so much @Einar. This idea is really impressive!! But I didn't quite understand the last part: "hence $\frac{t_{n+1}}{t_{n}}\rightarrow c$". I know that $F(a,u)$ cannot have higher convergence radius. But how can you get $\frac{t_{n+1}}{t_{n}}\rightarrow c$ from this? –  Chang Sep 17 '12 at 1:03
    
Ypu're right. I'm a little too quick in that step. The convergence radius dictates how fast $t_n$ may grow, but doesn't give the limit directly. Will correct the answer. –  Einar Rødland Sep 17 '12 at 2:13
    
Based on your answer, I think: as the convergence radius of $p(u)$ is $\frac{1}{c}>1$, and $p(1)=1$, the solution of $p(r_a)=\frac{1}{a}$ where $\frac{1}{a}>1$ should be between $1$ and $\frac{1}{c}$, i.e., $r_a\in (1,\frac{1}{c})$. And therefore, $\lim_{n\rightarrow \infty}\frac{t_{n+1}}{t_n}=\frac{1}{r_a}\in (c,1)$ Do you think it is right? –  Chang Sep 17 '12 at 2:49
    
@Chang: You're right. The solution to $r_a$ should have to be less than $1/c$ (by assumption), and hence provide a limit within the interval $(c,1)$. However, this still requires that such a solution exists. –  Einar Rødland Sep 17 '12 at 3:28
    
Thanks so much~~~I may need some time but I think can solve the remaining problems. Your idea of setting up $F(a,u)$ and the following analysis is really remarkable. Thank you~~ –  Chang Sep 18 '12 at 0:35
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.