3
$\begingroup$

I need to figure out a nice family of decaying functions such that

$\sum_{d=2}^k {k \choose d} f_k(d) \leq 1/k$ and $f_k(d)\geq f_k(d+1)$

How can I figure out what good candidates could be? Any leads or ideas?

$\endgroup$
1
  • 5
    $\begingroup$ $k^{-2d}$ might do for a start. $\endgroup$ Feb 13, 2014 at 5:21

1 Answer 1

1
$\begingroup$

I managed to find a few alternatives:

Binomial Theorem

$f_k(d) = x^d$ works for any $x$ such that $(1+x)^k \leq 1/k + 1 + kx$. The suggested $1/k^2$ from The Masked Avenger is one such $x$, but solving for each $k$ in turn one can see that we can do far better than $1/k^2$.

Vandermonde's Identity

From the identity ${m+n \choose r} = \sum_{d=0}^r{m\choose k}{n\choose r-k}$ we can extract the function families

$f_k^m(d) = \frac{{m\choose k-d}}{{k+m\choose k}\cdot k}$

that provide a viable family of functions for each $m\geq k$. These functions are not monotonic, but they are only really needed for an upper bound, so that still works. The $m$ forms a kind of a shape parameter -- higher $m$ means more mass is concentrated early on, while a lower value for $m$ means larger mass allowed in the middle of the sequence.

In particular, the Vandermonde-derived bounds allow for a much slower decay, while the exponential bounds allow for a large amount of mass used early in the sequence.

$\endgroup$
3
  • $\begingroup$ Indeed, one can use something like 5k to replace k^2. Looks like you found something more suitable. $\endgroup$ Feb 13, 2014 at 21:08
  • $\begingroup$ Does this has anything to do with tying ties? $\endgroup$ Apr 14, 2014 at 20:56
  • $\begingroup$ No, this is unrelated to the tie-knot thing; it's for a complexity analysis of an algorithm. $\endgroup$ Apr 15, 2014 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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