Convert uniform random generation to binomial

Question

I have written the following function to implement a type of mutation(creep) in my genetic algorithm project. Since I've used java's inbuilt random generation library, the probability of getting every index is uniform. I've been asked to modify the function such way that it uses binomial distribution instead of uniform. As far as I googled, I couldn't find any example/tutorial that demonstrates conversion of uniform to binomial. How do I achieve it?

int mutationRate = 0.001;
public void mutate_creep() {
    if (random.nextDouble() <= mutationRate) {

        // uniform random generation
        int index = random.nextInt(chromoLen); 

        if(index%2 == 0) { // even index
            chromo[index] += 1;
        } else { // odd index
            chromo[index] -= 1;
        }
    }
}

NOTE: I have already seen the solution at A efficient binomial random number generator code in Java. Since my problem here is specific to creep mutation algorithm, I'm not sure how it can be applied directly.

Possible duplicate of [A efficient binomial random number generator code in Java](http://stackoverflow.com/questions/23561551/a-efficient-binomial-random-number-generator-code-in-java) — pjs, Aug 14 '16 at 16:55
@pjs I understand that you've answered the duplicate marked question. FYI, I've seen it already and I cannot use it in my situation directly as I need it specifically for `creep mutation algorithm`. So please unmark the duplication flag and answer my problem here if u can. — DhiwaTdG, Aug 14 '16 at 17:02
A binomial is a binomial, and the linked answer tells you how to get those. As currently worded, your question *is* a duplicate. Sounds like your problem is not how to generate a binomial, but rather how to use it in your creep algorithm. — pjs, Aug 14 '16 at 17:09
Is your intention to flip the bit at a specified index? If so, your logic is off. Suppose you select index 4 and the value of chromo[4] is currently 1, you'll update it to 2. If your goal is to flip the bit, use `chromo[index] ^= 1;` regardless of even/odd index. — pjs, Aug 14 '16 at 17:40
@pjs I'm implementing the function for my project and I had taken the reference from http://www.ijcsit.com/docs/Volume%205/vol5issue03/ijcsit20140503404.pdf, `section IV. Types of mutations - creep mutation`. As per the explanation I choose a random index and change its value between my lower and upper bound. For simplicity I've coded +/- 1 here but I've actually used another function call which returns a value between the bounds & then I add or subtract its value depending on whether the index is odd/even. — DhiwaTdG, Aug 14 '16 at 17:47
I still don't think you've clarified your question sufficiently to get meaningful answers. The binomial distribution is a counting distribution, it describes the number of "successes" you observe when `n` independent trials are performed, each of which has probability `p` of success. How do you plan to use that count? — pjs, Aug 14 '16 at 20:12

score 1 · Answer 1 · edited May 23 '17 at 12:33

According to Wikipedia, you do this:

One way to generate random samples from a binomial distribution is to use an inversion algorithm. To do so, one must calculate the probability that P(X=k) for all values k from 0 through n. (These probabilities should sum to a value close to one, in order to encompass the entire sample space.) Then by using a pseudorandom number generator to generate samples uniformly between 0 and 1, one can transform the calculated samples U[0,1] into discrete numbers by using the probabilities calculated in step one.

I will leave it to you to "calculate the probability [...] for all values k from 0 through n". After that, it's a weighed distribution.

You can do that using a TreeMap, similar to how I show it in this answer.

Convert uniform random generation to binomial

1 Answers1