I'm looking to create an algorithm that allows me to select a number(index) from a list based on it's fractional weight component. It's for load balancing, I'll give an example below of what I mean.
lets say I have 3 nodes, N1 is 1.0, N2 is 1.0 and N3 is 2.0. I need to be able to select a Node N from this list and obtain N3 50%, N1 25%, N2 25% of the time after 3/6/9 etc iterations. This list would be dynamic in size and contain different weight values of any number from 0 to inf. I'm uncertain how to proceed.
Suppose you have $N$ nodes. Let the weight of the $i^{\mathrm{th}}$ node be $x_i$ and define $X = \sum_i x_i$. Partition the line segment from $0$ to $1$ at the following $N-1$ places:
$$ p_i = \sum_{n=0}^{i} x_i / X, \,\,\ i=1,2,\dots,N-1 $$
Thus, your partition will look like $\{0,p_1,p_2,\dots,p_{N-1},1\}$. Then choose a uniformly distributed random number between $0$ and $1$ and select the node based on the partition in which it lies. That is, if your random number $y \in [0,p_1)$, then choose node 1. If $y\in[p_1,p_2)$, then choose node 2, and so on.
The above will assign larger partitions to the nodes with the larger weights, so a uniformly distributed random number will fall in their partition more often.
For instance, say you have five nodes with weights 1,1,2,2, and 1. Then $X=7$ and we get the following partition:
$$ \{0, \,\, 1/7, \,\, 2/7, \,\, 4/7, \,\, 6/7, \,\, 1 \} $$
If the random number we get is then, say, $0.276$, we would choose node $2$ since $1/7 < 0.276 < 2/7$.