Search code examples
crandomprobability

How to select value from different ranges with equal probability

Provided different ranges, select each value with equal probability. Like say var 'a' can have values among { [10,20],40,[70,100]...} (given) . Each selected value by provided constraints should have same probability. How to get a random value in C?

Solution

  • Giving each Range equal probabilistic chance:

    1. Let N be the number of ranges you've defined in your problem-set. Ranges { R0, R1, R2 ... RN-1 }, Indexes start at 0.
    2. Generate a random number, RandValue mod N to pick a range. In C, modulo operator is %, gives you integral remainder.
    3. Is picked range just a number? (like 40 in your example)
      • 3.1 Yes, then your random value is that number
      • 3.2 No, it's a range. Find a random value within selected range.

    Giving each value in all ranges equal probabilistic chance:

    1. Let N be the number of values across all ranges.
    2. Map each value to an index, Values { V0, V1, V2 ... VN-1 }, Indexes start at 0.
    3. Use hash-tables for quick lookups. Also, you can handle overlapping ranges.
    4. Generate a random number, RandValue mod N to pick a value-index.
    5. Look up in hash-table for mapped value against the index.

    Also, note that hash-table could become huge if the ranges are too large. In that case you may have to merge overlapping/consecutive (if any) ranges and maintain sorted(by value-index) list(array of structs) of ranges and assign index-ranges. Use binary search to find the range against random-index. Range offsets (start/end values & indexes) should give the final value for a given random-index.

    PS: This is for trivial implementations of randomness in C projects. I believe all randomness is deterministic.

    Edit: I agree, there is modulo-bias & to reject values beyond (RAND_MAX - RAND_MAX % N).