Re: looking for a random function

From: Thad Smith (ThadSmith_at_acm.org)
Date: 03/29/04 

Date: Sun, 28 Mar 2004 16:53:41 -0700

Pacsek wrote:
 
> I'm trying to get an algorithm, preferably in C, that would pick up a random
> positive integer number, say, between 1 and n, n being a positive integer, too,
> but there would be a linear probability of picking the smaller number first. The
> higher the number, the less likely it will be selected. So 1 would have the most,
> n the least chance to be picked, and so on for the numbers in between.

The description calls for another parameter. n is one of them, but we
also need the ratio of the probability of selecting the 1 vs. the
probability of selecting n, which defines the slope of the linear
relationship.

Consider transforming this into a selecting a real value in the range 0
to 1, which can easily be scaled into an integer 1 to n. The
probability density function would be a trapezoid. Let the relative
probability of selecting 0 as a and selecting 1 as b. Then the
trapezoid has height a at x=0, height b at x=1. The total area is
(a+b)/2. We can scale a and b so that the area is 1.

Generate a random value r with even distribution in [0,1). Solve for
the value c, from 0 to 1, such that the area under the trapezoid curve
from 0 to c = r. c is then a derived random value with the distribution
described by the trapezoid, which has the linear change in probability.

Once you have the random value c, multiply by n, truncate, and add 1 to
get your desired range.

Solving for c given the area involves the solution of a quadratic
equation. If you write code to implement this allowing for a parameter
a/b, you probably will have to write a special case for even
distribution.

Thad

Relevant Pages

  • Re: Factoring, SF, and transforms
    ... >>probability that no head has resulted by the nth flip. ... any positive integer; this is what you were disputing. ... > ALL cases where the coin eventually lands on heads. ...
    (sci.crypt)
  • Re: please check my homework
    ... > /* return the probability of x successes in n events, ... > given the probability p for success in a single event, ... In the above comment you should specify that n must be a positive integer, ...
    (comp.programming)
  • Re: SF: Infinity proof
    ... you can pick a positive integer at random by choosing a ... and then choosing the integer as follows: ... The normal way of handling probability concerning positive integers is ... This gives a probability distribution depending on k, ...
    (sci.crypt)
  • Re: What does a "uniformly randomly picked subset from N" mean?
    ... Except that if selecting one member "at random" from a set of objects ... means that each object must have 'the same probability' of being ... It would require that a countably infinite number of equal values add up ... First a random subset of N could be finite set. ...
    (sci.math)
  • Nonrenormalization vs Renormalization 10: Gamma Analyzed By PI
    ... The gamma function already derives from Probable Influence/Causation ... other asymmetric nonnegative real line distributions, ... Recall that for positive integer n, ... same way that conditional probability y/x converts to 1 + y - x in PI ...
    (sci.physics)