0
$\begingroup$

I'm trying to generate random numbers that would be distributed according to a sample curve that I provide in the shape of vertices.

I came up with this:

function curve_map(curve) {
    //  convert to sorted points
    var points = [];
    for (var x in curve) { var y = Number(curve[x]);
        points.push( {'x' : Number(x), 'y' : y} );
    }
    points.sort(function(a,b) {return a.x - b.x});

    //  create segments
    this.segments = [];
    var posy = 0;   
    for (var i = 1; i < points.length; i++) {
        var n = points[i].y + points[i - 1].y;
        var seg = {
            'x0' : points[i - 1].x,     'x1' : points[i].x, 
            'y0' : points[i - 1].y,     'y1' : points[i].y,
            'n0' : posy,                'n1' : posy + n
        };
        posy = seg.n1;
        this.segments.push(seg);
    }

    //  normalize n
    for (var i = 0; i < this.segments.length; i++) {
        this.segments[i].n0 /= posy;
        this.segments[i].n1 /= posy;
        this.segments[i].nr = this.segments[i].n1 - this.segments[i].n0;
    }

    //  func
    this.apply = function(x) {
        for (var i = 0; i < this.segments.length; i++) {
            var seg = this.segments[i];
            if (x >= seg.n0 && x <= seg.n1) {
                var along = (x - seg.n0) / seg.nr;
                //along = seg.y0 / (seg.y1 - seg.y0);

                var val = seg.x0 + (seg.x1 - seg.x0) * along;
                return val;
            }
        }
    }.bind(this);
}

What this does is

  1. take 2 points and make a segment, preserving the original coordinates
  2. each segment's length is equal to the sum of Y of both points
  3. after creating a segment between all the points, normalize so the chain of segments reaches from 0 to 1

So now I have a chain of segments. If I feed it a value, it looks up which segment it belongs to, checks how far along in the segment it is and remaps the location to the original interpolated x coordinates of the segment.

In theory I expected this to shave off the corners of the original curve since I don't know how to account for the difference in Y values in each segment.

Anyways, the result is quite different:

enter image description here

The red curve is what I fed the "curve_map" and what it should mimic

The black one is ~10k uniformly distributed random values put through the algorithm.

At least it sorta follows the line... but this is nowhere near good enough. Also I'm out of ideas on how to fix it.

Does anybody know if what I'm trying to do actually has a name? So I could read up on it or maybe find a neat algorithm to port..

$\endgroup$

marked as duplicate by David Richerby, Evil, D.W. algorithms Nov 18 '16 at 16:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What do you mean "sample curve"? Is that a probability distribution function? Cumulative distribution function? Also, code is off-topic here. Please replace the code with a clear specification of the algorithmic task you're trying to solve (what are the inputs? what are the desired outputs?) and pseudocode for your algorithm. Finally, is this a discrete distribution or a continuous distribution? $\endgroup$ – D.W. Nov 16 '16 at 18:15
  • $\begingroup$ I don't really understand what you're trying to do. Also, your code doesn't do what you think it should and debugging it is off-topic so does including the code actually add anything? $\endgroup$ – David Richerby Nov 16 '16 at 18:31
1
$\begingroup$

For continuous distributions, you can use the inverse transform sampling method. See also https://stats.stackexchange.com/q/176955/2921 and https://en.wikipedia.org/wiki/Ziggurat_algorithm.

For discrete distributions, you just generate a random floating point number in the range [0,1], and then figure out which of the buckets $[0,p_1)$, $[p_1,p_1+p_2)$, $[p_1+p_2,p_1+p_2+p_3)$, ..., $[..,1]$ it falls into, where $p_1,p_2,p_3,\ldots$ are the desired probabilities of the possible values. See also https://stats.stackexchange.com/q/26858/2921 and http://www.keithschwarz.com/darts-dice-coins/.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.