Random ints with different likelihoods

Question

I was wondering if there was a way to have a random number between A an b and where if a number meets a certain requirement it is more likely to appear than all the other numbers between A and B, for example: Lower numbers are more likely to appear so if A = 1 and B = 10 then 1 would be the likeliest and 10 would be the unlikeliest.

All help is appreciated :) (sorry for bad English/grammar/question)

Answer 1

C++11 (which you should absolutely be using by now) added the <random> header to the C++ standard library. This header provides much higher quality random number generators to C++. Using srand() and rand() has never been a very good idea because there's no guarantee of quality, but now it's truly inexcusable.

In your example, it sounds like you want what would probably be called a 'discrete triangular distribution': the probability mass function looks like a triangle. The easiest (but perhaps not the most efficient) way to implement this in C++ would be the discrete distribution included in <random>:

auto discrete_triangular_distribution(int max) {
    std::vector<int> weights(max);
    std::iota(weights.begin(), weights.end(), 0);
    std::discrete_distribution<> dist(weights.begin(), weights.end());
    return dist;
}

int main() {
    std::random_device rd;
    std::mt19937 gen(rd());
    auto&& dist = discrete_triangular_distribution(10);
    std::map<int, int> counts;
    for (int i = 0; i < 10000; i++)
        ++counts[dist(gen)];
    for (auto count: counts)
        std::cout << count.first << " generated ";
        std::cout << count.second << " times.\n";
}

which for me gives the following output:

1 generated 233 times.
2 generated 425 times.
3 generated 677 times.
4 generated 854 times.
5 generated 1130 times.
6 generated 1334 times.
7 generated 1565 times.
8 generated 1804 times.
9 generated 1978 times.

Things more complex than this would be better served with either using one of the existing distributions (I have been told that all commonly used statistical distributions are included) or by writing your own distribution, which isn't too hard: it just has to be an object with a function call operator that takes a random bit generator and uses those bits to produce (in this case) random numbers. But you could create one that made random strings, or any arbitrary random objects, perhaps for testing purposes).

Answer 2

Your question doesn't specify which distribution to use. One option (of many) is to use the (negative) exponential distribution. This distribution is parameterized by a parameter λ. For each value of λ, the maximum result is unbounded (which needs to be handled in order to return results only in the range specified)

(from Wikipedia, By Skbkekas, CC BY 3.0)

so any λ could theoretically work; however, the properties of the CDF

(from Wikipedia, By Skbkekas, CC BY 3.0)

imply that it pays to choose something in the order of 1 / (to - from + 1).

The following class works like a standard library distribution. Internally, it generates numbers in a loop, until a result in [from, to] is obtained.

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>

class bounded_discrete_exponential_dist {
public: 
    explicit bounded_discrete_exponential_dist(std::size_t from, std::size_t to) : 
        m_from{from}, m_to{to}, m_d{0.5 / (to - from + 1)} {}
    explicit bounded_discrete_exponential_dist(std::size_t from, std::size_t to, double factor) : 
        m_from{from}, m_to{to}, m_d{factor} {}

    template<class Gen>
    std::size_t operator()(Gen &gen) {
        while(true) {
            const auto r = m_from + static_cast<std::size_t>(m_d(gen));
            if(r <= m_to)   
                return r;
        }
    }

private:
    std::size_t m_from, m_to;
    std::exponential_distribution<> m_d;
};

Here is an example of using it:

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());

    bounded_discrete_exponential_dist d{1, 10};

    std::vector<std::size_t> hist(10, 0);
    for(std::size_t i = 0; i < 99999; ++i)
        ++hist[d(gen) - 1];

    for(auto h: hist)
        std::cout << std::string(static_cast<std::size_t>(80 * h / 99999.), '+') << std::endl;
}

When run, it outputs a histogram like this:

$ ./a.out
++++++++++
+++++++++
+++++++++
++++++++
+++++++
+++++++
+++++++
+++++++
++++++
++++++