<p>Another possibility is to associate, with each element of the array, a random number drawn from an <a href="https://en.wikipedia.org/wiki/Exponential_distribution" rel="nofollow noreferrer">exponential distribution</a> with parameter given by the weight for that element. Then pick the element with the lowest such ‘ordering number’. In this case, the probability that a particular element has the lowest ordering number of the array is proportional to the array element's weight.</p>
<p>This is O(n), doesn't involve any reordering or extra storage, and the selection can be done in the course of a single pass through the array. The weights must be greater than zero, but don't have to sum to any particular value.</p>
<p>This has the further advantage that, if you store the ordering number with each array element, you have the option to sort the array by increasing ordering number, to get a random ordering of the array in which elements with higher weights have a higher probability of coming early (I've found this useful when deciding which DNS SRV record to pick, to decide which machine to query).</p>
<p>Repeated random sampling with replacement requires a new pass through the array each time; for random selection without replacement, the array can be sorted in order of increasing ordering number, and <em>k</em> elements can be read out in that order.</p>
<p>See the <a href="https://en.wikipedia.org/wiki/Exponential_distribution" rel="nofollow noreferrer">Wikipedia page about the exponential distribution</a> (in particular the remarks about the distribution of the minima of an ensemble of such variates) for the proof that the above is true, and also for the pointer towards the technique of generating such variates: if <em>T</em> has a uniform random distribution in [0,1), then <em>Z=-log(1-T)/w</em> (where <em>w</em> is the parameter of the distribution; here the weight of the associated element) has an exponential distribution.</p>
<p>That is:</p>
<ol>
<li>For each element <em>i</em> in the array, calculate <em>zi = -log(T)/wi</em> (or <em>zi = -log(1-T)/wi</em>), where T is drawn from a uniform distribution in [0,1), and <em>wi</em> is the weight of the I'th element.</li>
<li>Select the element which has the lowest <em>zi</em>.</li>
</ol>
<p>The element <em>i</em> will be selected with probability <em>wi/(w1+w2+...+wn)</em>.</p>
<p>See below for an illustration of this in Python, which takes a single pass through the array of weights, for each of 10000 trials.</p>
<pre><code>import math, random

random.seed()

weights = [10, 20, 50, 20]
nw = len(weights)
results = [0 for i in range(nw)]

n = 10000
while n &gt; 0: # do n trials
    smallest_i = 0
    smallest_z = -math.log(1-random.random())/weights[0]
    for i in range(1, nw):
        z = -math.log(1-random.random())/weights[i]
        if z &lt; smallest_z:
            smallest_i = i
            smallest_z = z

    results[smallest_i] += 1 # accumulate our choices

    n -= 1

for i in range(nw):
    print(&quot;{} -&gt; {}&quot;.format(weights[i], results[i]))
</code></pre>
<hr />
<p><strong>Edit (for history):</strong> after posting this, I felt sure I couldn't be the first to have thought of it, and another search with this solution in mind shows that this is indeed the case.</p>
<ul>
<li>In an <a href="https://stackoverflow.com/a/30226926/375147">answer to a similar question</a>, <a href="https://stackoverflow.com/users/854793/joe-k">Joe K</a> suggested this algorithm (and also noted that someone else must have thought of it before).</li>
<li>Another <a href="https://stackoverflow.com/a/20548895/375147">answer to that question</a>, meanwhile, pointed to <a href="https://doi.org/10.1016/j.ipl.2005.11.003" rel="nofollow noreferrer">Efraimidis and Spirakis</a> (<a href="https://docdro.id/XTglD09" rel="nofollow noreferrer">preprint</a>), which describes a similar method.</li>
<li>I'm pretty sure, looking at it, that the Efraimidis and Spirakis is in fact the same exponential-distribution algorithm in disguise, and this is corroborated by a passing remark in the <a href="https://en.wikipedia.org/wiki/Reservoir_sampling" rel="nofollow noreferrer">Wikipedia page about Reservoir sampling</a> that ‘[e]quivalently, a more numerically stable formulation of this algorithm’ is the exponential-distribution algorithm above. The reference there is to <a href="https://arxiv.org/abs/1305.0941" rel="nofollow noreferrer">a sequence of lecture notes by Richard Arratia</a>; the relevant property of the exponential distribution is mentioned in Sect.1.3 (which mentions that something similar to this is a ‘familiar fact’ in some circles), but not its relationship to the Efraimidis and Spirakis algorithm.</li>
</ul>
Weighted random selection from array
<p>I would like to randomly select one element from an array, but each element has a known probability of selection.</p>

<p>All chances together (within the array) sums to 1.</p>

<p>What algorithm would you suggest as the fastest and most suitable for huge calculations?</p>

<p>Example:</p>

<pre><code>id =&gt; chance
array[
    0 =&gt; 0.8
    1 =&gt; 0.2
]
</code></pre>

<p>for this pseudocode, the algorithm in question should on multiple calls statistically return four elements on id <code>0</code> for one element on id <code>1</code>.</p>