Probability and Stochastic Processes

The so-called “birthday paradox” concerns the fact that even in surprisingly small groups the probability for at least two people to share their birthdate is surprisingly high.

The combinatorics of the Birthday Paradox are not hard; in fact, it is a standard example in introductory textbooks. Yet, the typical exact treatment provides no intuitive sense for the way the probability depends on the size of the sample and the population.

Here is an approximate solution that shows that the probability in question is, in fact, a Gaussian.

Imagine a parking lot, consisting of a long, linear strip of slots. Cars enter at one end and leave by the other. Let’s also stipulate that each arriving car takes the first available slot that it encounters, that is, it will park in the first empty slot that is nearest to the parking lot entrance. Cars arrive randomly, with a given, average interarrival time $\tau_A$. Furthermore, cars occupy each slot for a random amount of time, but all with a common average dwell time $\tau_D$.

If we number the slots, starting at the entrance, we may now ask the question: what is the probability that the slot with index $n$ is occupied?

Selecting a random element from an array of length n is easy: simply generate a random integer i, with 0 <= i < n, and use the array element at that index position. But what if the length of the array is not known beforehand, or is, in fact, infinite (i.e. a stream)? And what if we don’t just want a single element, but a set of m samples, without replacement?

Imagine a shared resource, such as a compute server. Users can submit jobs to the server. The resource is “free”, in the sense that no costs are imposed on the users. The question is how to best assign and prioritize jobs when multiple users submit jobs simultaneously.

I have started to get interested in Hidden Markov Models (HMM). As a warm-up, I prepared a pure Python implementation of the relevant algorithms (github).

The “Newsvendor Problem” is a classic problem in inventory and supply-chain management: how much product to carry in stock in the face of uncertain demand?

The problem is obviously of interest in its own right, but it is also an archetypical problem, meaning that variations of it arise frequently and in different contexts. It is therefore valuable to know “how to think about” this kind of problem; in particular, since in its simplest form, it has a closed-form, analytic solution.