Coding Help

I used to make my own random number generators for various distributions by employing a uniform random number generator.

The basic idea is to generage a random number within the range of the distribution you are using. Then use this random number to calculate the height of the probability density function at that number.

To decide whether or not to keep this first generated random number, generate a second random number normalized to the maximum height of the probability density function.

If the second random number falls below the probability calculated using the first random number, keep the first random number. Otherwise, throw everything away and begin again.

Thus, the probability of keeping the first random number is the same as the probability that the second random number falls below the corresponting probability density function.

A quick google turned up this page:

http://www.ciphersbyritter.com/JAVASCRP/BINOMPOI.HTM#Binomial

Does it do what you want?

Regards,

Derek Tattersall

Derek Tattersall said: A quick google turned up this page: http://www.ciphersbyritter.com/JAVASCRP/BINOMPOI.HTM#Binomial Does it do what you want?

Mike Elzinga said: Thus, the probability of keeping the first random number is the same as the probability that the second random number falls below the corresponting probability density function.

Reed A. Cartwright said:

Mike Elzinga said: Thus, the probability of keeping the first random number is the same as the probability that the second random number falls below the corresponting probability density function.

I'm not asking how to generate a binomial random variable, I'm familiar with the algorithms and the theory. I just want one in javascript format that I don't have to port myself. The temporary one that I'm using builds the binomial from a sum of Bernoulli trials, but that's inefficient when population sizes get large.

Reed,

From what I can understand from your request and replies, I get the impression that you are having the same problem that I often had.

I could write a short program or function faster than I could find one. I needed to sample from various kinds of distributions.

The method I mentioned requires only a rather short program if you already have access to a uniform random number generator. Scaling the range of the second random number to the maximum of the probability density function greatly increases efficiency, especially for distributions that extend to very large numbers. Given the parameters of the density function, it is easy to calculate its height at any particular value as well as its maximum height.

I certainly agree that using the sum of Bernoulli trials is very inefficient, especially for large numbers.

Mike Elzinga said: How about the analysis tools in Microsoft Excel? Go to Tools and select Add-ins and get the Analysis tools. There are several random number generators there. Can you use Excel to do what you want to do?

I'm writing this off-the-cuff, with no testing (heck, I'm not even sure it's syntactically correct), but you can use it. It's based off of the ideas at http://www.winlab.rutgers.edu/~rito/ece541p1.pdf, but I think it's the same technique in Knuth (my copy of which is at work).

I am also assuming that a "binomial random variable" is functionally the same as a normal random variable.


// Returns two normal random value with mean 0 and standard deviation 1
function get2Normals()
{
var w = 2;
var v = []
while (w > 1) {
var u = [Math.random(), Math.random()];
var v = u.map(function (z) {return 2*z-1});
w = v[0]*v[0] + v[1]*v[1];
}
var y = Math.sqrt(-2*Math.log(w)/w);
var x = v.map(function(z) {return z*y;});
return x;
}


I can't get that to format properly...

Reed,

From what you wrote, you already have a good solution for small population sizes. For large sizes, you can just use a normal approximation. A normal random number generator is very simple to implement in Javascript: see this page, for example. The normal approximation works quite well even for relatively small population sizes, as long as the success probability p is not too small all too large - a useful heuristic is to use the approximation if np > 5 and n(1-p) > 5. Your only difficult case is when n is very large and p is very small, in which case you want to sample from a Poisson distribution with parameter Lambda = np. A simple algorithm can be found in this Wikipedia article.

What kind of resolution do you need? (how many unique values in the domain?) If the domain is sufficiently small, one cheap-and-dirty thing that could be done would be to pre-calculate an array containing samples that reflect a binomial distribution frequency of occurance, then index that table with a non-binomial random number. However, if the array is too large you are either paying for bandwidth to transmit it or the client is paying to calculate it on every startup. May not work for your needs... just a thought

Blaise Pascal said: I am also assuming that a "binomial random variable" is functionally the same as a normal random variable.

Reed A. Cartwright said: I'd love to have the gsl_ran_binomial from GSL ported to javascript so I can include it in my project.

Well I thought, javascript is part of the C syntax phylogenetic tree, and presumably this is mostly numeric calculations (no objects, data structures etc), so how hard can it be?
I was just looking gsl-1.12/randist/binomial_tpe.c source, trying to gauge the amount of work. It seems to call three other functions which would require translation or javascript substitutions - Stirling() (I assume Stirling's approximation for n!) which should be no problem, gsl_pow_int() which I assume is x^n, simple enough, and gsl_ran_uniform() which is the usual flat distribution, so translation seemed tractable.

Then I noticed its loaded with "goto"s! gotos?!!! GOTOS?!!! I thought I was seeing things. Jeez, what century is this? Did these guys just translate a fortran program?! BLECHH

Reed A. Cartwright said: I'm asking for an implementation, because I can't find one and don't have the time to implement one. I'd love to have the gsl_ran_binomial from GSL ported to javascript so I can include it in my project.

Then I noticed its loaded with “goto”s! gotos?!!! GOTOS?!!! I thought I was seeing things. Jeez, what century is this? Did these guys just translate a fortran program?! BLECHH

— Sean McCorkle

I had a go at doing it, I expect it has errors.

I haven't had time to work out what this function is all about, plus its my first code in JavaScript.

I expect you know how to test it (I don't), I don't have anymore time at the moment to look.

anyway hope its at least a start

goto:

http://www.orieladmin.plus.com/JS/

then right click - view source.

Dan Earle said: I had a go at doing it, I expect it has errors. I haven't had time to work out what this function is all about, plus its my first code in JavaScript. I expect you know how to test it (I don't), I don't have anymore time at the moment to look. anyway hope its at least a start

1. Whether there is any effect of moving from "int" and "double" types in C to "var" in Javascript (which are all floating point). This is a limitation of Javascript not a problem with the port. I don't know enough about how Javascript converts between integers and reals to know whether this is a problem.
2. Whether the Javascript math.random() function is a good random number generator. I don't know if there is an alternative (besides porting the GSL uniform random generator as well), but it may be worth a cursory investigation.

Made small change:

realised I could just use some breaks instead of the separate returns on each finish case - just shows you never need to use goto's.

Joe:
Yes it seems JavaScript doesn't have integer types, so I hope I used the Math.floor in the appropriate places...

Thanks, Dan, for doing the heavy lifting. I haven't tested it, but I will. I expect that in the end, I'll make some changes to the organization to convert your global functions into member functions of my "game" object.

Reed:
Let me know if you have some test code that finds a problem.
Looking forward to the "game" will it be hosted on this site??

Larry_boy:
Sorry for beating you to it, hope you didn't go to too much trouble.

Oh that was a stupid question!
you say it will be on this site in your opening entry.

can you plz send source code for development of lost articles and letters reconciliation system to my mail.technoligies used are java applets,JACOB,Mysql

This is just a heads up, seeing as I got here a bit late. I am very good in situations like these and am very available. <one of the joys of bring unemployed.>

Should anyone find themselves requiring problems solved, drop me a line, and I am sure I can help out. I know enough about js to get great joy in making it sit up like a nice puppy, and play well with others.

That Guy