# Expected cost of algorithm based on hypergeometrical distribution

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.

$$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.
• 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$$ ? – Make42 Aug 22 '17 at 7:27
• It's effectively the same because the individual probability distribution $p_c$ is the same for each $c$. – Peter Taylor Aug 22 '17 at 7:34
• What does this mean for me? How can I estimate the algorithmic cost of my algorithm? (Especially Big-O Notation, depending on $m$.) – Make42 Aug 22 '17 at 7:34