# What are some heuristics to minimize how many states to choose to maximize the cumulative probability in a discrete probability distribution?

Obviously, we could just choose all the states and get 100% probability. That would maximize the probability, but not minimize the number of states we'd have to choose.

The other extreme would be to just choose zero states, but we won't get any cumulative probability here.

So, my question is, are there any mathematically elegant, or statistically-established ideas which give us a 'middle' way?

Intuitively, I'm looking for a modification of the 80:20 rule, so that I can say x number of states give a cumulative probability of y%.

I apologize if I'm not using the right language. I have not studied probability distribution formally.

-
The question is very unclear. I cannot understand what you are trying to do. What information do you have about the probability distribution that you are trying to use to construct this discrete distribution? – Michael Chernick Aug 13 '12 at 11:15
Are you saying that you have a known discrete probability distirbution on a set of states and you want to choose a certain number of states that have large cumulative probability of occurrence? If this is the case what is the context of the problem? – Michael Chernick Aug 13 '12 at 12:20

Obviously, to choose $n$ elements $X = \{x_1, x_2, \dotsc, x_n\}$ of a finite set $S$ so as to maximize their combined probability $P(X) = P(x_1) + P(x_2) + \dotsb + P(x_n)$, we may simply sort the elements of $S$ in descending order of probability and take the $n$ first ones.

Similarly, to choose the smallest subset $X \subset S$ that has at least some given combined probability $P(X) \ge P_\min$, we may again sort the elements of $S$ in descending order of probability and take as many elements, starting from the first, as we need to reach the desired combined probability $P_\min$.

If you desire some more complicate tradeoff between the number of chosen elements and their combined probability, you should first try to make clear what that tradeoff should be. In any case, for any preference function $f: \mathcal P(S) \to \mathbb R$ that satisfies $f(X) \ge f(X')$ whenever $|X| \le |X'|$ and $P(X) \ge P(X')$, the subset maximizing $f$ can always be found by sorting the elements of $S$ in descending order of probability and taking the first $k$ elements for some $k$; however, there may or may not be any way to determine the optimal value of $k$ except by trying all values from $0$ to $|S|$.

(To prove this, note that, for any $X \subset S$, the set $X' = \{x_1, x_2, \dotsc, x_n\}$, where $n = |X|$ and $x_1, x_2, \dotsc, x_{|S|}$ are the elements of $S$ sorted in descending order of probability, has $|X'| = |X|$ and $P(X') \ge P(X)$, and thus $f(X') \ge f(X)$.)

-

It looks like your state space is finite, so let its size be $N$. If we take $n$ most probable states, their total probability is $P(n)$. This is an increasing concave function. What would be a mathematically elegant way to pick "small" $n$ with "large" $P(n)$? (I can't tell you what is established in statistics.)

One way is to maximize $(N-n)P(n)$. An attractive feature of the product is that both extremes $n=N$ and $n=0$ lose automatically. Also, the product is a concave function, which guarantees that the maximum is unique.

Another way is to look for solution of $n/N+P(n)=1$. Here we have an increasing function of $n$, so even though we are unlikely to hit $1$ exactly, there will be just two candidates for approximate solution. The advantage of the second method is that it looks good in headlines, especially if the solution happens to be $n=0.01N$. The 80-20 rule falls into this category as well.

From the mathematical point of view I prefer the first method, which involves no choice. I tried it on a very simple distribution: total points on a pair of dice. Here $N=11$ and the product is maximized by taking $n=5\approx 45\%$ most likely outcomes, with total probability $2/3\approx 67\%$. Sounds good?

I'd be interested in comparing these two approaches in a "real-world" example: If someone wanted to grab attention on Meta.SE with the headline "x% of users have y% of reputation points" (or give y% of all answers), what would be the most effective combination of $x$ and $y$?

-