3

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)$.

Henry.L
  • 7,951
Ray Bees
  • 31
  • 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$ – Henry.L Jun 22 '17 at 12:16
  • @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 ... – WhatsUp Jun 22 '17 at 14:09
  • you mean $\Omega$ for a fixed $k$? Else this is not true even without convexity. – Fedor Petrov Jun 22 '17 at 15:15
  • Yes, $k$ is fixed. – Ray Bees Jun 22 '17 at 16:53
  • For some additional inspiration, you may like: https://mathoverflow.net/questions/247553/binomx2-binomx4-cdots-binomx2u-is-a-convex-function-on-0-i – Suvrit Jun 22 '17 at 17:42
  • For your reference, the background in this post may be helpful https://mathoverflow.net/questions/275665/distributions-over-permutation-groups-mathcals-n – Henry.L Jul 23 '17 at 00:14

1 Answers1

1

$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.$

Aaron Meyerowitz
  • 30,015