# Expected value for a function concerning a balls and bins problem

I'm optimizing a hash function mapping $M$ items into $N$ bins and I need a criterion for evaluating the quality of the mapping. Denoting the number of items put into bin $i$ by $x_i$, an ideal mapping would make each $x_i$ equal to either $\lfloor {\frac MN} \rfloor$ or $\lceil {\frac MN} \rceil$.

Currently, I'm using $\sum x_i ^ p$ with $p=3$ as my criterion. Are there simple closed form expressions for the expected value and variance assuming uniform random placement?

I might switch to another criterion, so I'm interested in formulas for them, too. I don't care about asymptotic expressions as the typical values are $10 < N < M < 1000$.

-

## 1 Answer

By symmetry and linearity of expectation, the expected value is just $N$ times the expected value of $x_i^p$ for one bin, that is,

$$N\sum_{k=0}^M\binom Mk\left(\frac1N\right)^k\left(1-\frac1N\right)^{M-k}k^3\;,$$

which according to Wolfram|Alpha is

$$\frac M{N^2}\left(M^2+3MN+N^2-3M-3N+2\right)\;.$$

for $p=3$. You can calculate the variance similarly, by expressing it as an expectation value, but the resulting expression will probably be rather complicated.

If you want to use a different value of $p$, just replace it in the W|A input.

-

Thank you for this helpful answer. Now it looks quite easy, but I couldn't hope to come to a usable expression in an acceptable time (and I didn't know that WA is that good). – maaartinus Oct 4 '12 at 18:04
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9298537373542786, "perplexity_flag": "head"}