1
$\begingroup$

I am having an algorithm which cost I want to determine, but I am having trouble to do so. In order to do so, I tried to break it down to a well known scenario, to be able to communicate the issue:

Let's say I have an urn with balls of $R$ different colours. For each color there are $D$ balls in the urn, so in total there are $R\cdot D$ balls in the urn. Now I am going to draw $m$ balls from the urn. For some magical reasons, the maximum of balls I can draw of the same colour is $D-1$. Let's further say there is going to be a cost evoked for each type of ball I draw that is exponential to the number of balls I draw of that type, so $g^k$, where $k$ is the amount of balls I draw of a specific colour. Whether I draw three red balls and two black balls or three black balls and two red balls does not matter though - that is the same cost.

My goal is to find out what the expected cost is going to be.

Here are the thoughts: First one can say that the expected cost for each colour is $$ \sum_{k=0}^{D-1} p_c(k) \cdot g^k $$ where $p_c(k)$ is the probability to draw $k$ balls of the colour $c$. For a single color I can say that it follows individually the hypergeometrical distribution

$$ p_c(k) = \frac{ \binom {D}{k} \cdot \binom {R\cdot D - D}{m-k} }{ \binom {R\cdot D}{m} } $$

I had hoped that I could say that the total cost would be

$$ R \cdot \sum_{k=0}^{D-1} p_c(k) \cdot g^k $$

but this does not seem to be the case, as my experiments show: Here I chose $g=3, R=150, D=4$ and got for different $m$ after 100 experiments the cost_mean, while I expected from above formulas cost_expected:

     m  cost_mean  cost_expected
0    0     150.00     150.000000
1   30     219.96     219.208595
2   60     311.00     309.155349
3  120     566.64     555.690471
4  210    1150.32    1069.921732
5  300    1986.60    1642.216299
6  375    2903.40    1994.406183
7  450    4050.00    2020.841856

When thinking about it it is easy to see that $m=450=(D-1)\cdot R$ is the highest number of balls I am allowed to take out and that cost should be thus $4050=R\cdot g^{D-1}$, so I assume the implementation of my experiment is correct, and my formulas are not.

Where is my mistake in the formulas and what is the correct formula?


Disclaimer: This question is a follow up question of Expected cost of algorithm, but since I was able to figure a lot more out since then and the answer provided there is not correct regarding the aspects asked in this question here, I decided to ask a new one with all the new content.

$\endgroup$
1
$\begingroup$

$$R \cdot \sum_{i=0}^{D-1} p_m(i) \cdot g^k$$ doesn't actually make sense because $k$ is undefined, but I assume that what you really mean is $$\sum_{c=1}^R \sum_{k=0}^{D-1} p_c(k) \cdot g^k$$ The problem is that this assumes that the $p_c$ are independent: it counts, for example, $$\sum_{c=1}^R p_c(0) \cdot g^0$$ which is the total cost when drawing $0$ balls, but you're supposed to be drawing $m$ balls.

To handle interdependence you need to sum over complete draws: i.e. $$\sum_{b_1+\ldots+b_R = m}p(b_1,\ldots,b_R)\sum_{i=1}^R g^{b_i}$$ Given that the exact order of the $b_i$ doesn't change the cost it should be possible to restructure this as a sum over partitions of $m$ with a suitable multiplicity factor in the term, but I'm not sure that you're going to get a "nice" formula.

$\endgroup$
4
  • $\begingroup$ I corrected the formula that I meant in the question. It was a typo: I meant $k$ instead of $i$ and $c$ instead of $m$ in that formula. Maybe that is the same as $$\sum_{c=1}^R \sum_{k=0}^{D-1} p_c(k) \cdot g^k$$ ? $\endgroup$ – Make42 Aug 22 '17 at 7:27
  • $\begingroup$ It's effectively the same because the individual probability distribution $p_c$ is the same for each $c$. $\endgroup$ – Peter Taylor Aug 22 '17 at 7:34
  • $\begingroup$ What does this mean for me? How can I estimate the algorithmic cost of my algorithm? (Especially Big-O Notation, depending on $m$.) $\endgroup$ – Make42 Aug 22 '17 at 7:34
  • $\begingroup$ Could you explain your last term? $\endgroup$ – Make42 Sep 12 '17 at 15:08

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.