1
$\begingroup$

Is there an asymptotic approximation to the fraction of sets satisfying a knapsack feasibility constraint?

More precisely, imagine I have a large number $n$ of items with bounded weights $X_1,...,X_n \in [0,1]$. For a given bound $Y$, I want to compute the fraction of sets $S \subset \{1,...,n\}$ which satisfy the feasibility constraint $\sum_{i \in S} X_i \leq Y$. That is, I want to compute:

$$N(X_1,...,X_n,Y) = \frac{\# \{S: \sum_{i \in S} X_i \leq Y\}}{2^n}$$

I want to understand how the ``partial derivatives'' of $N$ behave when $X$ and $Y$ change. That is, I want to compute some analogue of $\frac{\partial N}{\partial X_i}$ or $\frac{\partial N}{\partial Y}$. As defined, the function $N$'s partial derivatives are not very interesting: the function is constant, except at regions of discontinuity where the number of feasible sets changes, and at those points the derivatives do not exist.

More concretely, I want to know if there's a function $F(X_1,...,X_n,Y,n)$ such that

  1. F is differentiable in $X_1,...,X_n,Y$
  2. $\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y)} = 1$

I know that, when $X_1,...,X_n = 1$, then $N(X_1,...,X_n,Y)=\sum_{k=0}^{\lfloor Y \rfloor} \frac{\binom{n}{k}}{2^n}$, which converges to the normal CDF $\Phi(Y; \frac{n}{2}, \frac{n}{4})$. But I don't know if this kind of approximation generalizes to arbitrary bounded $X_i$.

$\endgroup$
1
  • 1
    $\begingroup$ Your condition 2 is missing some quantifiers. What do you want this to hold for? Do you want this to hold for all infinite sequences $X_1,X_2,\dots$? $\endgroup$ – D.W. May 18 '20 at 23:45
1
$\begingroup$

The answer is no, assuming we interpret Condition 2 as follows:

  1. For every infinite sequence $X_1,X_2,\ldots$ with each $X_i$ in $[0,1]$, $$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y,n)} = 1.$$

Lemma 1. No function $F$ that satisfies the above condition is continuous (much less differentiable) in every $X_i$.

Proof. Fix any candidate function $F$ that is continuous in each $X_i$. Fix $Y=1$. To complete the proof, we show there must be a sequence $X_1', X_2', \ldots$ such that $$\lim\inf_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1,n)} = 0$$ or $$\lim\sup_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1,n)} = \infty.$$

Start by fixing an arbitrarily large index $n_1$. To ease notation, for $z\in[0,1]$, define $$\begin{align} F_1(z) &{} = F(z, z, \ldots, z, 1, n_1), \text{ and } \\ N_1(z) & {}= N(z, z, \ldots, z, 1, n_1). \end{align}$$ (That is, the restrictions of $F$ and $N$ to $X_1=X_2=\cdots=X_{n_1}=z$, $Y=1$, and $n=n_1$.)

Fix $\epsilon_1>0$ such that $$F_1(1/2) - F_1(1/2+\epsilon_1) \le 1/2^{n_1}.$$ (This is possible because $F_1$ is continuous, as $F$ is continuous in each $X_i$.)

Meanwhile, by inspection $$ \begin{aligned} N_1(1/2+\epsilon_1) &{} = (1 + n_1)/2^{n_1} &&{} = \Theta(n_1/2^{n_1}), & \text{ while} \\ N_1(1/2) &{} = \Big(1 + n_1 + {n_1 \choose 2}\Big)/2^{n_1} &&{} = \Theta(n_1^2/2^{n_1}). \end{aligned} $$

Case 1.1. First consider the case that $F_1(1/2+\epsilon_1) \le n_1^{3/2}/2^{n_1}$.

In this case, define $X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2$. Then $$\frac{F(X'_1, \ldots, X'_{n_1}, 1, n_1)}{N(X'_1,\ldots, X'_{n_1}, 1, n_1)} = \frac{F_1(1/2)}{N_1(1/2)} \le \frac{F_1(1/2+\epsilon_1)+1/2^{n_1}}{N_1(1/2)} = O(1/\sqrt{n_1}).$$

Case 1.2. Otherwise $F_1(1/2+\epsilon_1) > n_1^{3/2}/2^{n_1}$.

In this case, define $X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2 + \epsilon_1$. Then $$\frac{F(X'_1, \ldots, X'_{n_1}, 1, n_1)}{N(X'_1,\ldots, X'_{n_1}, 1, n_1)} = \frac{F_1(1/2+\epsilon_1)}{N_1(1/2+\epsilon_1)} = \Omega(\sqrt{n_1}).$$

So, at index $n=n_1$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.


To continue, choose index $n_2 \ge n_1^2$, and set the values of $X'_{n_1+1}, X'_{n_1+2}, \ldots, X'_{n_2}$ as follows. Define $$\begin{align} F_2(z) &{} = F(X'_1, X'_2, \ldots, X'_{n_1}, z, z, \ldots, z, 1, n_2), \text{ and } \\ N_2(z) & {}= N(X'_1, X'_2, \ldots, X'_{n_1}, z, z, \ldots, z, 1, n_2). \end{align}$$ (Above, $z$ occurs $n_2-n_1$ times in each parameter list.) Fix $\epsilon_2>0$ such that $$F_2(1/2) - F_2(1/2+\epsilon_2) \le 1/2^{n_2}.$$ (This is possible because $F_2$ is continuous, as $F$ is continuous in each $X_i$.)

By inspection, using that $n_2 \ge n_1^2$, $$ \begin{aligned} N_2(1/2+\epsilon_2) &{} = O((n_1^2 + n_2)/2^{n_2}) &&{} = O(n_2/2^{n_2}), & \text{ while} \\ N_2(1/2) &{} \ge {n_2 \choose 2}/2^{n_2} &&{} = \Theta(n_2^2/2^{n_2}). \end{aligned} $$

Case 2.1. First consider the case that $F_2(1/2+\epsilon_2) \le n_2^{3/2}/2^{n_2}$.

In this case, define $X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2$. Then $$\frac{F(X'_1, \ldots, X'_{n_2}, 1, n_2)}{N(X'_1,\ldots, X'_{n_2}, 1, n_2)} = \frac{F_2(1/2)}{F_1(1/2)} \le \frac{F_2(1/2+\epsilon_2)+1/2^{n_2}}{N_2(1/2)} = O(1/\sqrt {n_2}).$$

Case 2.2. Otherwise $F_2(1/2+\epsilon_2) > n_2^{3/2}$.

In this case, define $X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2 + \epsilon_2$. Then $$\frac{F(X'_1, \ldots, X'_{n_2}, 1, n_2)}{N(X'_1,\ldots, X'_{n_2}, 1, n_2)} = \frac{F_2(1/2+\epsilon_2)}{N_2(1/2+\epsilon_2)} = \Omega(\sqrt{n_2}).$$

So, at index $n=n_2$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.


Continuing in this way, we can set $X'_1, X'_2, \ldots$ so that there is an infinite sequence of indices $1\le n_1 < n_2 < n_3 < \cdots$ such that, at each index $n=n_i$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.

Then either there are infinitely many indices $n$ such that the ratio is $O(1/\sqrt n)$, in which case $$\lim\inf_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1, n)} = 0,$$ or there are infinitely many indices $n$ such that the ratio is $\Omega(\sqrt n)$, in which case $$\lim\sup_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1, n)} = \infty.$$ $~\Box$

$\endgroup$
3
  • $\begingroup$ Thanks for the detailed argument. It holds when $N$ counts the number of knapsack solutions, but does not hold when $N$ is normalized by a denominator $2^n$. In this case, the argument that the ratio is either $O(1/\sqrt{n})$ or $\Omega(\sqrt{n})$ doesn't hold. I think the question as I posed it is true, and I give an answer below. $\endgroup$ – Asterix May 26 '20 at 21:50
  • $\begingroup$ But surely the $2^n$ term in $N$ is irrelevant, since for every $n$ you are looking at the ratio of $F/N$? I've edited the proof to take into account the $2^n$ factor. $\endgroup$ – Neal Young May 26 '20 at 22:09
  • $\begingroup$ If you wouldn't mind, please check the proof. As far as I can tell, it's correct. Thanks. $\endgroup$ – Neal Young May 30 '20 at 13:56
0
$\begingroup$

Answering my own question, using the central limit theorem.

Consider a random variable $Z_i = X_i$ with probability $\frac{1}{2}$, and $Z_i = 0$ with probability $\frac{1}{2}$. Note that each $Z_i$ is a random variable with mean $\mu_i = \frac{X_i}{2}$ and finite variance $\sigma^2_i = \frac{X_i^2}{4}.$ Note further that all realizations of $Z \in \{0,X_1\} \times \{0,X_2\} \times ... \times \{0,X_n\}$ have equal probability of occurring, and that this probability is $\frac{1}{2^n}$.

Now consider the quantity $Pr(\sum_{i=1}^n Z_i \leq Y)$. We can write this in two ways

  1. $$Pr(\sum_{i=1}^n Z_i \leq Y) = \sum_{Z} \frac{1}{2^n} I(Z_1 + ... + Z_n \leq Y) = \sum_{S : \sum_{i \in S} Z_i \leq Y} \frac{1}{2^n} = N(X_1,...,X_n,Y)$$

  2. $$Pr(\sum_{i=1}^n Z_i \leq Y) = Pr( \frac{\sum_{i=1}^n (Z_i-\mu_i)}{\sqrt{\sum_{i=1}^n \sigma^2_i}} \leq \frac{Y-\sum_{i=1}^n \mu_i}{\sqrt{\sum_{i=1}^n \sigma^2_i}})$$

The first expression is $N(X_1,...,X_n,Y)$.

The second expression is the CDF of a sum of independent random variables $(Z_i-\mu_i)$ normalized by the sum of their variances. Because all the variances are finite, this converges to the CDF of a standard normal distribution evaluated at $\frac{Y-\sum_{i=1}^n \mu_i}{\sqrt{\sum_{i=1}^n \sigma^2_i}}$. That is, it converges to $\Phi(\frac{Y-\sum_{i=1}^n \mu_i}{\sqrt{\sum_{i=1}^n \sigma^2_i}}),$ where $\Phi(\cdot)$ is the standard normal CDF.

Note that $\mu_i,\sigma^2_i$ are differentiable functions of $X_i$. If we write $$F(X_1,...,X_n) = \Phi(\frac{Y-\sum_{i=1}^n X_i/2}{\sqrt{\sum_{i=1}^n X_i^2/4}})$$ we get the desired result.

$\endgroup$
4
  • $\begingroup$ But, above, what do mean by converges? What is the role of $n$, specifically? In your post, you ask about convergence as $n\rightarrow \infty$, but in the argument above, you've fixed $n$. For fixed $n$, I don't understand what you could mean by converges. (This question seems directly related to the ambiguity in your post about quantifiers in Condition 2, as pointed out in the comments. If we interpret it as suggested there, and in my answer above, I don't see any flaw in my proposed proof that the answer is "no". Perhaps you have something in mind that is not clear from the post.) $\endgroup$ – Neal Young Jun 1 '20 at 1:03
  • $\begingroup$ Consider these examples, all with $Y=1$. (1) Take $X_i = 1/2$ for all $i$. Then $N(\ldots) \sim n^2/2^{n+1}$ and $F(\ldots) = \Phi(z_1)$ for $z_1=-\sqrt n + 4/\sqrt n$. (2) Take $X_i = 1/2+\epsilon/2^i$. Then $N(\ldots) \sim n/2^n$ and $F(\ldots) = \Phi(z_2)$ for $z_2=-\sqrt n + 4/\sqrt n + O(\epsilon/\sqrt n)$. (3) Take $X_i=1$ for all $i$. Then $N(\ldots)\sim n/2^n$ and $F(\ldots) = \Phi(z_3)$ for $z_3=-\sqrt n + 2/\sqrt n$. So you would need $\Phi(z_1)\sim n^2/2^{n+1}$ while $\Phi(z_2)\sim\Phi(z_3)\sim n/2^n$. This surely doesn't hold, as $z_2$ is much closer to $z_1$ than $z_3$. $\endgroup$ – Neal Young Jun 1 '20 at 15:20
  • $\begingroup$ Or consider $Y=0$ and $X_i = 1/2^i$ for $i \ge 1$. Then $N(\ldots)=1/2^n \rightarrow 0$ but $F(\ldots) = \Phi(-\sqrt 3(1-O(1/2^n)))$, which tends to a positive constant as $n\rightarrow\infty$ ($0.04\ldots$ according to Wolfram Alpha). So I think Condition 2 does not hold for your $F$. Perhaps Condition 2 as written in the post is not what you had in mind? $\endgroup$ – Neal Young Jun 3 '20 at 12:40
  • $\begingroup$ can you please clarify? Thanks. $\endgroup$ – Neal Young Jun 12 '20 at 12:34

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.