Find a non-ascending sequence of non-zero probabilities $p_1,\dots,p_N$ s.t.
- the sum of probabilities is $1$ (i.e., a distribution), and
- maximizes the length of the sub-sequence $1/p_1,\dots,1/p_R$ where the sum is no greater than $N$.
Formally,
maximize $R$
s.t. $\sum_{i=1}^{N} p_i$ = 1 and $\sum_{i=1}^{R} 1/p_i \leq N$.
Observations:
If every $p_i=1/N$ then $R=1$.
If $p_i= (1-\varepsilon) / \sqrt{N}$ for $1 \leq i \leq \sqrt{N}$, and $p_i=\varepsilon/(N-\sqrt{N})$ for $\sqrt{N}+1 \leq i \leq N$, then $R=(1-\varepsilon)\sqrt{N}$. Is this a maximum for $R$?
Based on this answer, can we say that when $R$ is maximized, all $p_i$'s in the sub-sequence are equal?
I found an answer that very closely addresses the problem. Based on that, it is easy to see that observation 2 actually gives the maximum for $R$.