Distribution Search

Distribution Search

Overview

This skill provides structured guidance for finding probability distributions that satisfy specific statistical constraints. These problems typically involve constructing a discrete probability distribution over a large vocabulary that achieves target values for metrics like KL divergence, entropy, or other information-theoretic quantities.

Mathematical Analysis First

Before writing any code, perform thorough mathematical analysis to constrain the solution space:

1. Derive analytical relationships between the target metrics and distribution properties

   • For KL divergence from uniform: KL(P||U) = -H(P) + log(V) where H(P) is entropy and V is vocabulary size
   • For KL divergence to uniform: KL(U||P) = log(V) - (1/V) * Σ log(P(i))

2. Calculate fixed quantities from the problem specification

   • Vocabulary size V determines log(V)
   • Target values combined with log(V) constrain feasible entropy ranges

3. Identify implied constraints from simultaneous requirements

   • Multiple target metrics often severely restrict the feasible solution space
   • Determine if the problem is over-constrained before attempting optimization

4. Estimate the solution structure analytically

   • Determine the approximate entropy the distribution must have
   • Estimate how concentrated or spread the probability mass should be

Parameterization Strategy

High-dimensional optimization over all probability values is impractical. Use reduced parameterizations:

Recommended Parameterizations

1. Power law with uniform tail: k high-probability elements following p_i ∝ i^(-α), remaining elements share probability equally

   • Parameters: k (number of special elements), α (power law exponent), p_rest (probability for tail)

2. Two-group distribution: k elements with probability p_high, remaining elements with probability p_low

   • Parameters: k, p_high (p_low is determined by normalization)

3. Multi-tier distribution: Several groups of elements with distinct probability levels

   • Parameters: group sizes and probability levels

Parameter Selection Guidance

• Start with few parameters (2-3) and add flexibility only if needed
• Derive parameter bounds from mathematical constraints rather than arbitrary choices
• Calculate reasonable initial values from the analytical solution estimates

Implementation Approach

Modular Code Structure

Organize code into separate, tested functions:

- kl_forward(P, V): Compute KL(P||Uniform)
- kl_backward(P, V): Compute KL(Uniform||P)
- create_distribution(params, V): Generate distribution from parameterization
- objective(params): Optimization objective combining constraints
- verify_solution(P, V, targets): Independent verification

Computational Efficiency

• Avoid full array operations when possible - use analytical formulas for symmetric distributions
• For two-group distributions: compute entropy/KL directly from group sizes and probabilities
• Estimate computational cost before running - set appropriate timeouts

Optimization Strategy

1. Coarse grid search over reduced parameter space to find promising regions
2. Local optimization from multiple starting points in promising regions
3. Refinement with tighter tolerances near solutions

Verification

Independent Verification

Always verify solutions with code independent from the optimization:

1. Check probability constraints: All values non-negative, sum to 1.0
2. Compute metrics directly: Use explicit formulas, not the optimization objective
3. Test against known cases: Verify computation on uniform distribution or other known solutions

Common Verification Bugs

• Incorrect handling of log(0) - use appropriate thresholds (e.g., max(p, 1e-30))
• Array indexing errors when elements are counted vs indexed
• Forgetting to normalize after parameter adjustments
• Multiplication errors when computing sums over groups

Common Pitfalls

Computational

• Starting with full-dimensional optimization: Immediately recognize the need for reduced parameterization
• Insufficient timeout estimation: Estimate iterations needed before running
• Rewriting entire scripts: Use modular code to enable targeted fixes

Mathematical

• Incomplete constraint analysis: Fully leverage mathematical relationships before coding
• Arbitrary parameter bounds: Derive bounds from problem constraints
• Poor initial values: Use analytical estimates for starting points

Verification

• Trusting optimization output directly: Always verify with independent computation
• Not testing verification code: Verify the verifier using known solutions first
• Numerical precision issues: Handle small probabilities carefully

Problem-Solving Workflow

1. Analyze: Derive analytical relationships and estimate solution structure
2. Parameterize: Choose reduced parameterization matching expected structure
3. Implement: Write modular, tested code for each component
4. Search: Grid search followed by local optimization
5. Verify: Independent verification of candidate solutions
6. Refine: Adjust parameterization if tolerances not achieved

When Solutions Are Not Found

If optimization fails to find valid solutions:

1. Check if the problem is mathematically feasible given constraints
2. Verify the parameterization can represent valid solutions
3. Expand the parameterization to add flexibility
4. Check for bugs in objective function or constraint handling
5. Try different optimization algorithms or starting points