Nightclub Concentration Bounds

Learn a randomized algorithm using Chernoff bounds to solve the Berghain Bouncer Challenge, including a full mathematical derivation and code walkthrough.

Overview

A couple months ago, Listen Labs put out their “Berghain Bouncer Challenge”: a toy online optimization problem about admitting a diverse population of club goers into the popular nightclub. The obvious dynamic programming solution doesn’t scale very well; I’ll talk about a different randomized approach derived from Chernoff bounds, including a detailed derivation of the math and a walkthrough of my implementation code.

Tech stack