If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

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.
Nature of Code Image
Figure I.4
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):
  1. Pick a random number: R1
  2. Compute a probability P that R1 should qualify. Let’s try: P = R1.
  3. Pick another random number: R2
  4. If R2 is less than P, then we have found our number—R1!
  5. 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?

  • spunky sam red style avatar for user WhyNotLearn
    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!
    (29 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Taylor Poydence
      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).
      (25 votes)
  • leafers ultimate style avatar for user Danielle Cerrato
    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?
    (17 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user jamesrains78
    I dont understand the while(true)......it loops whilst what is true? Or how would I change true to false?
    (13 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user daniel.bryce.hall
      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;
      }
      }
      (7 votes)
  • duskpin ultimate style avatar for user Xernical
    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)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Dean Smith
      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)
  • blobby green style avatar for user Ritesh Pillai
    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)
    Default Khan Academy avatar avatar for user
    • duskpin ultimate style avatar for user Chmos
      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)
  • winston baby style avatar for user ♚| 𝕮𝖆𝖑𝖊𝖇 |♚
    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;}
    (5 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Arun Jayaraman
    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)
    Default Khan Academy avatar avatar for user
  • aqualine seed style avatar for user Abhitya
    i am not getting how to do challenge levy walker step 2.
    could any one plz help me
    (4 votes)
    Default Khan Academy avatar avatar for user
  • starky seed style avatar for user a
    I don't get the part 2 of Challenge: Levy Walker. The hint says to change something in the monteCarlo function, but I changed almost everything and I still didn't pass the part 2. Can someone help?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • purple pi teal style avatar for user Aahan Sarin
    can you help in the second step of previous challenge
    (3 votes)
    Default Khan Academy avatar avatar for user