Random number with Probabilities

Learn random number with probabilities with practical examples, diagrams, and best practices. Covers java, random, probability development techniques with visual explanations.
Tags:
Categories:

Generating Random Numbers with Custom Probabilities in Java

Hero image for Random number with Probabilities

Learn how to implement various techniques in Java to generate random numbers or select items from a list, where each outcome has a predefined probability of being chosen.

Generating random numbers is a fundamental task in many programming scenarios, from simulations and games to data sampling and statistical analysis. While Java's java.util.Random class provides excellent tools for uniform random distribution, real-world applications often require outcomes to be weighted by specific probabilities. This article explores several robust methods to achieve weighted random selection in Java, ensuring that certain outcomes are more likely to occur than others.

Understanding Weighted Random Selection

Weighted random selection means that instead of each item having an equal chance of being chosen, some items are assigned a higher 'weight' or 'probability' than others. For example, if you have three items A, B, and C with probabilities 20%, 30%, and 50% respectively, item C should be selected roughly half the time, while A is selected only 20% of the time. This is crucial for simulating realistic scenarios where events are not equally likely.

flowchart TD
    A[Start]
    B{Define Items and Probabilities}
    C[Calculate Cumulative Probabilities]
    D[Generate Random Number (0.0 to 1.0)]
    E{Find Item in Cumulative Range}
    F[Return Selected Item]

    A --> B
    B --> C
    C --> D
    D --> E
    E --> F

General workflow for weighted random selection.

Method 1: Cumulative Probability Distribution

One of the most common and intuitive ways to implement weighted random selection is using a cumulative probability distribution. This method involves assigning a range on a number line (typically from 0 to 1) to each item, where the size of the range corresponds to its probability. A random number is then generated within this total range, and the item whose range contains that random number is selected.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class WeightedRandomSelector {

    private static class Item {
        String name;
        double weight;

        public Item(String name, double weight) {
            this.name = name;
            this.weight = weight;
        }
    }

    public static String selectRandomItem(List<Item> items) {
        double totalWeight = 0;
        for (Item item : items) {
            totalWeight += item.weight;
        }

        // Calculate cumulative weights
        List<Double> cumulativeWeights = new ArrayList<>();
        double currentCumulativeWeight = 0;
        for (Item item : items) {
            currentCumulativeWeight += item.weight;
            cumulativeWeights.add(currentCumulativeWeight);
        }

        Random random = new Random();
        double randomNumber = random.nextDouble() * totalWeight; // Scale random number to total weight

        // Find the item corresponding to the random number
        for (int i = 0; i < items.size(); i++) {
            if (randomNumber < cumulativeWeights.get(i)) {
                return items.get(i).name;
            }
        }
        return null; // Should not happen if totalWeight > 0
    }

    public static void main(String[] args) {
        List<Item> items = new ArrayList<>();
        items.add(new Item("Gold Coin", 0.1)); // 10% chance
        items.add(new Item("Silver Coin", 0.3)); // 30% chance
        items.add(new Item("Bronze Coin", 0.6)); // 60% chance

        System.out.println("Simulating 10 selections:");
        for (int i = 0; i < 10; i++) {
            System.out.println("Selected: " + selectRandomItem(items));
        }
    }
}

Java implementation of weighted random selection using cumulative probabilities.

Method 2: Using a TreeMap for Efficient Lookup

For scenarios where you might have a large number of items or need to frequently update probabilities, using a TreeMap can offer more efficient lookup than iterating through a list. The TreeMap can store cumulative probabilities as keys and the corresponding items as values. Its higherEntry() or ceilingEntry() methods can then quickly find the correct item.

import java.util.List;
import java.util.Random;
import java.util.TreeMap;
import java.util.ArrayList;

public class WeightedRandomTreeMapSelector<T> {

    private final TreeMap<Double, T> map = new TreeMap<>();
    private double totalWeight = 0;
    private final Random random = new Random();

    public void add(T item, double weight) {
        if (weight <= 0) {
            throw new IllegalArgumentException("Weight must be positive");
        }
        totalWeight += weight;
        map.put(totalWeight, item); // Store cumulative weight
    }

    public T next() {
        double value = random.nextDouble() * totalWeight;
        // ceilingEntry returns an entry associated with the least key greater than or equal to the given key
        return map.ceilingEntry(value).getValue();
    }

    public static void main(String[] args) {
        WeightedRandomTreeMapSelector<String> selector = new WeightedRandomTreeMapSelector<>();
        selector.add("Rare Item", 0.05); // 5% chance
        selector.add("Uncommon Item", 0.25); // 25% chance
        selector.add("Common Item", 0.70); // 70% chance

        System.out.println("Simulating 10 selections with TreeMap:");
        for (int i = 0; i < 10; i++) {
            System.out.println("Selected: " + selector.next());
        }
    }
}

Weighted random selection using a TreeMap for efficient item lookup.