2
$\begingroup$

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case when the parts are bounded: $a_i\in\{0, 1, \ldots, j-1\}$. The number of such compositions satisfies the two-variable recurrence \begin{equation} \kappa(n,j,k)=\sum_{i=0}^{j-1}\kappa(n-i,j,k-1) \end{equation} and can be expressed as \begin{equation} \kappa(n,j,k) = \sum_{s\geq0} (-1)^s {k \choose s} {k-sj+n-1 \choose k-1} \end{equation} [R. P. Stanley, Enumerative Combinatorics, Vol. I, p. 307]. Does someone know how to find the asymptotics of $\kappa(n,j,k)$ when $k\to\infty$, $n\sim\lambda k$, $\lambda\in(0,j-1)$, and $j$ is fixed? In particular, I would like to determine \begin{equation} \lim_{k\to\infty,\ n = \lambda k} (\kappa(n,j,k))^{\frac{1}{k}} =\ ? \end{equation}

$\endgroup$
3
$\begingroup$

Up to a factor of $j^k$, What you're asking for is the probability $P$ that a k-step random walk with steps chosen uniformly from $S = \{0, 1, ..., j-1\}$ lands on $\lambda n$. This is the probability of return to the origin at time $k$ of the (typically biased) random walk with steps chosen uniformly from $S - \lambda = \{-\lambda, -\lambda+1, \dots, -\lambda + j-1\}$.

If we choose some $t$ and bias this random walk so that $-\lambda+r$ has probability $t^{-\lambda + r}/Z_t$, we are multiplying the probability of return to the origin by $(j/Z_t)^{k}$. But we can choose $t$ so that this new random walk is unbiased, in which case its probability of return to the origin is roughly proportional to $k^{-1/2}$.

So, $P \sim k^{-1/2 }j^{-k}Z_t^k$, and the number you're interested in is roughly

$$k^{-1/2} Z_t^k.$$

All that remains is to find the values of $t$ such that this new random walk is unbiased, but this is the value that maximizes the probability of return to the origin, i.e. the value for which $$Z_t = \sum_{r=0}^{j-1} t^{-\lambda + r} = t^{-\lambda}\frac{t^j-1}{t-1}$$ is minimal.

So the number you're interested in is roughly

$$k^{-1/2} \rho^k,$$

where

$$\rho = \min_t t^{-\lambda}\frac{t^j-1}{t-1}.$$

You can get an explicit upper bound on $\rho$ by noting that, by convexity of the summands, $$\frac1j Z_t = \frac1j \sum_{r=0}^{j-1} t^{-\lambda + r} \leq \frac{1}{2}(t^{-\lambda} + t^{-\lambda+j-1}).$$ The optimal value of $t$ is $((j-1)/\lambda-1)^{-1/(j-1)}$, which gives

$$\rho \leq \frac{j}{2} \left( \left(\alpha^{-1}-1\right)^{\alpha} + \left(\alpha^{-1}-1\right)^{-(1-\alpha)} \right) = \frac{j}{2} \alpha^{-\alpha}(1-\alpha)^{-(1-\alpha)},$$ where $\alpha = \lambda/(j-1).$

$\endgroup$
  • $\begingroup$ @antonThank you for your answer. Note that $\kappa(n,2,k)={k \choose n}$ (compositions are binary sequences in this case), and so $\lim_{k\to\infty} (\kappa(\lambda k,2,k))^\frac{1}{k} = \lambda^{-\lambda}(1-\lambda)^{-1+\lambda}$ (by Stirling's approximation), which seems to violate your upper bound. Am I mistaken? $\endgroup$ – Mladen Dec 27 '14 at 14:57
  • $\begingroup$ Yes, I had made a mistake with the indexing. I've fixed it. The bound now agrees exactly with the right answer for $j=2$, as it should. $\endgroup$ – Anton Malyshev Dec 27 '14 at 17:50
  • $\begingroup$ I expect that this can be extended to exact asymptotics by using Berry-Esseen to derive a CLT and the log-concavity to infer a local CLT. $\endgroup$ – Brendan McKay Dec 28 '14 at 0:44
  • $\begingroup$ @antonThanks a lot, this is a nice approach. Differentiating wrt $t$ implies that $\rho$ is the positive real root of the polynomial $\sum_{r=0}^{j-1}(r-\lambda)t^r$. This seems to be the same characterization as the one obtained by the analytic approach suggested by Dr Wilson. I will try to get the exact value explicitly, but I don't know if that's possible (the above upper bound can be "loose", depending on what one needs of course, e.g., for $\lambda=1/2$ and $j=4$ one obtains $\rho\approx2.56$, whereas the bound yields $3.138...$). $\endgroup$ – Mladen Dec 28 '14 at 15:03
  • $\begingroup$ Yeah, I optimized that bound for being reasonably good near $\lambda = (j-1)/2$, if you're looking near $\lambda = 0$ or $\lambda = j-1$, you can fruitfully approximate the finite geometric series for $Z_t$ with an infinite one. $\endgroup$ – Anton Malyshev Dec 28 '14 at 21:25
3
$\begingroup$

Such problems can be solved routinely using the methods explained in the book by me and Robin Pemantle, Analytic Combinatorics in Several Variables (preprint version online at our websites, book published by Cambridge in 2013). The bivariate generating function for $\kappa(n,j,k)$ is $F_j(x,y) = 1/(1 - yf_j(x))$ where $f_j(x) = \sum_{i=0}^{j-1} x^i$. This simplifies to a nice rational function - use the standard smooth point formula for Riordan arrays (Section 12.2 as I recall) to get the desired results. I won't work out all details, because I am on vacation, but this is an absolutely standard application of our basic theory.

$\endgroup$
  • $\begingroup$ @markThanks a lot for the reference and the pointers, I'll work out the details... $\endgroup$ – Mladen Dec 28 '14 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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