1
$\begingroup$

I'm modeling a process which involves a subset $S$ of a large number $n_A$ of objects - call them balls. Each time I add a ball to $S$, it may dislodge another ball with probability proportional to the fraction of the total balls already in $S$.

I've gotten as far as this expression for the expected number of balls $n_k$ after $k$ additions, and I'm hoping someone might show me how to find a closed form expression for this series, or at least some bounds:

$$\langle n_{k}\rangle=k- \frac{1}{n_{A}}\sum_{a=1}^{k-1}1+ \frac{1}{{n_{A}}^2}\sum_{a=1}^{k-2}\sum_{b=1}^{a}1- \frac{1}{{n_{A}}^3}\sum_{a=1}^{k-3}\sum_{b=1}^{a}\sum_{c=1}^{b}1+ \frac{1}{{n_{A}}^4}\sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\sum_{d=1}^{c}1-...$$

$\endgroup$
  • 1
    $\begingroup$ Nested sums all using the same index $i$? $\endgroup$ – Martin R Apr 26 '16 at 13:07
  • $\begingroup$ Edited, thanks. $\endgroup$ – JHD Apr 26 '16 at 13:21
1
$\begingroup$

Note that $$\sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\sum_{d=1}^{c}1= \sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\binom c1=\sum_{a=1}^{k-4}\sum_{b=1}^{a}\binom {b+1}2=\sum_{a=1}^{k-4}\binom {a+2}3=\binom {k-1}4$$ and so on.

Hence $$\begin{align} \langle n_k\rangle &=k- \frac{1}{n_{A}}\sum_{a=1}^{k-1}1+ \frac{1}{{n_{A}}^2}\sum_{a=1}^{k-2}\sum_{b=1}^{a}1- \frac{1}{{n_{A}}^3}\sum_{a=1}^{k-3}\sum_{b=1}^{a}\sum_{c=1}^{b}1+ \frac{1}{{n_{A}}^4}\sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\sum_{d=1}^{c}1-...\\ & =k-\frac 1{n_A}\binom {k-1}1+\frac 1{n_A^2}\binom {k-1}2-\frac 1{n_A^3}\binom{k-1}3+\frac 1{n_A^4}\binom {k-1}4-\cdots\\ &=\sum_{r=0}^\infty \binom {k-1}r\left(- \frac 1{n_A}\right)^r\\ &=\sum_{r=0}^{k-1} \binom {k-1}r\left(- \frac 1{n_A}\right)^r \qquad\qquad\text{as } \binom {k-1}r=0 \text { for }r>k-1\\ &=\left(1-\frac1{n_A} \right)^{k-1}\qquad\blacksquare \end{align}$$

$\endgroup$
  • $\begingroup$ What a great piece of insight - thank you! I checked this with a spreadsheet and the correct answer is slightly different than your formula - possibly due to inaccurate problem statement - but your form is right on the money. I'll post it in case someone is working on a similar problem: $\endgroup$ – JHD Apr 26 '16 at 21:39
  • $\begingroup$ You're welcome! Glad you found the hint helpful. Have completed the solution. $\endgroup$ – hypergeometric Apr 27 '16 at 2:14
0
$\begingroup$

Thanks to @hypergeometric for the insight that led to this. Now I'm off to look for implementations of the biomial coefficient. ;^)

$$\langle n_{k}\rangle=\sum_{r=0}^{k-1} {(-1)^r \frac 1{n_A^r}\binom {k}r}$$

$\endgroup$
  • $\begingroup$ You're welcome!. FYI the binomial coeff shown in your solution above should be $\binom {k-1}r$ instead of $\binom kr$. $\endgroup$ – hypergeometric Apr 27 '16 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.