I may as well write down how I've been attacking this, although I don't have a solution yet. Sequences $(p_i)$ of nonnegative integers with sum $r$ are in bijection with weakly increasing $r$-tuples $(n_1, n_2, \ldots, n_r)$ of positive integers. Specifically, given the sequence $(p_0, p_1, p_2, \ldots)$, form the sequence of partial sums $(q_1, q_2, \ldots)$ given by $q_i:=p_0+p_1+\ldots+p_{i-1}$. Let $n_j$ be the minimal $i$ for which $q_i \geq j$. For example, $(1,0,0,1,0,0,2,0,0,\ldots)$ corresponds to $(1, 4, 7,7)$. So, we want to compute the sum over all weakly increasing $r$-tuples and prove it is equal to $1/r!$.
For each weakly increasing $r$-tuple, let us sum instead over all $r!$ permutations of the $r$-tuple. So we can view our sum as being over all $r$-tuples of nonnegative integers, and we want to prove now that the sum is $1$. One difficulty is that some $r$-tuples will appear more than once. For example, $(1,4,7,7)$ will appear twice, because the permutation which switches the $7$'s stabilizes this quadruple. It turns out that the multiplicity of an $r$-tuples is precisely $\prod (p_i)!$. So, what we want to show is that
$$\sum_{n_1, n_2, \ldots, n_r \geq 0} \frac{1}{\prod (p_i)! \prod \binom{p_{k-1}+p_k+k}{k}} =1$$
Now, when none of the $n_i$ are equal to each other, and when none of them differ by $1$, the summand is
$$\frac{1}{n_1(n_1+1)n_2(n_2+1) \cdots n_r(n_r+1)} = \left( \frac{1}{n_1} - \frac{1}{n_1+1} \right) \cdot \left( \frac{1}{n_2} - \frac{1}{n_2+1} \right) \cdots \left( \frac{1}{n_r} - \frac{1}{n_r+1} \right).$$
This is set up beautifully to telescope. If I could just find a similar nice description for when the $n_i$ collide or are adjacent ...
Hi Yaroslav, With the additional hypothesis you are considering, I guess that the inequality can be proved following the text that you linked.
Fix any probability vector $(p_1,\ldots,p_k)$ and consider $E\subset \{1,\ldots, n\}^k$ such that
$$
E\subset\left\{(i_1,\ldots,i_k); \sum_{j}^ki_j=n\ \text{and }\ p_j\geq\frac{i_j}{n} \right\}
$$
For any element of $E$, we have
$$
\sum_{j}^k p_j\log p_j\leq \sum_{j=1}^k \frac{i_j}{n}\log p_j.
$$
Therefore
$$
-n\left(\sum_{j=1}^k-p_j\log p_j \right)\leq \sum_{j=1}^k i_j\log p_j.
$$
Exponentiating both sides we get
$$
\exp\left(-n\left(\sum_{j=1}^k-p_j\log p_j \right)\right)\leq p_1^{i_1}\ldots p_k^{i_k}.
$$
For the other hand, we have that
$$
1=(p_1+\ldots+p_k)^n=\sum_{i_1,\ldots,i_k}\frac{n!}{i_1!\ldots i_k!}p_1^{i_1}\ldots p_k^{i_k}\geq \sum_{(i_1,\ldots,i_k)\in E}\frac{n!}{i_1!\ldots i_k!}\exp\left(-n\left(\sum_{j=1}^k-p_j\log p_j \right)\right),
$$
where the first summation is taken over all sequences of nonnegative integer indices $i_1$ through $i_k$ such the sum of all $i_j$ is $n$.
So we get that
$$
\sum_{(i_1,\ldots,i_k)\in E}\frac{n!}{i_1!\ldots i_k!}\leq\exp\left(n\left(\sum_{j=1}^k-p_j\log p_j \right)\right)\leq e^{n H^*}.
$$
Best Answer
– Gjergji Zaimi, Aug 24 at 0:45
– Ira Gessel, Aug 24 at 3:53
– Max Alekseyev Aug 24 at 9:38