Pseudo-random number generator with dependent probability of outputting desired numbers?

Question

Programming

There is a task:
Based on some ready-made tools or functions (for example, rand), you need to make a function that will return pseudo-random numbers for a given range (or a ready-made set of some numbers), and not uniformly, but according to some given dependence . The following dependency can be taken as a basic one: return large values ​​more often. This raises a reasonable question, how often. Here, any given option is also offered, for example, as many times more often as the ordinal number of the given element in the array is greater.
Example:
Array m = [1, 3, 7, 19]. We call our getMyRand() function passing it an array (or a range if there is no array). As a result, we get some values ​​like this (the number of the function call is the returned value):
1 - 19
2 - 7
3 - 19
4 - 19
5 - 3
6 - 19
7 - 7
8 - 1
9 - 19
10 - 7
11 - 19
12 - 7
13 - 3
14 - 19
15 - 19
etc.
If you have any thoughts on how to approach such a function, I would like to hear and discuss.
What might be interesting about her? For example, write a bot that will visit sites and simulate page views close to human behavior.

Answer 1

Elementary Watson, you need a function that will give random numbers with a given distribution.
For example:

return larger values ​​more often

is an exponential or exponential function. I somehow dealt with this issue. You need to do the inverse transformation of the distribution function and just substitute your values ​​there and have the output with the desired distribution.

Answer 2

Wrote a quick test script in PHP:

<?php
$m = [];
for ($i = 0; $i < 1000; $i++)
{
  $rnd = (int) (10 * log(rand(3, 50)));
  $m[$rnd] = isset($m[$rnd]) ? $m[$rnd] + 1 : 0;
}
ksort($m);
foreach ($m as $i => $cnt)
    echo "<div style='margin: 2px; color: #fff; padding: 3px; background: #696; width: ".($cnt * 10)."px;'>$i</div>\n";
?>

Answer 3

I once made a psch generator with an arbitrary distribution through a hash function. The algorithm is frontal, it does not pretend to mathematical and technical beauty, but anyway I will describe it, suddenly it will come in handy for someone.
- We need a psch generator, say from 0 to 99 with a variable probability of dropping numbers.
- We start an array of 10,000 elements. We put all the numbers in the array 100 times.
- Choosing from the array a number with a random (through the usual gpsch) index from 0 to 9999, we will get a number from 0 to 99 with equal probability.
- To reduce the probability of a number falling out, you need to reduce the number of these numbers in the array. For example, if the number "8" is included in the array not 100, but 50 times, then its probability of falling out will be half that of the others.
- To increase the probability of a number falling out, we expand the array and add more such numbers.
Thus, it is possible to build almost any distribution function (of course, with restrictions on the probability coefficients of numbers falling out). The smoothness of the tuning of such a generator directly depends on the size of the array.

Answer 4

For a variant of a finite discrete sequence (as in your case), the problem is solved quite simply by a variation of the Monte Carlo method.
Suppose we have an array A of natural numbers from 0 to n (0, 1, ..., n - 1) and for each of these numbers the probability of its generation p (a_i) is set (naturally, the sum of all probabilities is 1). The idea of ​​the method is to divide the segment [0;1) into n segments, the length of each of which is equal to the probability of the corresponding number from the array A. Next, we select a number in the range [0;1) with the standard PRNG generator and check which of the segments it falls into . We return the element of the original array corresponding to this segment as the result of our generator.
We will leave the implementation of the algorithm to the reader as homework :)

Answer 5

My stupid, but working solution is described here habrahabr.ru/post/194598/ - I used the modified version in the last project. Generates everything according to my rules, quickly and clearly.

Answer 6

moved to QA - habrahabr.ru/qa/47196/