4
$\begingroup$

Let's have n users with each having a ball and m boxes. The users put their ball in a random box. It takes exactly 10 seconds for all balls to be put in a random box (independently to the number of users). When the 10 seconds are passed, we remove the boxes with at least one ball and start the process again (each user get a new ball) until there is no boxes left.

We know that each iteration takes exactly 10 seconds, hence:

average_execution_time = average_iteration_count * 10

How can we calculate the average iteration count?

Here I describe an analog problem but it will help modelling a distributed computing problem.

$\endgroup$
  • $\begingroup$ Do you start back with $n$ users and one ball each, in each iteration? $\endgroup$ – Shash Dec 11 '14 at 3:32
  • $\begingroup$ Yes, exactly! n is independant to the iteration and the users always get one new ball. $\endgroup$ – DurandA Dec 11 '14 at 19:39
1
$\begingroup$

I think this is the required recurrence (for m people and n boxes):

\begin{align*} E_{n,m} &= \left( \sum_{j=1}^{n-1} \Bigg\vert \sum_{k=1}^j (-1)^{k+1} \binom{j}{k} k^m \Bigg \vert \binom{n}{j} \dfrac{E_{n-j,m}}{n^m}\right)+1 \\ E_{1,m} &= 1 \end{align*}

E.g. \begin{align*} E_{10,5} &= \dfrac{143552416944963272131}{44599077450547200000}\approx 3.21873063639351 \\ \\ E_{100,10} &\approx 12.1672191476212 \end{align*}

etc.

This is the maxima code I used:

m : 5$ for i : 2 thru 10 do E[i] : sum(abs(sum((-1)^(k+1) * binomial(j,k) * k^m,k,1,j) * binomial(i,j)) * (E[i-j]) / i^m,j,1,i-1) + 1;

Update:

We may also write in terms of stirling numbers of the second kind:

\begin{align*} E_{n,m} &= \left(\sum_{j=1}^{n-1} \left\lbrace {m \atop j} \right\rbrace \frac{n!}{(n-j)!} \dfrac{E_{n-j,m}}{n^m}\right)+1 \\ E_{1,m} &= 1 \end{align*}

load(stirling)$ m:5$ E[1]:1$ E[n]:=sum(stirling2(m,j)*factorial(n)/factorial(n-j)*E[n-j]/n^m,j,1,n-1)+1$ E[10];

$\endgroup$
  • $\begingroup$ You're results are on par with a simulation I built using python so you are probably right. However I don't get the same results as you using your formula. $$\begin{align*}E_{10,5} &= \dfrac{3759580194197153975951}{1156008087518183424000}\approx 3.25221\end{align*}$$ I am using Mathematica !input $\endgroup$ – DurandA Dec 14 '14 at 3:50
  • $\begingroup$ Hi, I updated the formula along with maxima code. I forgot to add 1. $\endgroup$ – gar Dec 14 '14 at 5:27
  • $\begingroup$ Using either first formula or stirling_s2 I get \begin{align*}E_{10,5} &= \dfrac{16852276906189664849401}{693604852510910054400}\approx 24.2967\end{align*} I am missing something? !input $\endgroup$ – DurandA Dec 14 '14 at 14:15
  • $\begingroup$ Did you try translating the maxima code instead? That one definitely gives the answer written there. $\endgroup$ – gar Dec 14 '14 at 15:17
  • 1
    $\begingroup$ Thanks for the correction. I have modified it now. $\endgroup$ – gar Dec 16 '14 at 4:23

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.