3
$\begingroup$

How does one go about upper bounding the following expression/what is the tightest upper bound one can achieve?

$$\prod_{i = 1}^k A_i!$$ such that $$\sum_{i}^k A_i \leq C$$.

What is the tighest upper bound for the first expression in terms of C and k?

Note that the trivial upper bound for this expression is $((\frac{C-k}{e})^C)^k$ but can we do better than this?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

The Stirling approximation yields a good bound:

$$\prod_{i=1}^{k}A_i! \cong \prod_{i=1}^{k}\sqrt{2\pi A_i}\dot{} (\frac{A_i}{e})^{A_i}=\prod_{i=1}^{k}\sqrt{2\pi A_i}\prod_{i=1}^{k}(\frac{A_i}{e})^{A_i}$$ We can bound the first term on the right side by the known inequality: $$\prod_{i=1}^{k} A_i\leq (\frac 1 k \sum_{i}^k A_i)^k\implies\prod_{i=1}^{k}\sqrt{2\pi A_i}\leq(\frac{2\pi C}{k})^{k/2}$$

Now we shall bound the scound term using the fact $1\leq A_i\leq C-k$:

$$\prod_{i=1}^{k}(\frac{A_i}{e})^{A_i}=\exp[\sum_{i=1}^kA_i\log(\frac{A_i}{e})]\leq\exp[\log(\frac {C-k} e) \sum_{i=1}^kA_i]=(e^{(C-k)/e})^C$$ Combining the two we get: $$\prod_{i=1}^{k}A_i!\leq (\frac{2\pi C}{k})^{k/2}(e^{(C-k)/e})^C$$

$\endgroup$
6
  • $\begingroup$ What I need is a tighter bound than that provided by Stirling's if there is such a bound. The problem with Stirling's approximation is that it asymptotically diverges from the expression given by the factorial. $\endgroup$ May 6, 2017 at 16:42
  • $\begingroup$ Stirling does not diverge from the factorial. The limit of the Stirling approximation divided by the factorial is 1, and it converges very fast. $\endgroup$
    – Alon Yariv
    May 6, 2017 at 18:22
  • $\begingroup$ Be it as it my, there is some sense of inefficiency in my bound. Could you share the related problem? $\endgroup$
    – Alon Yariv
    May 6, 2017 at 18:28
  • $\begingroup$ Oh yes, you are correct. The bound doesn't diverge. Thanks for the answer. $\endgroup$ May 6, 2017 at 18:34
  • $\begingroup$ How did you get the part $\exp[\log(\frac {C-k} e) \sum_{i=1}^kA_i]=e^{C-k-1}\dot{}C$? Isn't this supposed to be $\exp[\log(\frac {C-k} e) \sum_{i=1}^kA_i]=(\frac{C - k}{e})^C$? $\endgroup$ May 6, 2017 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .