Wikipedia:Reference desk/Archives/Mathematics/2016 April 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 30

Calculating Expected Value

Say that I randomly choose k balls out of n balls with repetitions, until the first time I get some ball that I've already chosen in the past (I can choose it again, since tere're repetitions). Let X denote the number of choices until the first time when I choose some ball that I've already chosen. What is the expected value of X? I thought that $\Pr(X=k+1)={\frac {\binom {n}{k}}{n^{k}}}\cdot {\frac {k}{n}}$ (because I need to choose a subset of k distinct balls, and then, to choose one of thes balls), but this leads to expected value < 1, which does not make sense to me. What is the correct expected value of X? Thanks in advance! 80.246.136.227 (talk) 06:12, 30 April 2016 (UTC)

I'm not sure there can even be an analytic formula for this. If k > n/2, the exact number of repetitions is 2, and so the expected value is 2. For k = n/2, the exact number of repetitions is either 2 or 3, the latter being very unlikely, so the expected value is slightly greater than 2. So it seems that there's a sort of kink point in the expected value function at k = n/2. Likewise, for k > n/3 the actual number of repetitions can be no more than 3, but for k = n/3 there is a slight chance of as many as 4 repetitions, so it seems that there's a kind of kink point there too. That's why I doubt there's an analytic function for the expected value. Loraof (talk) 15:49, 30 April 2016 (UTC)

For what it's worth, I've worked out the k=1 case (derivation omitted here), which is far simpler than other cases. We have

$Pr(X=x)={\frac {x-1}{n^{x-1}}}\prod _{j=2}^{x-1}\left(n-(x-j)\right)$

and

$E(X)=\sum _{x=2}^{n+1}\left({\frac {x(x-1)}{n^{x-1}}}\prod _{j=2}^{x-1}(n-(x-j))\right).$

Loraof (talk) 21:58, 30 April 2016 (UTC)

And the other relatively simple case has k=n/2. Then X=3 if all the ones not drawn on the first repetition are drawn on the second rep; otherwise X=2. So

$Pr(X=3)={\frac {k}{n}}\cdot {\frac {k-1}{n-1}}\cdots {\frac {1}{k+1}}={\frac {k!}{n!/k!}}={\frac {(k!)^{2}}{n!}}$

and Pr(X=2) equals 1 minus that. Hence

$E(X)=2\cdot \left(1-{\frac {(k!)^{2}}{n!}}\right)+3\cdot {\frac {(k!)^{2}}{n!}}=2+{\frac {(k!)^{2}}{n!}}.$

Loraof (talk) 23:56, 30 April 2016 (UTC)

These formulae helped me a lot! Thank you! 213.8.204.72 (talk) 11:43, 1 May 2016 (UTC)

Assuming the choice model in question is: I reach into a bag of n balls and choose k all at once (so, without repetition), then put all k back and do this again: the probability that you see a first repeated ball on step t+1 is

$\left(1-{\frac {\binom {n-tk}{k}}{\binom {n}{k}}}\right)\cdot \prod _{i=0}^{t-1}{\frac {\binom {n-ik}{k}}{\binom {n}{k}}}$.

(We take ${\binom {a}{b}}=0$ if a < b, including if a < 0.) From the probability distribution it is routine to write down a formula for the expected value. A priori this is an infinite sum, but of course only the first n/k or so terms are nonzero. Possibly this expression simplifies in some reasonable way, but I haven't thought about it. --JBL (talk) 19:08, 3 May 2016 (UTC)

Also, the case k = 1 is an expectation form of the birthday problem and is treated here. --JBL (talk) 19:17, 3 May 2016 (UTC)