3
$\begingroup$

For $n\in\mathbb{N}$, the probability that a random subset of $[n]=\{1,\cdots n\}$ has cardinality at most $k$ is $f_k(n)=2^{-n}\sum\limits_{i=0}^k{n\choose i}$. I'm looking for a lower bound $g_k(x)\leq f_k(x)$ such that $g_k(x)=\Omega(2^{-x}x^k)$ and $g_k$ is convex on $[0,\infty)$.

$\endgroup$
6
  • $\begingroup$ Probably a bit clarification of the notation $g_k(x)=\Omega(2^{-x}x^k)$ will help, and you should also be consistent about the usage of $x$ and $n$ $\endgroup$
    – Henry.L
    Jun 22, 2017 at 12:16
  • $\begingroup$ @Henry.L I guess the change from $n$ to $x$ is to indicate that $g_k$ may not only be defined for integers. The "big Omega" notation is standard in computer science, but maybe some explanation would be needed on this cite ... $\endgroup$
    – WhatsUp
    Jun 22, 2017 at 14:09
  • $\begingroup$ you mean $\Omega$ for a fixed $k$? Else this is not true even without convexity. $\endgroup$ Jun 22, 2017 at 15:15
  • $\begingroup$ Yes, $k$ is fixed. $\endgroup$
    – Ray Bees
    Jun 22, 2017 at 16:53
  • $\begingroup$ For some additional inspiration, you may like: mathoverflow.net/questions/247553/… $\endgroup$
    – Suvrit
    Jun 22, 2017 at 17:42

1 Answer 1

1
$\begingroup$

$f_k$ is positive, convex and decreasing approximately exponentially for large enough $x.$ I'll show below that for $x \gt 2k+1,$$$2^{-x}\binom{x}{k} \lt f_k \lt (1+\frac{k}{x-2k})2^{-x}\binom{x}{k}.$$ I suspect that just a hair before $x=2k$ is where $f_k$ it becomes convex. For an asymptotically good convex lower bound you can just use $g_k=f_k$ itself, for large enough $x.$ Since you want your bound to start at $x=0$ you need to decide where to start using $f_k$ and what to do before that. I suspect that you could set $g_k(0)=1-\frac1k$, descend linearly to $(3k+1,f_k(3k+1))$ and follow $f_k$ from there. The starting point could get moved up, though not all the way to $1$ and the transition point made a bit earlier but probably not before $2k$.

If you want a simple but good lower bound then a similar modification of $2^{-x}\binom{x}{k}$ , perhaps starting around $x=3k$ would work well (with a linear portion before that.) $2k+\sqrt{2k}$ might be enough but I didn't investigate carefully where the best starting points are.

$f_k(x)=1$ for $x=0,1,2,3,4,\cdots,k$ and is alternately above and below $1$ (or below and above, depending on the parity) between them, although not by very much. After $x=k$ (also slightly before) it decreases getting to $\frac12$ at $2k+1.$ Then it continues decreasing approximately exponentially to $0$ as seen by the bounds above.

Here, for $k$ up to $40$ are the first integer $x$ where the tangent line hits the $y$-axis below $(0,1):$

$[2, 7], [3, 10], [4, 13], [5, 15], [6, 18], [7, 20], [8, 23], [9, 25], [10, 28], $ $[11, 30], [12, 33], [13, 35], [14, 38], [15, 40], [16, 42], [17, 45], [18, 47], [19, 49], [20, 52],$ $ [21, 54], [22, 56], [23, 59], [24, 61], [25, 63], [26, 66], [27, 68], [28, 70], [29, 73], [30, 75],$ $ [31, 77], [32, 79], [33, 82], [34, 84], [35, 86], [36, 89], [37, 91], [38, 93], [39, 95], [40, 98]$


For $n$ (or $x$) reasonably large relative to $k,$ the last few terms of $f_k$ are much more important than the rest. Their ratios working down from the last one are: $\frac{k}{n-k} \gt \frac{k-1}{n-k+1}\gt \cdots.$ So a lower bound is the last term $2^{-n}\binom{n}{k}$ and an upper bound is $(1+\frac{k}{n-2k})2^{-n}\binom{n}{k}.$ The upper bound comes from taking $\sum_0^{\infty}{r^j2^{-n}\binom{n}{k}}$ for $r=\frac{k}{n-k}.$ One can adjust to take the last few terms exactly for closer bounds.

As pointed out by Ray, $2^{-x}\binom{x}k$ is $0$ at $0,1,2,..k-1$ and alternately positive and negative between them. However, not long after $x=2k$ it does seem to become convex. For example some place between $45$ and $46$ for $k=20.$

$\endgroup$
1
  • $\begingroup$ $2^{-n}{n\choose k}$ isn't convex unless $k=0$. $\endgroup$
    – Ray Bees
    Jun 22, 2017 at 17:38

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.