[math-fun] Probability question
Let set S contain n objects, each object having equal probability of being selected. At the end of k selections with replacement, what is the expected number of distinct objects that were selected?
Mean distinct number for a single trial looks like n*m/(n+m-1) , though I don't have a proof --- and presumably it is well-known anyway? WFL On 7/30/16, David Wilson <davidwwilson@comcast.net> wrote:
Let set S contain n objects, each object having equal probability of being selected. At the end of k selections with replacement, what is the expected number of distinct objects that were selected?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Since we have replacement, the probability that object i is *not* selected in k trial is (1-1/n)^k, so the mean number of distinct objects selected is n*(1-(1-1/n)^k). Victor On Fri, Jul 29, 2016 at 11:30 PM, David Wilson <davidwwilson@comcast.net> wrote:
Let set S contain n objects, each object having equal probability of being selected. At the end of k selections with replacement, what is the expected number of distinct objects that were selected?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This problem reminds me of Martin Gardner's (I think?) observation that if you throw 6 dice simultaneously onto a table and the count the number of different numbers that appear, the probability that the answer is exactly 4 is over 50%. On Sat, Jul 30, 2016 at 12:42 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Since we have replacement, the probability that object i is *not* selected in k trial is (1-1/n)^k, so the mean number of distinct objects selected is
n*(1-(1-1/n)^k).
Victor
On Fri, Jul 29, 2016 at 11:30 PM, David Wilson <davidwwilson@comcast.net> wrote:
Let set S contain n objects, each object having equal probability of being selected. At the end of k selections with replacement, what is the expected number of distinct objects that were selected?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
I was (accidentally) attacking the more general problem where m denotes the number of objects selected at each pass; and only now realise that m = 1 for DW's original question. Does VM's solution generalise to m > 1 ? I couldn't seem to make it work ... WFL On 7/30/16, Thane Plambeck <tplambeck@gmail.com> wrote:
This problem reminds me of Martin Gardner's (I think?) observation that if you throw 6 dice simultaneously onto a table and the count the number of different numbers that appear, the probability that the answer is exactly 4 is over 50%.
On Sat, Jul 30, 2016 at 12:42 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Since we have replacement, the probability that object i is *not* selected in k trial is (1-1/n)^k, so the mean number of distinct objects selected is
n*(1-(1-1/n)^k).
Victor
On Fri, Jul 29, 2016 at 11:30 PM, David Wilson <davidwwilson@comcast.net> wrote:
Let set S contain n objects, each object having equal probability of being selected. At the end of k selections with replacement, what is the expected number of distinct objects that were selected?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/ _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes --- the probability of *not* selecting a particular element in one pass is (1-m/n). Since we're using replacement, each pass is independent so the expected number of selected items after k passes is n*(1-(1-m/n)^k) Victor On Sat, Jul 30, 2016 at 6:53 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I was (accidentally) attacking the more general problem where m denotes the number of objects selected at each pass; and only now realise that m = 1 for DW's original question.
Does VM's solution generalise to m > 1 ? I couldn't seem to make it work ...
WFL
On 7/30/16, Thane Plambeck <tplambeck@gmail.com> wrote:
This problem reminds me of Martin Gardner's (I think?) observation that if you throw 6 dice simultaneously onto a table and the count the number of different numbers that appear, the probability that the answer is exactly 4 is over 50%.
On Sat, Jul 30, 2016 at 12:42 PM, Victor Miller <victorsmiller@gmail.com
wrote:
Since we have replacement, the probability that object i is *not* selected in k trial is (1-1/n)^k, so the mean number of distinct objects selected is
n*(1-(1-1/n)^k).
Victor
On Fri, Jul 29, 2016 at 11:30 PM, David Wilson < davidwwilson@comcast.net> wrote:
Let set S contain n objects, each object having equal probability of being selected. At the end of k selections with replacement, what is the expected number of distinct objects that were selected?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/ _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
David Wilson -
Fred Lunnon -
Thane Plambeck -
Victor Miller