Matching quantile sets using likelihood based on the binomial coefficients


Let’s say we have a distribution \(X\) that is given by its \(s\)-quantile values:

\[q_{X_1} = Q_X(p_1),\; q_{X_2} = Q_X(p_2),\; \ldots,\; q_{X_{s-1}} = Q_X(p_{s-1}) \]

where \(Q_X\) is the quantile function of \(X\), \(p_j = j / s\).

We also have a sample \(y = \{y_1, y_2, \ldots, y_n \}\) that is given by its \(s\)-quantile estimations:

\[q_{y_1} = Q_y(p_1),\; q_{y_2} = Q_y(p_2),\; \ldots,\; q_{y_{s-1}} = Q_y(p_{s-1}), \]

where \(Q_y\) is the quantile estimation function for sample \(y\). We also assume that \(q_{y_0} = \min(y)\), \(q_{y_s} = \max(y)\).

We want to know the likelihood of “\(y\) is drawn from \(X\)”. In this post, I want to suggest a nice way to do this using the binomial coefficients.

The \(q_{X_j}\) quantile values split all the real numbers into \(s\) intervals:

\[(-\infty; q_{X_1}],\; (q_{X_1}; q_{X_2}],\; \ldots,\; (q_{X_{s-2}}; q_{X_{s-1}}],\; (q_{X_{s-1}}; \infty) \]

If we introduce \(q_{X_0} = -\infty\), \(q_{X_s}=\infty\), we can describe the \(j^\textrm{th}\) interval as \((q_{X_{j-1}}; q_{X_{j}}]\). Each of such intervals contains exactly \(1/s\) portion of the whole distribution:

\[F_X(q_{X_j}) - F_X(q_{X_{j-1}}) = 1/s, \]

where \(F_X\) is the CDF of \(X\).

If we knew the elements of sample \(y\), we would be able to match \(y_i\) to the corresponding intervals. Let’s consider another sample \(z = \{ z_1, z_2, \ldots, z_n \}\) where \(z_i\) is the index of the interval that contains \(z_i\):

\[z_i = \sum_{j=1}^{s} j \cdot \mathbf{1} \{ q_{X_{j-1}} < y_i \leq q_{X_j} \} \quad (i \in \{ 1..n\}). \]

Let \(k_j\) be the number of \(y\) elements that belong to the \(j^\textrm{th}\) segment:

\[k_j = \sum_{i=1}^n \mathbf{1} \{ z_i = j \} \quad (j \in \{ 1..s\}). \]

Unfortunately, we don’t know the exact values of \(y_i\), we know only \(s\)-quantile estimations \(q_{y_j}\). For this case, we could estimate the \(k_j\) values using linear interpolation between known quantiles:

\[k_j = n \cdot \sum_{l=1}^{s} \frac{1}{s} \frac{\max(0, \min(q_{y_l}, q_{X_j}) - \max(q_{y_{l-1}}, q_{X_{j-1}}) )}{q_{y_l} - q_{y_{l-1}}} \quad (j \in \{ 1..s\}). \]

(Here we assume that \(q_{y_l} \neq q_{y_{l-1}}\), such cases should be handled separately.)

Now we transform the original problem into the new one: what’s the likelihood of observing sample \(\{ z_i \}\) described by \(\{ k_j \}\) given that \(z_i\) is a random number from \(\{ 1, 2, \ldots, s \}\).

This is a simple combinatorial problem. The total number of different \(z\) samples is \(s^n\) (we have \(n\) elements, each element is one of \(s\) values). The number of ways to choose \(k_1\) elements that equal \(1\) is \(C_n^{k_1}\). Once we remove these elements from consideration, the number of ways to choose \(k_2\) elements that equal \(2\) is \(C_{n-k_1}^{k_2}\). If we continue this process, we will get the following equation for the likelihood:

\[\mathcal{L} = \frac{ C_n^{k_1} \cdot C_{n-k_1}^{k_2} \cdot C_{n-k_1-k_2}^{k_3} \cdot \ldots \cdot C_{n-k_1-k_2-\ldots-k_{s-1}}^{k_s}}{s^n} \]

Note that \(C_n^k\) usually assumes that \(n\) and \(k\) are integers. However, in our approach with the linear interpolation, \(k_j\) are real numbers. To work around this limitation, we could consider a generalization of \(C_n^k\) on real numbers using the gamma function \(\Gamma(n) = (n-1)!\):

\[C_n^k = \frac{n!}{k!(n-k)!} = \frac{\Gamma(n+1)}{\Gamma(k+1)\Gamma(n-k+1)} \]

In practice, it’s pretty hard to “honestly” calculate the likelihood using the above formulate so we switch to the log-likelihood notation:

\[\log\mathcal{L} = \log C_n^{k_1} + \log C_{n-k_1}^{k_2} + \log C_{n-k_1-k_2}^{k_3} + \ldots + \log C_{n-k_1-k_2-\ldots-k_{s-1}}^{k_s} - n \log s \]

It’s easy to see that \(\log C_n^k\) could be easily expressed via the log-gamma function:

\[\log C_n^k = \log \frac{\Gamma(n+1)}{\Gamma(k+1)\Gamma(n-k+1)} = \log\Gamma(n+1) - \log\Gamma(k+1) - \log\Gamma(n-k+1). \]

This log-likelihood could be used in various applications where we need a way to match sets of quantiles between each other. In one of the future posts, we will learn to apply this approach to change point detection.