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

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

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

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

<p>Now fix any <span class="math-container">$x$</span> and <span class="math-container">$w$</span> with <span class="math-container">$X\ge n/4$</span>, and fix <span class="math-container">$\epsilon&gt;0$</span>.  To complete the proof we bound the fraction of subsets <span class="math-container">$S$</span> such that <span class="math-container">$|1/2 - \sum_{i\in S} w_i| \ge \epsilon$</span>.  </p>

<p>This fraction equals the probability that <span class="math-container">$|1/2 - \sum_{i\in S} w_i| \ge \epsilon$</span> for a random subset <span class="math-container">$S\subseteq \{1,\ldots,n\}$</span>.</p>

<p>Because <span class="math-container">$w=x/X$</span>, the condition <span class="math-container">$|1/2 - \sum_{i\in S} w_i| \ge \epsilon$</span>
is equivalent to <span class="math-container">$|X/2 - \sum_{i\in S} x_i| \ge \epsilon X$</span>.</p>

<p>Note that <span class="math-container">$E_S[\sum_{i \in S} x_i] = X/2$</span>,
so by a standard Chernoff bound
<span class="math-container">$$\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).$$</span>
(The last step uses <span class="math-container">$X\ge n/4$</span>.) <span class="math-container">$~~\Box$</span></p>

<p>We don't have to choose <span class="math-container">$w$</span> randomly to get the bound.
Any <span class="math-container">$w$</span> with <span class="math-container">$\max_i w_i = O(1/n)\sum_i w_i$</span> will do.</p>

<p>Note that the result implies a sharp threshold in the following sense:
for any <span class="math-container">$c &gt; 1/2$</span>, almost all sets <span class="math-container">$S$</span> will satisfy the given knapsack inequality <span class="math-container">$\sum_{i\in S} x_i \le c$</span>.
For any <span class="math-container">$c &lt; 1/2$</span>, almost none will.</p>

CC BY-SA 4.0
2020-06-02T15:38:19.647Z
2020-06-02T15:44:09.090Z
2020-06-02T15:44:09.090Z
Neal Young
<p>Imagine that you have a normalized knapsack constraint with <span class="math-container">$n$</span> items and weights
<span class="math-container">$w_1,...,w_n$</span> satisfying <span class="math-container">$\sum_{i=1}^n w_i = 1$</span>. I'm trying to understand the behavior of the function</p>

<p><span class="math-container">$$Z(c) = \#| S \subset \{1,...,n\} : \sum_{i \in S} w_i \leq c|.$$</span></p>

<p>Clearly if <span class="math-container">$c = 0$</span>, then <span class="math-container">$Z(c) = 0$</span>, and if <span class="math-container">$c = 1$</span> then <span class="math-container">$Z(c) = 2^n$</span>. Are there any results on phase transition behavior for <span class="math-container">$Z(c)$</span> when the <span class="math-container">$w_i$</span> are drawn randomly?</p>

<p>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. </p>

<counting-complexity><phase-transition>
Phase transition in counting feasible solutions to knapsack problems?
Asterix
# Phase transition in counting feasible solutions to knapsack problems?

(Asked by: username_0 on 2020-05-05)

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.

**Tags:** counting-complexity, phase-transition

---

## 1 answers

### Answer by username_1 on 2020-06-02. Score: 2

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.


---

