1
$\begingroup$

I have been trying to analyze a randomized algorithm I cooked up and have found the need to compute some moments of a random variable modeling an aspect of the algorithm but I am unsure if there is a nice closed form. Suppose the random variable in question is $X$ and it can take a value $i \in \lbrace 0, 1, \cdots, k \rbrace$ with probability $$\text{Pr}\lbrace X = i \rbrace = \binom{n}{k}^{-1}\binom{M}{i}\binom{n-M}{k-i}$$ where $n \geq M \geq 1$ and $n \geq k \geq 1$. Note that I assume that $\binom{a}{b} = 0$ if $a < b$ since there are $0$ ways to choose size $b$ sets out of a size $a$ set when this inequality holds. It is clear by the Chu-Vandermonde identity that indeed these values are probabilities because $$\sum_{i=0}^{k} \text{Pr}\lbrace X = i \rbrace = \binom{n}{k}^{-1} \sum_{i=0}^k \binom{M}{i}\binom{n-M}{k-i} = 1$$ The first moment of $X$, namely its expectation, can be computed analytically as \begin{align} \mathbb{E}(X) &= \sum_{i=0}^k i \text{Pr}\lbrace X = i \rbrace \\ &= \binom{n}{k}^{-1} \sum_{i=1}^k i \binom{M}{i}\binom{n-M}{k-i} \\ &= M \binom{n}{k}^{-1} \sum_{i=1}^k \binom{M-1}{i-1}\binom{(n-1)-(M-1)}{(k-1)-(i-1)} \\ &= M \binom{n}{k}^{-1} \binom{n-1}{k-1} \\ &= \frac{Mk}{n} \end{align}

I also need to compute $\mathbb{E}(X^2)$ so I can do a variance calculation but I am not sure how to go about it. One can find a loose upper bound of $Mk^2/n$ but at least empirically, it seems for the valid ranges of $k$, the upper bound can at least be made to be $Mk^{3/2}/n$. If I could find an exact expression to this moment, I would feel a lot better of where I might be able to go with this algorithm.

So does anyone recognize this probability distribution and have insight into the desired moment I want to compute?

$\endgroup$

1 Answer 1

1
$\begingroup$

I did some digging and found the probability distribution I was looking for was the Hypergeometric distribution. This gave me all the information I needed to finish the analysis of my randomized algorithm!

$\endgroup$

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.