Perl: the Markov chain saw PerlMonks

### Re: Randomly biased, random numbers.

by roboticus (Chancellor)
 on Dec 05, 2013 at 23:11 UTC ( #1065862=note: print w/replies, xml ) Need Help??

in reply to Randomly biased, random numbers.

I used to use a "density map" generator back in the day. Basically each time you want a random coordinate, you generate the coordinate plus one extra random number. You then check the number against a density function, and if the extra random number is less than the density at that location, you return the coordinates. Otherwise you try again:

```sub generate_coordinate {
my \$fDensity = shift;
my @coordinate;
{
@coordinate = (rand, rand);
redo if \$fDensity->(rand, @coordinate);
}
return @coordinate;
}

sub density_uniform { 1 }
sub density_h_gradient { \$_[0] < \$_[2] }
sub density_v_gradient { \$_[0] < \$_[1] }

sub density_broken [ 0 }

sub density_lookup {
my (\$chk, \$r, \$c) = @_;
return \$lookup_table[\$r][\$c]<\$chk;
}

So by defining an appropriate density map function, you can create many types of distributions. The disadvantage is that your density map function may reject too many candidates, slowing things down. (The density_broken function, for example, is quite useless in this regard.)

The reason that I thought you might like it is this: For testing a project, I would create distinct distributions by simply drawing an image with MSPAINT or similar and loading that into a lookup table and using a function like density_lookup.

I don't know your objections to your own suggestion, so I don't know if this one is interesting or not, though.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Replies are listed 'Best First'.
Re^2: Randomly biased, random numbers.
by BrowserUk (Pope) on Dec 05, 2013 at 23:43 UTC

Basically, it is too directed. That is, it requires parameters to be chosen -- the ratio between clustered picks and non-clustered; the size of clustering subrange; etc. -- which means I would essentially be choosing what to test and thus excluding anything I haven't thought of.

so I don't know if this one is interesting or not

This is very interesting. I particularly like the idea of using images -- whether hand-drawn, or grabbed at random from an image search -- to bias the picking process. It has so many possibilities ...

Eg. grab a random image, process the image with a filter to reduce it to a just points of a particular color or hue; or maybe use a Conway's Life type process to manipulate the pixels until groups of similar hues the reduce to single points; or a dozen other ideas; and then use those points as my dataset.

The only problem with the idea is that it has triggered so many possibilities for investigation, I might never get back to testing the algorithm :) Thanks for kicking down the doors on the box of my thought train!

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Randomly biased, random numbers.
by salva (Abbot) on Dec 06, 2013 at 09:43 UTC
Math::Vector::Real::MultiNormalMixture generates density functions which may suit the OP case and that can also be randomly parametrized.

Anyway, one problem with this approach is that the ratio of a discarded points could be too high.

In that case, a more efficient way may be to divide the plane in regions (i.e. triangles), calculate the probability of every region and then generate the random points first picking a region and then a point inside the region with your proposed algorithm using the conditioned density function.

Yes, the discard rate can be a problem. For the table lookup version in 2D, I had a speedup that worked decently: Generate the first coordinate, then use the same technique to generate the remaining coordinate. It can still be a problem, though, in the event you choose a "mostly black" line, but I never needed made anything better than that.

I also tried to make a "transformational" technique that wouldn't reject any coordinates, but never got it working well enough to use. (Rather: the technique worked fine, but coming up with the warping functions for the project was more difficult (for me, at any rate), so I simply tended to run the density-mapping version before going to lunch, going home for the day, etc.

The intention was: Generate a random coordinate, and "remap" it based on a displacement function. I was hoping to be able to turn a density function into a space warping function. The difficulties I had were primarily coming up with functions to warp space appropriately, and ensuring that I could hit any point in the desired output space without too much overhang. (If the function moved the point outside the desired range, you had to reject the point and try again anyway.)

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Create A New User
Node Status?
node history
Node Type: note [id://1065862]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (2)
As of 2018-05-26 08:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (192 votes). Check out past polls.

Notices?