<p>The answer is no, assuming we interpret Condition 2 as follows:</p>

<ol start="2">
<li>For every infinite sequence <span class="math-container">$X_1,X_2,\ldots$</span> with each <span class="math-container">$X_i$</span> in <span class="math-container">$[0,1]$</span>,
<span class="math-container">$$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y,n)} = 1.$$</span></li>
</ol>

<hr>

<p><strong>Lemma 1.</strong> <em>No function <span class="math-container">$F$</span> that satisfies the above condition is continuous (much less differentiable) in every <span class="math-container">$X_i$</span>.</em></p>

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

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

<p>Fix <span class="math-container">$\epsilon_1&gt;0$</span> such that 
<span class="math-container">$$F_1(1/2) - F_1(1/2+\epsilon_1) \le 1/2^{n_1}.$$</span>
(This is possible because <span class="math-container">$F_1$</span> is continuous, as <span class="math-container">$F$</span> is continuous in each <span class="math-container">$X_i$</span>.)</p>

<p>Meanwhile, by inspection
<span class="math-container">$$
\begin{aligned}
N_1(1/2+\epsilon_1) &amp;{} = (1 + n_1)/2^{n_1} &amp;&amp;{} = \Theta(n_1/2^{n_1}), &amp; \text{ while} \\
N_1(1/2) &amp;{} = \Big(1 + n_1 + {n_1 \choose 2}\Big)/2^{n_1} &amp;&amp;{} = \Theta(n_1^2/2^{n_1}).
\end{aligned}
$$</span></p>

<p><em>Case 1.1.</em> First consider the case that <span class="math-container">$F_1(1/2+\epsilon_1) \le n_1^{3/2}/2^{n_1}$</span>.</p>

<p>In this case, define <span class="math-container">$X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2$</span>.
Then
<span class="math-container">$$\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}).$$</span></p>

<p><em>Case 1.2.</em> Otherwise <span class="math-container">$F_1(1/2+\epsilon_1) &gt; n_1^{3/2}/2^{n_1}$</span>.</p>

<p>In this case, define <span class="math-container">$X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2 + \epsilon_1$</span>.
Then <span class="math-container">$$\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}).$$</span></p>

<p>So, at index <span class="math-container">$n=n_1$</span>, the ratio in question is either <span class="math-container">$O(1/\sqrt n)$</span> or <span class="math-container">$\Omega(\sqrt n)$</span>.</p>

<hr>

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

<p>By inspection, using that <span class="math-container">$n_2 \ge n_1^2$</span>,
<span class="math-container">$$
\begin{aligned}
N_2(1/2+\epsilon_2) &amp;{} = O((n_1^2 + n_2)/2^{n_2}) &amp;&amp;{} = O(n_2/2^{n_2}), &amp; \text{ while} \\
N_2(1/2) &amp;{} \ge {n_2 \choose 2}/2^{n_2} &amp;&amp;{} = \Theta(n_2^2/2^{n_2}).
\end{aligned}
$$</span></p>

<p><em>Case 2.1.</em> First consider the case that <span class="math-container">$F_2(1/2+\epsilon_2) \le n_2^{3/2}/2^{n_2}$</span>.</p>

<p>In this case, define <span class="math-container">$X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2$</span>.
Then
<span class="math-container">$$\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}).$$</span></p>

<p><em>Case 2.2.</em> Otherwise <span class="math-container">$F_2(1/2+\epsilon_2) &gt; n_2^{3/2}$</span>.</p>

<p>In this case, define <span class="math-container">$X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2 + \epsilon_2$</span>.
Then <span class="math-container">$$\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}).$$</span></p>

<p>So, at index <span class="math-container">$n=n_2$</span>, the ratio in question is either <span class="math-container">$O(1/\sqrt n)$</span> or <span class="math-container">$\Omega(\sqrt n)$</span>.</p>

<hr>

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

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

CC BY-SA 4.0
2020-05-26T21:50:25.193Z
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.
Asterix
CC BY-SA 4.0
2020-05-26T22:09:22.260Z
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.
Neal Young
CC BY-SA 4.0
2020-05-30T13:56:39.547Z
If you wouldn't mind, please check the proof.  As far as I can tell, it's correct.  Thanks.
Neal Young
CC BY-SA 4.0
2020-05-25T14:36:21.053Z
2020-05-26T22:08:58.413Z
2020-05-26T22:08:58.413Z
Neal Young
<p>Answering my own question, using the central limit theorem. </p>

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

<p>Now consider the quantity <span class="math-container">$Pr(\sum_{i=1}^n Z_i \leq Y)$</span>. We can write this in two ways</p>

<ol>
<li><p><span class="math-container">$$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)$$</span></p></li>
<li><p><span class="math-container">$$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}})$$</span></p></li>
</ol>

<p>The first expression is <span class="math-container">$N(X_1,...,X_n,Y)$</span>. </p>

<p>The second expression is the CDF of a sum of independent random variables <span class="math-container">$(Z_i-\mu_i)$</span> 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 <span class="math-container">$\frac{Y-\sum_{i=1}^n \mu_i}{\sqrt{\sum_{i=1}^n \sigma^2_i}}$</span>. That is, it converges to <span class="math-container">$\Phi(\frac{Y-\sum_{i=1}^n \mu_i}{\sqrt{\sum_{i=1}^n \sigma^2_i}}),$</span> where <span class="math-container">$\Phi(\cdot)$</span> is the standard normal CDF.</p>

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

CC BY-SA 4.0
2020-06-01T01:03:53.780Z
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.)
Neal Young
CC BY-SA 4.0
2020-06-01T15:20:55.343Z
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$.
Neal Young
CC BY-SA 4.0
2020-06-03T12:40:54.733Z
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](https://www.wolframalpha.com/input/?i=integral+%281%2Fsqrt%282*Pi%29%29+exp%28-x%5E2%2F2%29+from+-infinity+to+-sqrt%283%29)). 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?
Neal Young
CC BY-SA 4.0
2020-06-12T12:34:34.243Z
can you please clarify?  Thanks.
Neal Young
CC BY-SA 4.0
2020-05-31T21:58:48.410Z
2020-05-31T21:58:48.410Z
Asterix
<p>Is there an asymptotic approximation to the fraction of sets satisfying a knapsack feasibility constraint?</p>

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

<p><span class="math-container">$$N(X_1,...,X_n,Y) =  \frac{\# \{S: \sum_{i \in S} X_i \leq Y\}}{2^n}$$</span></p>

<p>I want to understand how the ``partial derivatives'' of <span class="math-container">$N$</span> behave when <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> change. That is, I want to compute some analogue of <span class="math-container">$\frac{\partial N}{\partial X_i}$</span> or <span class="math-container">$\frac{\partial N}{\partial Y}$</span>. As defined, the function <span class="math-container">$N$</span>'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.</p>

<p>More concretely, I want to know if there's a function <span class="math-container">$F(X_1,...,X_n,Y,n)$</span> such that </p>

<ol>
<li>F is differentiable in <span class="math-container">$X_1,...,X_n,Y$</span></li>
<li><span class="math-container">$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y)} = 1$</span></li>
</ol>

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

CC BY-SA 4.0
2020-05-18T23:45:04.527Z
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$?
D.W.
<counting-complexity><asymptotics>
Asymptotic Approximation to Number of Knapsack Solutions
Asterix
# Asymptotic Approximation to Number of Knapsack Solutions

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

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

**Tags:** counting-complexity, asymptotics

> **Comments:**
> **username_1**: 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$?  

---

## 2 answers

### Answer by username_2 on 2020-05-25. Score: 1

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

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

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  
> **username_2**: If you wouldn't mind, please check the proof.  As far as I can tell, it's correct.  Thanks.  

---

### Answer by username_0 on 2020-05-31. Score: 0

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.

> **Comments:**
> **username_2**: 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.)  
> **username_2**: 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$.  
> **username_2**: 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](https://www.wolframalpha.com/input/?i=integral+%281%2Fsqrt%282*Pi%29%29+exp%28-x%5E2%2F2%29+from+-infinity+to+-sqrt%283%29)). 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?  
> **username_2**: can you please clarify?  Thanks.  

---

