Distributions over sorted lists

Question

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.

Answer 1

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.

Answer 2

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