Main content

## Computer programming

### Course: Computer programming > Unit 5

Lesson 2: Randomness# Custom distribution of random numbers

There will come a time in your life when you do not want a uniform distribution of random values, or a Gaussian one. Let’s imagine for a moment that you are a random walker in search of food. Moving randomly around a space seems like a reasonable strategy for finding something to eat. After all, you don’t know where the food is, so you might as well search randomly until you find it. The problem, as you may have noticed, is that random walkers return to previously visited locations many times (this is known as “oversampling”). One strategy to avoid such a problem is to, every so often, take a very large step. This allows the walker to forage randomly around a specific location while periodically jumping very far away to reduce the amount of oversampling. This variation on the random walk (known as a Lévy flight) requires a custom set of probabilities. Though not an exact implementation of a Lévy flight, we could state the probability distribution as follows: the longer the step, the less likely it is to be picked; the shorter the step, the more likely.

Earlier in this section, we saw that we could generate custom probability distributions by filling an array with values (some duplicated so that they would be picked more frequently) or by testing the result of

`random()`

. We could implement a Lévy flight by saying that there is a 1% chance of the walker taking a large step.```
var r = random(1);
// A 1% chance of taking a large step
if (r < 0.01) {
xstep = random(-100, 100);
ystep = random(-100, 100);
} else {
xstep = random(-1, 1);
ystep = random(-1, 1);
}
```

However, this reduces the probabilities to a fixed number of options. What if we wanted to make a more general rule—the higher a number, the more likely it is to be picked? 3.145 would be more likely to be picked than 3.144, even if that likelihood is just a tiny bit greater. In other words, if

`x`

is the random number, we could map the likelihood on the y-axis with `y`

= `x`

.If we can figure out how to generate a distribution of random numbers according to the above graph, then we will be able to apply the same methodology to any curve for which we have a formula.

One solution is to pick two random numbers instead of one. The first random number is just that, a random number. The second one, however, is what we’ll call a “qualifying random value.” It will tell us whether to use the first one or throw it away and pick another one. Numbers that have an easier time qualifying will be picked more often, and numbers that rarely qualify will be picked infrequently. Here are the steps (for now, let’s consider only random values between 0 and 1):

- Pick a random number: R1
- Compute a probability P that R1 should qualify. Let’s try: P = R1.
- Pick another random number: R2
- If R2 is less than P, then we have found our number—R1!
- If R2 is not less than P, go back to step 1 and start over.

Here we are saying that the likelihood that a random value will qualify is equal to the random number itself. Let’s say we pick 0.1 for R1. This means that R1 will have a 10% chance of qualifying. If we pick 0.83 for R1 then it will have a 83% chance of qualifying. The higher the number, the greater the likelihood that we will actually use it.

Here is a function (named after the Monte Carlo method, which itself was named after the Monte Carlo casino) that implements the above algorithm, returning a random value between 0 and 1. This program uses the values to size ellipses , but we could use those values for many things.

This "Natural Simulations" course is a derivative of "The Nature of Code" by Daniel Shiffman, used under a Creative Commons Attribution-NonCommercial 3.0 Unported License.

## Want to join the conversation?

- On the next challenge I'm completely lost. The article didn't help me and I'm stuck on step 1 with no clue what to do. Can someone explain to me with the Lévy Walker is? On the challenge I have only added stepSize = monteCarlo. Please help!(26 votes)
- The Monte Carlo function generates two numbers and if the second is
*less*than the first, then it passes the first value through. A Lévy Walker function wants to do the opposite, passing the first number through if the second is*greater*than it. Check the code and see where there is a line that you can make that change easily (only need to change one character).(21 votes)

- I don't understand why we need the P = R1 step.

Aren't we just comparing R2 to the same exact value either way? I don't see the probability variable used anywhere else in the code either, so it doesn't seem that removing it would make any difference.

so we could just say:

while (true) {

var r1 = random(1);

var r2 = random(1);

if (r2 < r1) {

return r1;

}

};

I've been peering through the last few paragraphs for like ten minutes and can't help feeling I am completely missing something…? Is this one of those things that makes no sense in a simplistic program but makes a huge difference in complex programs?(15 votes)- I think the author is just trying to make it clear what the variable
`r1`

represents. You are right, though, it would be more efficient to simply do`var probability = random(1);`

(14 votes)

- I dont understand the while(true)......it loops whilst what is true? Or how would I change true to false?(11 votes)
- The while loop below repeats until the if block with the return statement is executed. This allows the loop to keep going until the threshold for r1 is met (it is larger than r2).

while (true) {

// Pick a random value.

var r1 = random(1);

// Assign a probability.

var probability = r1;

// Pick a second random value.

var r2 = random(1);

// Does it qualify? If so, we’re done!

if (r2 < probability) {

return r1;

}

}(4 votes)

- I don't understand what it wants me to do on the second step in the Lévy Walker challenge. I've tried changing the R1 and R2, and I know that changing R1 ' s random parameters will either increase or decrease its chance of 'qualifying'.

Any help would be much appreciated, thanks!(5 votes)- Serious, sometimes there are multiple ways of solving the problem, but only one chang of code is selected as the right solution. I just flipped the inequality sign: r2 > probability

that seemed to have solved the problem with regards to the preference of choosing small generated numbers.(9 votes)

- Im not really understanding what is happening here. How is implementing a Lévy flight by saying that there is a 1% chance of the walker taking a large step different than saying the higher a number, the more likely it is to be picked? ... does it really matter if the first option reduces the probabilities to a fixed number of options? if yes then why does it matter?(8 votes)
- I'm struggling a bit my self, but I think I understand what you're asking and the answer.

Using a Monte Carlo, higher numbers are more probable. That means, if the step size is a random number, longer steps will be more probable because higher numbers = longer steps. If you invert this number, longer steps are less probable. I hope I answered your question.(5 votes)

- I don't understand in Levy Walker, how to make a stepsize equal to a number of the montecarlo function. What do you make stepsize equal to?(2 votes)
- This is the aswer I hopre that is healpful and sorry for the two year wait

var stepSize = random(monteCarlo(), monteCarlo()*10);(5 votes)

- Why do you even have to assign a probability variable to the value of
`r1`

? Just compare`r1`

to`r2`

directly.

I think this line is useless:`var probability = r1;`

You can skip it entirely and replace all instances of`probability`

with`r1`

, and it does the same thing:`if(r2 < r1) {return r1;}`

(3 votes)- The authors of the program might not have thought about that, or perhaps they wanted to be more clear. Code is an art as much as a science.(4 votes)

- i am not getting how to do challenge levy walker step 2.

could any one plz help me(4 votes)- Change the monteCarlo function so that the probability is higher for lower numbers instead.
`if (r2 > probability) {`

return r1;

}(3 votes)

- I'm stuck on step 2 of the Levy walker. I don't really understand what it's asking me to do.(2 votes)
- what is the value of monteCarlo() ?(3 votes)