This questions stems from a problem that I encountered while writing a program. This problem was identical to this one. What I did on the spot was described as a "trick" with binary search over additional table with cumulative "weights". Anyway, I've been thinking of an even faster way, and it seemed obvious that the solution would be the following:
Create a list of points (weight, index_in_array), then find a function that goes exactly through (0, 0) and these points, and then it is pretty trivial - generate random number X, scale it so that it fits into range from 0 to accumulated weight and floor of the result is an index of an object.
Everything is fine, but I can't find anything about finding such a function. I believe that it must be (now please forgive me if I'm using bad wording, I never learned maths in English) monotonic, non-decreasing over whole range and must go through selected points exactly without fail (of course rounding errors and such, but it doesn't matter).
Any help will be appreciated, whether direct information about algorithm or more precise keywords which I can use to find the solution.
Maybe the easiest thing you can do is taking a piecewise linear function. Let $w_1,\dots w_n$ be the (positive) weights relative to the items indexed by $1,\dots,n$, and let $x_i=w_1+w_2+\dots+w_i$.
You want a function $f$ that interpolates the points $(0,0),(x_1,1),(x_2,2),\dots,(x_n,n)$.
Then, if I understood correctly, you generate a random number $x\in]0,x_n]$, calculate $ceiling(f(x))$ and this will give you the index of the selected item. (You could do it also with the floor function but then you'll have to consider $f(x)+1$ instead of only $f(x)$).
To build the piecewise linear function we'll need two generic "base functions". The first is the characteristic function of the interval $I_i=[x_i,x_{i+1}[$: \begin{equation} \chi_{_{i}}(x)=\left\{ \begin{array}{cc} 1&\quad&\text{if}\quad x\in[x_1,x_{i+1}[\\ 0&\quad&\text{if}\quad x\notin[x_1,x_{i+1}[ \end{array} \right. \end{equation} The second family of functions is given by the linear functions that interpolate couples of consecutive points: \begin{equation} f_i(x)=\frac{x-x_i}{w_i}+i \end{equation}
Your function is then given by: \begin{equation} f=f_1\chi_{_1}+f_2\chi_{_2}+\cdots+f_n\chi_{_n} \end{equation}