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.