Ratio

Robust measure of scale ratio between two samples — the multiplicative dual of $\operatorname{Shift}$.

• Asymptotic — geometric median of pairwise ratios $\frac{x_i}{y_j}$ (via log-space aggregation)
• Domain — $x_i > 0$, $y_j > 0$
• Assumptions — positivity(x), positivity(y)
• Unit — dimensionless
• Complexity — $O((m + n) \log L)$

Properties

• Self-ratio $\operatorname{Ratio}(\mathbf{x}, \mathbf{x}) = 1$
• Scale equivariance $\operatorname{Ratio}(k_x \cdot \mathbf{x}, k_y \cdot \mathbf{y}) = (\frac{k_x}{k_y}) \cdot \operatorname{Ratio}(\mathbf{x}, \mathbf{y})$
• Multiplicative antisymmetry $\operatorname{Ratio}(\mathbf{x}, \mathbf{y}) = 1 / \operatorname{Ratio}(\mathbf{y}, \mathbf{x})$

Example

• Ratio([1, 2, 4, 8, 16], [2, 4, 8, 16, 32]) = 0.5
• Ratio(x, x) = 1 Ratio(2x, 5y) = 0.4 · Ratio(x, y)

Relationship to Shift

$\operatorname{Ratio}$ is the multiplicative analog of $\operatorname{Shift}$. While $\operatorname{Shift}$ computes the median of pairwise differences $x_i - y_j$, $\operatorname{Ratio}$ computes the median of pairwise ratios $\frac{x_i}{y_j}$ via log-transformation. This relationship is expressed formally as:

The log-transformation converts multiplicative relationships to additive ones, allowing the fast $\operatorname{Shift}$ algorithm to compute the result efficiently. The exp-transformation converts back to the ratio scale.

$\operatorname{Ratio}$ is appropriate for multiplicative relationships rather than additive differences. If one system is twice as fast or prices are 30% lower, the underlying thinking is in ratios. A result of 0.5 means the first group is typically half the size of the second; 2.0 means twice as large. This estimator is appropriate for quantities like prices, response times, and concentrations where relative comparisons make more sense than absolute ones. Both samples must contain strictly positive values.

Algorithm

The $\operatorname{Ratio}$ estimator measures the typical multiplicative relationship between elements of two samples. Given samples $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ and $\mathbf{y} = (y_1, y_2, \ldots, y_m)$ with all positive values, this estimator is defined as:

A naive approach would compute all $n \times m$ ratios, sort them, and extract the median. With $n = m = 10000$, this creates 100 million values, requiring quadratic memory and $O(n m \log(n m))$ time.

The presented algorithm avoids this cost by exploiting the multiplicative-additive duality. Taking the logarithm of a ratio yields a difference:

This transforms the problem of finding the median of pairwise ratios into finding the median of pairwise differences in log-space.

The algorithm operates in three steps:

• Log-transform — Apply $\log$ to each element of both samples. If $\mathbf{x}$ was sorted, $\log \mathbf{x}$ remains sorted (log is monotonically increasing for positive values).

• Delegate to Shift — Use the Shift algorithm to compute the desired quantile of pairwise differences in log-space. This leverages the $O((m + n) \log L)$ complexity of the Shift algorithm.

• Exp-transform — Apply $\exp$ to convert the result back to ratio-space. If the log-space median is $d$, then $\exp(d) = \exp(\log(x_i) - \log(y_j)) = \frac{x_i}{y_j}$ is the original ratio.

The total complexity is $O((m + n) \log L)$ per quantile, where $L$ represents the convergence precision in the log-space binary search. This is dramatically more efficient than the naive $O(n m \log(n m))$ approach.

Memory usage is $O(m + n)$ for storing the log-transformed samples, compared to $O(n m)$ for materializing all pairwise ratios.

namespace Pragmastat.Algorithms;

using System;
using System.Collections.Generic;
using System.Linq;
using Pragmastat.Exceptions;
using Pragmastat.Internal;

/// <summary>
/// Computes quantiles of pairwise ratios via log-transformation and FastShift delegation.
/// Ratio(x, y) = exp(Shift(log(x), log(y)))
/// </summary>
public static class FastRatio
{
  /// <summary>
  /// Computes quantiles of all pairwise ratios { x_i / y_j }.
  /// Time: O((m + n) * log(precision)) per quantile. Space: O(m + n).
  /// </summary>
  /// <remarks>
  /// Log-transformation preserves sort order for positive values.
  /// </remarks>
  /// <param name="x">First sample (must be strictly positive).</param>
  /// <param name="y">Second sample (must be strictly positive).</param>
  /// <param name="p">Probabilities in [0, 1].</param>
  /// <param name="assumeSorted">If true, assumes x and y are already sorted in ascending order.</param>
  /// <returns>Quantile values for each probability in p.</returns>
  public static double[] Estimate(IReadOnlyList<double> x, IReadOnlyList<double> y, double[] p, bool assumeSorted = false)
  {
    // Log-transform both samples (includes positivity check)
    var logX = MathExtensions.Log(x, Subject.X);
    var logY = MathExtensions.Log(y, Subject.Y);

    // Delegate to FastShift in log-space
    var logResult = FastShift.Estimate(logX, logY, p, assumeSorted);

    // Exp-transform back to ratio-space
    return logResult.Select(v => Math.Exp(v)).ToArray();
  }
}

Tests

The $\operatorname{Ratio}$ test suite contains 37 test cases (25 original + 12 unsorted), excluding zero values due to division constraints. The new definition uses geometric interpolation (via log-space), which affects expected values for even $m \times n$ cases.

Demo examples ($n = m = 5$) — from manual introduction, validating properties:

• demo-1: $\mathbf{x} = (1, 2, 4, 8, 16)$, $\mathbf{y} = (2, 4, 8, 16, 32)$, expected output: $0.5$ (base case, odd $m \times n$)
• demo-2: $\mathbf{x} = (1, 2, 4, 8, 16)$, $\mathbf{y} = (1, 2, 4, 8, 16)$, expected output: $1$ (identity property)
• demo-3: $\mathbf{x} = (2, 4, 8, 16, 32)$, $\mathbf{y} = (10, 20, 40, 80, 160)$ (= [2×demo-1.x, 5×demo-1.y]), expected output: $0.2$ (scale property)

Natural sequences ($[n, m] in {1, 2, 3} \times {1, 2, 3}$) — 9 combinations:

• natural-1-1: $\mathbf{x} = (1)$, $\mathbf{y} = (1)$, expected output: $1$
• natural-1-2: $\mathbf{x} = (1)$, $\mathbf{y} = (1, 2)$, expected output: $\approx 0.707$ ($= \sqrt{0.5}$, geometric interpolation)
• natural-1-3: $\mathbf{x} = (1)$, $\mathbf{y} = (1, 2, 3)$, expected output: $0.5$
• natural-2-1: $\mathbf{x} = (1, 2)$, $\mathbf{y} = (1)$, expected output: $\approx 1.414$ ($= \sqrt{2}$, geometric interpolation)
• natural-2-2: $\mathbf{x} = (1, 2)$, $\mathbf{y} = (1, 2)$, expected output: $1$
• natural-2-3: $\mathbf{x} = (1, 2)$, $\mathbf{y} = (1, 2, 3)$, expected output: $\approx 0.816$ (geometric interpolation)
• natural-3-1: $\mathbf{x} = (1, 2, 3)$, $\mathbf{y} = (1)$, expected output: $2$
• natural-3-2: $\mathbf{x} = (1, 2, 3)$, $\mathbf{y} = (1, 2)$, expected output: $\approx 1.225$ (geometric interpolation)
• natural-3-3: $\mathbf{x} = (1, 2, 3)$, $\mathbf{y} = (1, 2, 3)$, expected output: $1$

Additive distribution ($[n, m] in {5, 10, 30} \times {5, 10, 30}$) — 9 combinations with $\underline{\operatorname{Additive}}(10, 1)$:

• additive-5-5, additive-5-10, additive-5-30
• additive-10-5, additive-10-10, additive-10-30
• additive-30-5, additive-30-10, additive-30-30
• Random generation: $\mathbf{x}$ uses seed 0, $\mathbf{y}$ uses seed 1

Uniform distribution ($[n, m] in {5, 100} \times {5, 100}$) — 4 combinations with $\underline{\operatorname{Uniform}}(0, 1)$:

• uniform-5-5, uniform-5-100, uniform-100-5, uniform-100-100
• Random generation: $\mathbf{x}$ uses seed 2, $\mathbf{y}$ uses seed 3
• Note: all generated values are strictly positive (no zeros); values near zero test numerical stability of log-transformation

The natural sequences verify the identity property ($\operatorname{Ratio}(\mathbf{x}, \mathbf{x}) = 1$) and validate ratio calculations with simple integer inputs. Note that implementations should handle the practical constraint of avoiding division by values near zero.

Unsorted tests — verify independent sorting for ratio calculation (12 tests):

• unsorted-x-natural-{n}-{m} for $(n,m) in {(3,3), (4,4)}$: X unsorted (reversed), Y sorted (2 tests)
• unsorted-y-natural-{n}-{m} for $(n,m) in {(3,3), (4,4)}$: X sorted, Y unsorted (reversed) (2 tests)
• unsorted-both-natural-{n}-{m} for $(n,m) in {(3,3), (4,4)}$: both unsorted (reversed) (2 tests)
• unsorted-demo-unsorted-x: $\mathbf{x} = (16, 1, 8, 2, 4)$, $\mathbf{y} = (2, 4, 8, 16, 32)$ (demo-1 with X unsorted)
• unsorted-demo-unsorted-y: $\mathbf{x} = (1, 2, 4, 8, 16)$, $\mathbf{y} = (32, 2, 16, 4, 8)$ (demo-1 with Y unsorted)
• unsorted-demo-both-unsorted: $\mathbf{x} = (8, 1, 16, 4, 2)$, $\mathbf{y} = (16, 32, 2, 8, 4)$ (demo-1 both unsorted)
• unsorted-identity-unsorted: $\mathbf{x} = (4, 1, 8, 2, 16)$, $\mathbf{y} = (16, 1, 8, 4, 2)$ (identity property, both unsorted)
• unsorted-asymmetric-unsorted-2-3: $\mathbf{x} = (2, 1)$, $\mathbf{y} = (3, 1, 2)$ (asymmetric, both unsorted)
• unsorted-power-unsorted-5: $\mathbf{x} = (16, 2, 8, 1, 4)$, $\mathbf{y} = (32, 4, 16, 2, 8)$ (powers of 2 unsorted)