<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">2017-01-17 22:13 GMT+01:00 Nadav Har'El <span dir="ltr"><<a href="mailto:nyh@scylladb.com" target="_blank">nyh@scylladb.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote"><span class="gmail-">On Tue, Jan 17, 2017 at 7:18 PM, <a href="mailto:alebarde@gmail.com" target="_blank">alebarde@gmail.com</a> <span dir="ltr"><<a href="mailto:alebarde@gmail.com" target="_blank">alebarde@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div>Hi Nadav,<br><br></div>I may be wrong, but I think that the result of the current implementation is actually the expected one.<br></div>Using you example: probabilities for item 1, 2 and 3 are: 0.2, 0.4 and 0.4<br><br></div><div>P([1,2]) = P([2] | 1st=[1]) P([1]) + P([1] | 1st=[2]) P([2])<br></div></div></blockquote><div><br></div></span><div>Yes, this formula does fit well with the actual algorithm in the code. But, my question is *why* we want this formula to be correct:<br><br></div></div></div></div></blockquote><div>Just a note: this formula is correct and it is one of statistics fundamental law: <a href="https://en.wikipedia.org/wiki/Law_of_total_probability">https://en.wikipedia.org/wiki/Law_of_total_probability</a> + <a href="https://en.wikipedia.org/wiki/Bayes%27_theorem">https://en.wikipedia.org/wiki/Bayes%27_theorem</a><br></div><div>Thus, the result we get from random.choice IMHO definitely makes sense. Of course, I think we could always discuss about implementing other sampling methods if they are useful to some application.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><span class="gmail-"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><br></div><div>Now, P([1]) = 0.2 and P([2]) = 0.4. However:<br> P([2] | 1st=[1]) = 0.5 (2 and 3 have the same sampling probability)<br> P([1] | 1st=[2]) = 1/3 (1 and 3 have probability 0.2 and 0.4 that, once normalised, translate into 1/3 and 2/3 respectively)<br></div><div>Therefore P([1,2]) = 0.7/3 = 0.23333<br></div><div>Similarly, P([1,3]) = 0.23333 and P([2,3]) = 1.6/3 = 0.533333<br></div></div></blockquote><div><br></div></span><div>Right, these are the numbers that the algorithm in the current code, and the formula above, produce:<br><br></div><div>P([1,2]) = P([1,3]) = 0.23333<br></div><div>P([2,3]) = 0.53333<br><br></div><div>What I'm puzzled about is that these probabilities do not really fullfill the given probability vector 0.2, 0.4, 0.4...<br></div><div>Let me try to explain explain:<br><br></div><div>Why did the user choose the probabilities 0.2, 0.4, 0.4 for the three items in the first place?<br><br></div><div>One reasonable interpretation is that the user wants in his random picks to see item 1 half the time of item 2 or 3. <br>For example, maybe item 1 costs twice as much as item 2 or 3, so picking it half as often will result in an equal expenditure on each item.<br><br></div><div>If the user randomly picks the items individually (a single item at a time), he indeed gets exactly this distribution: 0.2 of the time item 1, 0.4 of the time item 2, 0.4 of the time item 3.<br><br></div><div>Now, what happens if he picks not individual items, but pairs of different items using numpy.random.choice with two items, replace=false?<br></div><div>Suddenly, the distribution of the individual items in the results get skewed: If we look at the expected number of times we'll see each item in one draw of a random pair, we will get:<br><br></div><div>E(1) = P([1,2]) + P([1,3]) = 0.46666<br></div><div>E(2) = P([1,2]) + P([2,3]) = 0.76666<br></div><div>E(3) = P([1,3]) + P([2,3]) = 0.76666<br><br></div><div>Or renormalizing by dividing by 2:<br><br></div><div>P(1) = 0.233333<br></div><div>P(2) = 0.383333<br></div><div>P(3) = 0.383333<br><br></div><div>As you can see this is not quite the probabilities we wanted (which were 0.2, 0.4, 0.4)! In the random pairs we picked, item 1 was used a bit more often than we wanted, and item 2 and 3 were used a bit less often!<br></div></div></div></div></blockquote><div><br></div><div>p is not the probability of the output but the one of the source finite population. I think that if you want to preserve that distribution, as Josef pointed out, you have to make extractions independent, that is either sample with replacement or approximate an infinite population (that is basically the same thing). But of course in this case you will also end up with events [X,X]. <br></div><div> </div><div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><div>So that brought my question of why we consider these numbers right.<br><br></div><div>In this example, it's actually possible to get the right item distribution, if we pick the pair outcomes with the following probabilties:<br><br></div><div> P([1,2]) = 0.2 (not 0.233333 as above)<br></div><div> P([1,3]) = 0.2<br></div><div> P([2,3]) = 0.6 (not 0.533333 as above)<br></div><br></div><div class="gmail_quote">Then, we get exactly the right P(1), P(2), P(3): 0.2, 0.4, 0.4<br><br></div><div class="gmail_quote">Interestingly, fixing things like I suggest is not always possible. Consider a different probability-vector example for three items - 0.99, 0.005, 0.005. Now, no matter which algorithm we use for randomly picking pairs from these three items, *each* returned pair will inevitably contain one of the two very-low-probability items, so each of those items will appear in roughly half the pairs, instead of in a vanishingly small percentage as we hoped.<br><br></div><div class="gmail_quote">But in other choices of probabilities (like the one in my original example), there is a solution. For 2-out-of-3 sampling we can actually show a system of three linear equations in three variables, so there is always one solution but if this solution has components not valid as probabilities (not in [0,1]) we end up with no solution - as happens in the 0.99, 0.005, 0.005 example.<br><br></div><div><div class="gmail-h5"><div class="gmail_quote"><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><br></div><div>What am I missing?<br><br></div><div>Alessandro<br></div><div> <br></div><div><div><div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2017-01-17 13:00 GMT+01:00 <span dir="ltr"><<a href="mailto:numpy-discussion-request@scipy.org" target="_blank">numpy-discussion-request@scip<wbr>y.org</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Hi, I'm looking for a way to find a random sample of C different items out<br>
of N items, with a some desired probabilty Pi for each item i.<br>
<br>
I saw that numpy has a function that supposedly does this,<br>
numpy.random.choice (with replace=False and a probabilities array), but<br>
looking at the algorithm actually implemented, I am wondering in what sense<br>
are the probabilities Pi actually obeyed...<br>
<br>
To me, the code doesn't seem to be doing the right thing... Let me explain:<br>
<br>
Consider a simple numerical example: We have 3 items, and need to pick 2<br>
different ones randomly. Let's assume the desired probabilities for item 1,<br>
2 and 3 are: 0.2, 0.4 and 0.4.<br>
<br>
Working out the equations there is exactly one solution here: The random<br>
outcome of numpy.random.choice in this case should be [1,2] at probability<br>
0.2, [1,3] at probabilty 0.2, and [2,3] at probability 0.6. That is indeed<br>
a solution for the desired probabilities because it yields item 1 in<br>
[1,2]+[1,3] = 0.2 + 0.2 = 2*P1 of the trials, item 2 in [1,2]+[2,3] =<br>
0.2+0.6 = 0.8 = 2*P2, etc.<br>
<br>
However, the algorithm in numpy.random.choice's replace=False generates, if<br>
I understand correctly, different probabilities for the outcomes: I believe<br>
in this case it generates [1,2] at probability 0.23333, [1,3] also 0.2333,<br>
and [2,3] at probability 0.53333.<br>
<br>
My question is how does this result fit the desired probabilities?<br>
<br>
If we get [1,2] at probability 0.23333 and [1,3] at probability 0.2333,<br>
then the expect number of "1" results we'll get per drawing is 0.23333 +<br>
0.2333 = 0.46666, and similarly for "2" the expected number 0.7666, and for<br>
"3" 0.76666. As you can see, the proportions are off: Item 2 is NOT twice<br>
common than item 1 as we originally desired (we asked for probabilities<br>
0.2, 0.4, 0.4 for the individual items!).<br>
<br>
<br>
--<br>
Nadav Har'El<br>
<a href="mailto:nyh@scylladb.com" target="_blank">nyh@scylladb.com</a><br>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <<a href="https://mail.scipy.org/pipermail/numpy-discussion/attachments/20170117/d1f0a1db/attachment-0001.html" rel="noreferrer" target="_blank">https://mail.scipy.org/piperm<wbr>ail/numpy-discussion/attachmen<wbr>ts/20170117/d1f0a1db/attachmen<wbr>t-0001.html</a>><br>
<br>
------------------------------<br>
<br>
Subject: Digest Footer<br>
<br>
______________________________<wbr>_________________<br>
NumPy-Discussion mailing list<br>
<a href="mailto:NumPy-Discussion@scipy.org" target="_blank">NumPy-Discussion@scipy.org</a><br>
<a href="https://mail.scipy.org/mailman/listinfo/numpy-discussion" rel="noreferrer" target="_blank">https://mail.scipy.org/mailman<wbr>/listinfo/numpy-discussion</a><br>
<br>
<br>
------------------------------<br>
<br>
End of NumPy-Discussion Digest, Vol 124, Issue 24<br>
******************************<wbr>*******************<span class="gmail-m_-3190996802041252572HOEnZb"><font color="#888888"><br>
</font></span></blockquote></div><span class="gmail-m_-3190996802041252572HOEnZb"><font color="#888888"><br><br clear="all"><br>-- <br><div class="gmail-m_-3190996802041252572m_7412123321628590327gmail_signature"><font size="1">------------------------------<wbr>------------------------------<wbr>--------------</font><font size="1"><br>
NOTICE:</font><font size="1"> Dlgs 196/2003 this e-mail and any attachments thereto may contain confidential information and are intended for the sole
use of the recipient(s) named above. If you are not the intended
recipient of this message you are hereby notified that any dissemination
or copying of this message is strictly prohibited. If you have received
this e-mail in error, please notify the sender either by telephone or
by e-mail and delete the material from any computer. Thank you.</font><font size="1"><br>
------------------------------</font><font size="1"><wbr>------------------------------</font><font size="1"><wbr>--------------</font></div>
</font></span></div></div></div></div></div></div></div>
<br>______________________________<wbr>_________________<br>
NumPy-Discussion mailing list<br>
<a href="mailto:NumPy-Discussion@scipy.org" target="_blank">NumPy-Discussion@scipy.org</a><br>
<a href="https://mail.scipy.org/mailman/listinfo/numpy-discussion" rel="noreferrer" target="_blank">https://mail.scipy.org/mailman<wbr>/listinfo/numpy-discussion</a><br>
<br></blockquote></div><br></div></div></div></div>
<br>______________________________<wbr>_________________<br>
NumPy-Discussion mailing list<br>
<a href="mailto:NumPy-Discussion@scipy.org">NumPy-Discussion@scipy.org</a><br>
<a href="https://mail.scipy.org/mailman/listinfo/numpy-discussion" rel="noreferrer" target="_blank">https://mail.scipy.org/<wbr>mailman/listinfo/numpy-<wbr>discussion</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"><font size="1">--------------------------------------------------------------------------</font><font size="1"><br>
NOTICE:</font><font size="1"> Dlgs 196/2003 this e-mail and any attachments thereto may contain confidential information and are intended for the sole
use of the recipient(s) named above. If you are not the intended
recipient of this message you are hereby notified that any dissemination
or copying of this message is strictly prohibited. If you have received
this e-mail in error, please notify the sender either by telephone or
by e-mail and delete the material from any computer. Thank you.</font><font size="1"><br>
------------------------------</font><font size="1">------------------------------</font><font size="1">--------------</font></div>
</div></div>