# Expected cost of algorithm

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^i$, where $i$ 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_{i=0}^{D-1} p_m(i) \cdot g^i$$ where $p_m(i)$ is the probability to draw $i$ balls of this colour.

### First question

It is save to say that for the first colour to draw $$p_m(i) = \frac{D}{D\cdot R} \cdot \frac{D-1}{D\cdot R-1} \cdot\ ...\ \cdot \frac{D-(i-1)}{D\cdot R-(i-1)}$$

Is it right, that I can reduce this to the Binomial distribution

$$p_m(i) = \binom {m}{i} \cdot \left(\frac{D}{D\cdot R}\right)^i \cdot \left(1 - \frac{D}{D\cdot R}\right)^{m-i}$$

and if so why? I think not, because the binomial distribution is only for independent experiments, and once I have drawn a (let's say red) ball, the probability to draw another red ball goes down. However maybe I am at least able to say

$$p_m(i) < \binom {m}{i} \cdot \left(\frac{D}{D\cdot R}\right)^i \cdot \left(1 - \frac{D}{D\cdot R}\right)^{m-i} \qquad ?$$

After all I am going to try to find an upper bound for the cost.

### Second question

Can I say that the total expected cost is $$R \cdot \sum_{i=0}^{D-1} p_m(i) \cdot g^i \qquad ?$$ On the one hand, all colours are equal, on the other hand having many balls drawn of one colour reduces the likelihood for other colours to be drawn, so I am not sure. Would this be at least a reasonable approximation as an upper bound?

The number of balls of a particular color being drawn follows a hypergeometric distribution, with pmf

$$\Pr\{X = k\} = \frac {\displaystyle \binom {d} {k} \binom {(r-1)d} {m-k}} {\displaystyle \binom {rd} {m}}, k = 0, 1, \ldots, m$$

Therefore the expected cost for this particular color is $$E[g^X] = \sum_{k=0}^{d-1} g^k \frac {\displaystyle \binom {d} {k} \binom {(r-1)d} {m-k}} {\displaystyle \binom {rd} {m}}$$

You are correct that since the distribution of each particular color are identical, we have $$E\left[\sum_{j=1}^r g^{X_j}\right] = \sum_{j=1}^r E[g^{X_j}] = rE[g^{X_j}]$$

The sum itself does not have a closed form solution (it is a hypergeometric function)

• Thanks for the hypergeometric distribution. After that (answer to my question 2) I am not sure I can follow: Please keep in mind, that I continue to draw all the time. From the entire urn I draw $m$ times. So if I draw a couple of white and red balls, that would change the number of available balls and thus the concrete pmf (still hypergeometric, but with different parameters) of the available black balls? – Make42 Aug 15 '17 at 11:13
• Sorry previously I misread that you are drawing $d-1$ balls out from the urn. Now you draw $m$ number of balls out of the urn, so I updated the formula. In this setting I am considering all the draw all in once, not one by one. $X$ is the number of balls of a particular color over all $m$ drawn balls. Finally, if your magical reason is that all color must keep at least one in the urn, I think you just reduce $d$ to $d-1$ and you will be fine. – BGM Aug 15 '17 at 15:28
• How is it making a difference whether I draw all balls at once or one at the time? Shouldn't be the probability be the same? – Make42 Aug 16 '17 at 7:33
• Yes then I just misunderstand your doubt – BGM Aug 16 '17 at 10:51
• What I mean is this (considering I am taking one ball out after the other): If you have only two colors (white, black) and you want to know about likelihoods of taking the amount of white balls taken out, you use the Binomial distribution if you put the balls back in - because for each draw you the likelihood of drawing a white does not change. But if don't put the drawn balls back, you need to use the hypergeometric distribution - so a different one. For my scenario you don't put the balls back in, so for each color we have a hypergeometrical distribution. – Make42 Aug 17 '17 at 19:40