Overview
Multinomial sampling generalizes categorical sampling to multiple draws, producing category counts that follow specified probabilities.
CoreSource checked
Multinomial Sampling
Draws counts or categories according to a discrete probability vector.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Intermediate
- Family
- Discrete Sampling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
categorical probabilitycount vectordiscrete distributionrandom draw
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k)
Average
O(draws * k)
Worst
O(draws * k)
Space
O(k)
When to Use
- Use when monte Carlo simulation needs categorical probability.
- Use when the input matches the assumptions behind discrete Sampling.
When Not to Use
- Avoid when independence, reproducibility, or distribution quality cannot be checked.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Draws counts or categories according to a discrete probability vector
- Uses categorical probability and count vector to guide the work.
- Produces samples.
Use Cases
- Monte Carlo simulation
- Randomized algorithms
- Sampling distributions
Inputs
- Random source
- Distribution or weights
- Sample count
Outputs
- Samples
- Estimated statistic
- Randomized selection
Key Formulas (1)
Multinomial probability
P(counts) = n! / product ci! · product pici
P(counts) = n! / product c_i! * product p_i^c_iGives the probability of observing a count vector after n draws.
Pseudocode
- 1.Prepare the inputs and state needed for Multinomial Sampling.
- 2.Apply the categorical probability step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return samples.
Canonical Example
- Input
- Multinomial Sampling input with a small representative case
- Output
- Samples
- Explanation
- Multinomial Sampling applies categorical probability to produce samples.
Implementation Notes
- Expose seed handling when reproducibility is important.
- Keep the categorical probability step separate enough to test independently.
Common Pitfalls
- Using a biased random source can quietly invalidate downstream estimates.
- Forgetting to check edge cases can make Multinomial Sampling look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryPlot generated samples against the target distribution or domain.
Step 1 of 4: Prepare the inputs and state needed for Multinomial Sampling.
randomness-sampling-mechanismNotes
Multinomial Sampling should be used with the assumptions and tradeoffs of discrete Sampling in mind.
Sources (1)
What each reference supports for this entry.
Non-Uniform Random Variate Generation
BookRandom variate generation reference for Multinomial Sampling sampling from categorical and multinomial distributions.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageGeneralizesAlias Method
Alias sampling is one efficient way to draw repeated multinomial outcomes.
Related Algorithms
Tags
Randomness & SamplingWeighted SamplingProbabilitySampling