1
$\begingroup$

The goal is to establish a set of probabilities to be used to select an integer value where the probability of selecting I is Q, I+1 is R, I+2 is S, ... I+n is Z and such that the integer with the highest selection probability can be set by the user and the integer probabilities of the integers before and after the highest probability integers have subsequently lower probabilities. (some sort of parametrized skewed normal distribution)

e.g. Generate a set of probabilities for a set of integers between 1 and 27 where the mean of the probability curve is such that the average integer selected will be 9.

I want to be able to code this in Java - so pseudo-code would be appreciated.

My temptation is to build the table by hand, but it turns out the getting the curve right is tricky because of the skew...

enter image description here

Another example:

enter image description here

$\endgroup$
9
  • $\begingroup$ Just to clarify, since your notation is a little confusing, would it be sufficient to find probability measure $P$ on $\mathbb{Z}$ such that for each $z \in \mathbb{Z}$ you have $P(z) = p_z$ where $p_z$ is fixed by a user ahead of time? Then you want code to be able to sample from this distribution? $\endgroup$
    – nullUser
    Commented Feb 25, 2015 at 21:40
  • $\begingroup$ In the software $p_{1}$ and $p_{27}$ will be assigned fixed values and $p_{x}$ will be user assignable such that the probability of $p_{x}=\frac{p\sum_{k=1}^{27}}{27}$ -- in the first particular example (above) $p_{x}$ is $p_{9}$ and in the second example (above) $p_{x}$ is $p_{12}$ $\endgroup$
    – Neoheurist
    Commented Feb 27, 2015 at 15:30
  • $\begingroup$ I had to learn the latex markup and I'm not sure that the notation that I've used is appropriate / correct... my apologies if I'm making my intent less clear $\endgroup$
    – Neoheurist
    Commented Feb 27, 2015 at 15:34
  • $\begingroup$ I want to create the curve based upon the values of $p_{1} p_{x} p_{27}$ such that: $\endgroup$
    – Neoheurist
    Commented Feb 27, 2015 at 15:44
  • $\begingroup$ float[27] probabilities = { $p_{1}$, $p_{2}$, ..., $p_{27}$ }; $\endgroup$
    – Neoheurist
    Commented Feb 27, 2015 at 15:48

3 Answers 3

1
$\begingroup$

I think the binomial distribution might satisfy your needs.

With range $a,\ldots,b$ and desired mean $k$, set the binomial parameter $p$ to $\dfrac{k-a}{b-a}$ (in your example, $p=\frac{8}{26}$). Then $p_i$ is equal to

$$\binom{b-a}{i-a}p^{i-a}(1-p)^{b-i}$$

$\endgroup$
1
  • $\begingroup$ Looks promising... now how to turn this into code... let me noodle on this for a few $\endgroup$
    – Neoheurist
    Commented Feb 27, 2015 at 16:47
0
$\begingroup$

Suppose you have a distribution $F$ that is strictly increasing and you want to generate random numbers with distribution $F$. It is an easy exercise to show that if $U$ is uniform on $[0,1]$, then $X := F^{-1}(U)$ has distribution $F$.

Thus if you know how to generate uniform random numbers, you can generate $F$-distributed random numbers.

//static double Finverse(double x) { ... }

double u = Math.random(); //uniform on [0,1]
double x = Finverse(u); //distributed according to F

Now distributions on $\mathbb{Z}$ aren't strictly increasing (they increase only at integers) so for your case you will have to do a little more.

Take the distribution you want on integers, and interpolate linearly inbetween the integers of positive mass. Use the given method to generate reals according to that distribtuion, then floor them to the nearest integer of positive mass. Then all the mass of the density is pushed onto the integers and will give the distribution you want.

$\endgroup$
2
  • $\begingroup$ It's the part in the { ... } that's of interest to me... $\endgroup$
    – Neoheurist
    Commented Feb 27, 2015 at 15:50
  • $\begingroup$ @nullUser: I think you are answering the wrong question here. Given integers $a,b,k$, with $a < k < b$, Neohurist wants a simple way to generate some nice probabilities $p_a,\ldots,p_b$ with mean $k$ (or with maximum probability at $p_k$ $-$ the question doesn't make this clear). $\endgroup$
    – TonyK
    Commented Feb 27, 2015 at 15:54
0
$\begingroup$

This is the current state of the code - I want to replace the pseudoProbabilities integer array (below) with a programmatically generated list of probabilities... the trick is generating the right curve as opposed to hand coding an approximation as I've had to do here...

public class Container
{
    private String servingRoot;
    private int containerCapacity;

    private List<List<String>> unitFileNames;

    private Random aleatory;
    private Orderer orderer;

    private final int[] pseudoProbabilities = { 100, 200, 400, 800, 900, 1000, 900, 775, 650, 525, 425, 350, 300, 275, 250, 225, 200, 175, 150, 125, 100, 75, 50, 25, 25, 25, 25 };

    private final int[] cumulativeProbabilities;

    private int sum = 0;

    /**
     * @param unitRoot
     * @param servingRoot
     * @throws Exception
     */
    public Container(String unitRoot, String servingRoot, int containerCapacity) throws Exception
    {
        // intialize objects from the file system

        reset(unitRoot, servingRoot, containerCapacity);

        // initialize member objects

        this.orderer = new Orderer();
        this.aleatory = new Random(System.currentTimeMillis());

        // build the cumulative probability table to randomly select unit sizes

        this.cumulativeProbabilities = new int[this.pseudoProbabilities.length];

        for (int index = 0; this.pseudoProbabilities.length > index; index++)
        {
            this.sum += this.pseudoProbabilities[index];

            this.cumulativeProbabilities[index] = this.sum;            
        }
    }

    /**
     * Load unit file names into an in-memory table.
     * 
     * Used to initialized or refresh the system without shutting down the server.
     * 
     * @param unitRoot
     * @param servingRoot
     * @throws Exception
     */
    public void reset(String unitRoot, String servingRoot, int containerCapacity) throws Exception
    {
        this.servingRoot = servingRoot;
        this.containerCapacity = containerCapacity;

        ArrayList<Path> units = (new FileList(unitRoot + "content" + File.separator).getList());

        // set up a matrix to store the units by size

        this.unitFileNames = new ArrayList<List<String>>(pseudoProbabilities.length);

        for (int unit = 0; pseudoProbabilities.length > unit; unit++)
        {
            unitFileNames.add(new ArrayList<String>());
        }

        String unitPath, unitPathParse;

        int unitRowIndex;

        // arrange the units within the in-memory table by size

        for (Path unit : units)
        {
            unitPath = unit.toString();
            unitPathParse = unitPath.substring(0, unitPath.lastIndexOf('\\'));
            unitRowIndex = Integer.valueOf(unitPathParse.substring(unitPathParse.lastIndexOf('\\') + 1)) - 1;

            // there may be (are) units longer than the standard size (ignore these)

            if (pseudoProbabilities.length > unitRowIndex)
            {
                unitFileNames.get(unitRowIndex).add(unitPath);
            }
        }
    }

    /**
     * Create a manifest of randomized unit files that completely fill the container.
     * 
     * @return
     * @throws Exception
     */
    public ArrayList<String> manifest() throws Exception
    {
        // Containers are assembled from unit

        int unallocatedContainerCapacity = this.containerCapacity;

        int probabilityTableProbe;
        int cumulativeProbabilityIndex;

        int unitCount;
        int unitSize;
        int unitSizeIndex = 0;

        int[] unitSizes = new int[unallocatedContainerCapacity];

        // build a proto-manifest of unit sizes (there's a bug in this code)

        while (0 < unallocatedContainerCapacity)
        {
            cumulativeProbabilityIndex = unallocatedContainerCapacity > this.cumulativeProbabilities.length - 1 ? this.cumulativeProbabilities.length - 1 : unallocatedContainerCapacity;

            probabilityTableProbe = this.aleatory.nextInt(this.cumulativeProbabilities[cumulativeProbabilityIndex]);

            while (probabilityTableProbe < this.cumulativeProbabilities[cumulativeProbabilityIndex])
            {
                cumulativeProbabilityIndex--;

                if (0 > cumulativeProbabilityIndex) break;
            }

            unitSize = cumulativeProbabilityIndex + 2;

            unitSizes[unitSizeIndex++] = unitSize;

            unallocatedContainerCapacity -= unitSize;
        }

        unitSizeIndex--;

        // randomize the distribution of the unit sizes within the container manifest
        // to compensate for smaller units tending to aggregate at the "end" of list

        orderer.shuffle(unitSizes, 0, unitSizeIndex);

        // create a randomized list of unit files to be loaded into a container

        ArrayList<String> containerManifest = new ArrayList<String>(unitSizes.length);

        while (0 <= unitSizeIndex)
        {
            // get the next unit size to randomly pull a unit to be added to the container manifest

            unitSize = unitSizes[unitSizeIndex];

            // get the count of units of this size to randomly select one

            unitCount = unitFileNames.get(unitSize - 1).size();

            // randomly select a unit of this this unit size to be added to the manifest

            containerManifest.add(unitFileNames.get(unitSize - 1).get(this.aleatory.nextInt(unitCount)));

            unitSizeIndex--;
        }

        return containerManifest;
    }
}
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .