Selecting numbers on a number line where distribution tends to cluster at one end.

Lets say I've got a number line from $1$ to $100$. I want to randomly select $20$ integer numbers from the number line. But I want the numbers to tend to come from say $1$-$50$, with only a few coming from between $50$-$100$.

My initial thought on how to solve the problem is to use an exponential function, say $2^n$. Then, until I've reached $20$ numbers, select a random decimal between $1$ and $\sim 6.65$ for $n$. Rounding the result to the nearest integer to use as my next number.

I'm wondering if there is a better solution.

-
Maybe you can explain "only a few" and "a better solution" a little more, to get an appropriate answer. BTW, welcome to MathStackExchange. –  draks ... May 7 '12 at 18:25

2 Answers

There are too many possible answers here because your question is so vague. Here's one possible technique: Select a random number $r$ uniformly between 0 and 1. Calculate $r' = 1+\lfloor100r^2\rfloor$. Then you get $r'$ between 1 and 50 about 70.7% of the time. (Whenver $r$ is less than ${\sqrt 2 \over 2}\approx 0.707$), and between 1 and 25 half the time. It will be between 1 and $n$ about $10\sqrt n$ percent of the time.

The $r^2$ is the important part here; the $1+\lfloor100\ \cdots\rfloor$ stuff is only to transform the range of the function from real numbers in $[0,1]$ to integers in $[1,100]$.

You can bias the thing as much as you like toward low numbers by changing the $r^2$ to $r^3$ or some higher power. If you use $r^n$, then you get $r'$ bigger than 50 only whenever $r$ is less than $1\over \sqrt[n]{2}$.

In general, you can pick any function $f : [0,1]\to[0,1]$ that has the property that $f(x)≤x$, and then use $r' = 1+\lfloor100f(r)\rfloor$. By drawing different $f$, you can bias the generator more or less toward smaller numbers.

-

I think you are overthinking this (unless you need some sort of smoothly decaying distribution that puts more probability mass on the smaller elements). If you just need to distinguish the first 50 elements from the last 50, with no within-set distinctions, just hand-specify a discrete distribution without caring about the functional form too much.

If you want there to be a probability $p$ that the values come from $\{1,2,\cdots,50\}$ and probability $(1-p)$ that values come from $\{51,\cdots,100\}$, then just make a discrete distribution that is $p/50$ for any value in $\{1,2,\cdots,50\}$ and $(1-p)/50$ for any value in $\{51,\cdots,100\}$. Then $p$ tunes how lopsided the distribution is towards the first set, without making any individual element of that set more likely than any other. By putting $p$ close to 1, you can make the occurrence of elements from $\{51,\cdots,100\}$ as infrequent as you'd like for your purposes.

To implement this in software, you'll need to use a psuedorandom number generator to generate draws from a standard uniform distribution on (0,1). Compute the cumulative sum vector for the discrete distribution, $F(i) = \sum_{k\leq i}P(k)$. Define $F(0) = 0$ and then by definition you'll get $F(100) = 1$.

For a given uniform draw $u$, find the index $j$ such that $F(j) \leq u \leq F(j+1)$, and return $j+1$ as the drawn number. Languages such as Python (NumPy), Matlab, and C++ (Boost), provide this kind of user-defined discrete distribution as a built-in function, with built-in sampling functions. But it's often a good exercise to write your own discrete simulator at least once.

-