Maximum length sub-sequence of probability reciprocals

46 Views Asked by At

Find a non-ascending sequence of non-zero probabilities $p_1,\dots,p_N$ s.t.

  1. the sum of probabilities is $1$ (i.e., a distribution), and
  2. 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:

  1. If every $p_i=1/N$ then $R=1$.

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

  3. Based on this answer, can we say that when $R$ is maximized, all $p_i$'s in the sub-sequence are equal?

1

There are 1 best solutions below

0
On

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