# Phase transition in counting feasible solutions to knapsack problems?

Imagine that you have a normalized knapsack constraint with $$n$$ items and weights $$w_1,...,w_n$$ satisfying $$\sum_{i=1}^n w_i = 1$$. I'm trying to understand the behavior of the function

$$Z(c) = \#| S \subset \{1,...,n\} : \sum_{i \in S} w_i \leq c|.$$

Clearly if $$c = 0$$, then $$Z(c) = 0$$, and if $$c = 1$$ then $$Z(c) = 2^n$$. Are there any results on phase transition behavior for $$Z(c)$$ when the $$w_i$$ are drawn randomly?

I'm aware there are results, for example, for counting the number of solutions to constraint satisfiability problems, but I haven't seen similar results for a counting the feasible solutions to a knpasack constraint.

I don't have a reference for you, just a minor remark that is too large for a comment.

We assume $$w$$ is chosen as follows. Choose r.v. $$x\in[0,1]^n$$ uniformly at random (i.e., each $$x_i$$ is i.i.d. uniformly in $$[0,1]$$), then set $$w_i = x_i/X$$, where $$X=\sum_j x_j$$. Then with high probability, almost all sets $$S$$ will have $$\sum_{i\in S} w_i \sim 1/2$$:

Lemma 1. Let r.v. $$w$$ be chosen as above. With probability $$1-e^{-n/6}$$, for all $$\epsilon\in[0,1]$$, among the subsets $$S\subseteq\{1,\ldots,n\}$$, the fraction satisfying $$\textstyle\Big|1/2 - \sum_{i\in S} w_i\Big| \ge \epsilon$$ is at most $$2 e^{-n\epsilon^2/4}$$.

Proof. For any $$x$$, and $$X=\sum_{i=1}^n x_i$$ as described above, note that $$E[X] = n/2$$, so by a standard Chernoff bound the probability of the event $$X\le n/4$$ is at most $$e^{-n^2/6}$$. So, with probability at least $$1-e^{-n^2/6}$$, $$X\ge n/4$$.

Now fix any $$x$$ and $$w$$ with $$X\ge n/4$$, and fix $$\epsilon>0$$. To complete the proof we bound the fraction of subsets $$S$$ such that $$|1/2 - \sum_{i\in S} w_i| \ge \epsilon$$.

This fraction equals the probability that $$|1/2 - \sum_{i\in S} w_i| \ge \epsilon$$ for a random subset $$S\subseteq \{1,\ldots,n\}$$.

Because $$w=x/X$$, the condition $$|1/2 - \sum_{i\in S} w_i| \ge \epsilon$$ is equivalent to $$|X/2 - \sum_{i\in S} x_i| \ge \epsilon X$$.

Note that $$E_S[\sum_{i \in S} x_i] = X/2$$, so by a standard Chernoff bound $$\Pr_S\big[|X/2 - \textstyle\sum_{i\in S} x_i| \ge \epsilon X\big] \le 2\exp(-X\epsilon^2) \le 2\exp(-n\epsilon^2/4).$$ (The last step uses $$X\ge n/4$$.) $$~~\Box$$

We don't have to choose $$w$$ randomly to get the bound. Any $$w$$ with $$\max_i w_i = O(1/n)\sum_i w_i$$ will do.

Note that the result implies a sharp threshold in the following sense: for any $$c > 1/2$$, almost all sets $$S$$ will satisfy the given knapsack inequality $$\sum_{i\in S} x_i \le c$$. For any $$c < 1/2$$, almost none will.