# Distributions over sorted lists

Say we have an ordered list of items

[a, b, c, ... x, y, z, ...]


I am looking for a family of distributions with support on the list above governed by some parameter alpha so that:

• For alpha=0, it assigns probability 1 to the first item, a above, and 0 to the rest. That is, if we sample from this list, with replacement, we always get a.
• As alpha increases, we assign higher and higher probabilities to the rest of the list, respecting the ordering of the list, following ~exponential decay.
• When alpha=1, we assign equal probability to all items in the list, so sampling from the list is akin to ignoring its ordering.

This is is very similar to the geometric distribution, but there are some notable differences:

• The geometric distribution distribution is defined over all natural numbers. In my case above, the list has fixed size.
• The geometric distribution isn't defined for alpha=0.
• You appear to describe a family of truncated geometric distributions. However, there are infinitely many families that qualitatively behave like your description. More to the point, then, would be to explain what you would like to use such a family for. – whuber Nov 20 '16 at 23:34
• Thanks @whuber Yes, I understand there are infinitely many distributions that fit this description. Any specific ones that come to mind? I have a system that currently picks the first element of this list (representing scores), but I want to randomize this choice (and parameterize this randomization). I am not looking for a particular type of "decay" based on alpha. As long as alpha=0 represents no randomization, i.e. pick the first element, 1 represents "pick any element", and alphas between 0 and 1 represent "something in between" these two alphas, it would be good enough. – Amelio Vazquez-Reina Nov 21 '16 at 1:21

Let's assume $r_i$, the rank of list element $i$, has a value in $\{0, 1, \ldots, n-1\}$ for a list with $n$ elements (ties can be broken randomly). Then we could define the probability of selecting $i$ to be:

$$p_i = \frac{\alpha^{r_i}}{\sum_{k=1}^n \alpha^{r_k}}$$

This is basically just an appropriately normalized truncated geometric distribution, and it is also related to the Softmax function. In the special case of $\alpha=0$, use the convention $0^0 = 1$. Note that the denominator can always be written in a simple closed-form expression. For $\alpha < 1$ it takes value $\frac{1-\alpha^n}{1-\alpha}$, and for $\alpha=1$ it takes value $n$.

With $\alpha=1$, it is clear that this just assigns equal probability to each element. As $\alpha\rightarrow 0$, this approaches giving all the probability mass to the first element.

In a list with 10 elements, the roughly exponential decrease you requested is clear with $\alpha=0.5$:

$$p_0 \approx 0.5005 \\ p_1 \approx 0.2502 \\ p_2 \approx 0.1251 \\ p_3 \approx 0.0626 \\ p_4 \approx 0.0313 \\ p_5 \approx 0.0156 \\ p_6 \approx 0.0078 \\ p_7 \approx 0.0039 \\ p_8 \approx 0.0020 \\ p_9 \approx 0.0010$$

The following plots how the probability of the first element being selected changes based on $\alpha$, using a list of length 10.

• Nice. This is way more clever than I could ever hope to be. – Matthew Drury Nov 21 '16 at 1:58
• @Matthew These are the truncated geometric distributions to which I referred earlier. – whuber Nov 21 '16 at 18:39

I'll try to build an example from first principles.

Let's take three distributions as our building blocks:

• P is the distribution assigning probability one to the first element of the list, zero to all others.
• E is the distribution assigning probability $\frac{1}{2}$ to the first element of the list, $\frac{1}{4}$ to the next, and so on. Since the list is finite, these will not sum to $1$, but we can normalize to get a probability distribution.
• U is the uniform distribution over the list.

Now we want to take a one-parameter family of positive convex combinations of these distributions

$$\alpha(t) P + \beta(t) E + \gamma(t) U$$

where $\alpha(t) + \beta(t) + \gamma(t) = 1$ for all $t \in [0, 1]$, with the additional property that $\alpha(0) = 1$ and $\gamma(1) = 1$.

Geometrically, we want $(\alpha(t), \beta(t), \gamma(t))$ to trace out a curve in the equilateral triangle spanned between the points $(1, 0, 0), (0, 1, 0), (0, 0, 1)$ which starts at the first corner, and ends and the last. Additionally, since we want the distribution to look "exponential" in the middle times, we would like the curve to occupy the interior of the triangle at times $t \in (0, 1)$.

Here's an option for the curve:

$$(1 - t(1-t)) \left(1 - t, 0, t \right) + t(1 - t) \left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right)$$

I constructed this working backwards from the properties we would like. The curve $(1-t, 0, t)$ runs along the edge of the triangle between the starting and ending verticies. The rest of the formula is just a convex sum of this edge curve and the single point $\left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right)$, which pushes the curve along the edge into the interior at times $t \in (0, 1)$.