---
name: adaptive-rejection-sampler
description: Guidance for implementing Adaptive Rejection Sampling (ARS) algorithms. This skill should be used when implementing rejection sampling methods, log-concave distribution samplers, or statistical sampling algorithms that require envelope construction and adaptive updates. It provides procedural approaches, performance considerations, and verification strategies specific to ARS implementations.
---

# Adaptive Rejection Sampler

## Overview

This skill provides guidance for implementing Adaptive Rejection Sampling (ARS) algorithms. ARS is a method for generating samples from log-concave probability distributions by constructing piecewise linear upper and lower envelopes of the log-density function. The skill focuses on procedural approaches, performance optimization, and verification strategies rather than providing implementation code.

## When to Use This Skill

Use this skill when:
- Implementing adaptive rejection sampling from scratch
- Working with log-concave distribution samplers
- Building statistical sampling algorithms that require envelope construction
- Debugging or optimizing existing ARS implementations
- The task involves R, Python, or other statistical computing environments

## Implementation Approach

### Phase 1: Algorithm Design Before Coding

Before writing any code:

1. **Understand the mathematical foundations**
   - Review the ARS algorithm requirements for log-concave functions
   - Understand how piecewise linear envelopes are constructed from tangent lines
   - Identify the squeeze function optimization

2. **Design with performance in mind**
   - Plan iteration limits and safeguards from the start
   - Consider worst-case computational complexity of the sampling loop
   - Design for timeout constraints that may be stricter than development testing

3. **Plan the module structure**
   - Log-concavity verification module
   - Envelope construction and update module
   - Sampling loop with rejection logic
   - Initialization point selection

### Phase 2: Critical Implementation Considerations

#### Log-Concavity Checking

When implementing log-concavity verification:

- Use appropriate tolerance values for numerical comparison
- Consider that some valid distributions have constant second derivatives (e.g., exponential distribution)
- Use `<= tolerance` instead of strict `<` comparisons when checking for non-positive second derivatives
- Test with edge cases like exponential, normal, and gamma distributions

#### Initialization Points

Proper initialization significantly affects sampling quality and performance:

- Handle shifted distributions by adjusting initialization points relative to the mode
- Consider the support bounds when selecting initial points
- Use multiple initial points to ensure good envelope coverage
- Test with distributions that have modes far from the origin

#### Iteration Limits and Safeguards

Critical for preventing infinite loops and timeouts:

- Implement maximum iteration limits in all sampling loops
- Add progress indicators or logging for long-running computations
- Include timeout protection mechanisms
- Design early exit conditions for convergence

### Phase 3: Performance-First Development

#### Timeout Considerations

- External test frameworks may use shorter timeouts than development testing
- If development tests use 180-second timeouts, production may use 60 seconds
- Profile performance early to catch issues before they become blocking
- Test with varying timeout constraints to ensure robustness

#### Computational Efficiency

- Analyze the computational complexity of the sampling loop
- Optimize envelope updates to minimize recalculation
- Consider caching frequently computed values
- Profile with realistic sample sizes

## Verification Strategies

### Unit Testing Approach

1. **Test each module independently**
   - Log-concavity checker with known log-concave and non-log-concave functions
   - Envelope construction with simple distributions
   - Sampling loop with controlled random seeds

2. **Test known distributions**
   - Standard normal distribution
   - Exponential distribution (constant second derivative edge case)
   - Truncated normal distributions
   - Gamma distributions with various parameters

3. **Test edge cases explicitly**
   - Non-function inputs
   - Negative sample counts
   - Invalid bounds (lower > upper)
   - Very small and very large sample sizes

### Performance Testing

- Match testing timeouts to expected production constraints
- Test worst-case behavior, not just average case
- Profile with different random seeds to catch stochastic failures
- Measure time per sample to identify performance degradation

### Integration Testing

- Test the complete pipeline from input to samples
- Verify statistical properties of generated samples (mean, variance, distribution shape)
- Use statistical tests (KS test, chi-square) to verify sample quality
- Test with distributions that have known analytical moments

## Common Pitfalls and Mistakes

### Critical Mistakes to Avoid

1. **Missing iteration limits**
   - Always include maximum iteration safeguards in rejection sampling loops
   - An unbounded rejection loop will cause timeouts on difficult distributions

2. **Inadequate performance testing**
   - Development tests passing does not guarantee production success
   - Test with the same timeout constraints as the target environment

3. **Tolerance issues in log-concavity checking**
   - Strict inequality checks (`< 0`) may incorrectly reject valid distributions
   - Use tolerant comparisons (`<= tolerance`) for numerical stability

4. **Poor initialization for shifted distributions**
   - Hard-coded initialization points fail for distributions with non-zero modes
   - Always compute initialization relative to the distribution's characteristics

5. **Incomplete file verification**
   - After writing large code blocks, verify the complete content was written
   - Truncated files can cause subtle bugs

### Debugging Approach

When tests fail or timeout:

1. **Systematic debugging over trial-and-error**
   - Understand root causes before implementing fixes
   - Use logging to identify where time is being spent

2. **Isolate the problematic component**
   - Test log-concavity checking separately
   - Test envelope construction separately
   - Test sampling loop with mock envelopes

3. **Check for infinite loops**
   - Add iteration counters to all loops
   - Log when iteration limits are approached
   - Verify exit conditions are reachable

## Quality Checklist

Before considering the implementation complete:

- [ ] All sampling loops have maximum iteration limits
- [ ] Log-concavity checking uses appropriate tolerances
- [ ] Initialization points adapt to distribution characteristics
- [ ] Performance tested with target timeout constraints
- [ ] Edge cases for invalid inputs are handled
- [ ] Statistical properties of samples verified
- [ ] Code verified to be completely written (no truncation)
- [ ] Tested with multiple random seeds