Counting Collisions

Specialeforsvar: Mathias Bæk Tejs Knudsen

Title: Counting Collisions

Resume: Lad os sige at $m$ bolde bliver kastet uniformt tilfældigt og uafhængigt ned i $n$ spande. Vi giver nye concentration bounds for antallet af kollisioner, dvs. antallet af par af bolde, der bliver kastet i den samme spand. Vi viser at man op til konstante faktorer kun behøver at betragte en idealiseret version, hvor alle kollisioner er uafhængige, samt bidraget fra en enkelt fastsat spand for at få concentration bounds. Vi
betragter også situationen hvor boldene bliver fordelt ved hjælp af en simple tabulation hash funktion. De concentration bounds vi får i dette tilfælde tillader os at vise concentration bounds for antallet af bolde der bliver kastet i en fastsat spand. Det udvider et resultat af P\v{a}tra\c{s}cu og Thorup [J.ACM '12] til tilfældet hvor antallet af bolde er polynomielt i antallet af spande.

Vejleder: Mikke Thorurp
Censor: Jørgen Bang-Jensen