Writings
Table of Contents
Here is some material I wrote on maths and coding in Python. Here is the same list, sorted by date.
1. Math Related
- Caching, alias memoization. I like to think in terms of recursion. which leads to solutions formulated in terms of recursion. Here are some examples to demonstrate how to use recursion to solve probability problems, and how to implement them in python.
- Weighted random shuffling of a set of numbers. Typically, when shuffling cards, or numbers, any order has the same probability. However, what algorithm can we use if we want to assign weights to some elements so that these elements have higher probability to end up first? This we discuss here.
- Throwing a six-sided die to fairly select a winner in a group. When we have one prize to hand out and want to select one winner out of six persons, we can use a six sided die to select the winner fairly. This is simple enough, but what to do if we have class of \(19\) children and one cookie? Here I develop an algorithm that selects fairly a child in the least number of throws, in expectation, for groups of any size. In passing, I discuss many related ideas of interest.
- MMM vs MUM: First Step Analysis. This explains why the attractive algorithm that aimed to select with equal probability one child out of a class fails. In passing we discuss hitting times and other fundamental concepts in probability theory.
- Vickrey auctions and complexity theory. The simulation of Vickrey auctions makes an interesting case to study some complexity theory, mainly of recursive algorithms. The interesting idea of this auction is that we need to find the value of the second highest bid instead of the highest bid. Hence, a simple computation of the maximum of a number of bids will not give us the answer we need.
- Complex graphs from simple ideas. Simple recursions can lead to unexpectedly intricate and nice graphs.
- Applying Snell's envelope to the secretary problem. For some inventory control problems I use optimal stopping, and to prove that a certain stopping time, i.e., strategy, is optimal, I can use Snell's envelope. To see how this works I apply it to the classical secretary problem. Now I don't particularly like this name, nor its application to hiring people, so I frame the problem in terms of house selling and buying.
- Memoryless Excursions. Sometimes I come across some quick probabilistic arguments to see that some (in)equality is true. However, mistakes with probability easily made. Moreover, slick arguments often only work for very particular problems. Therefore, I am not so fond of such approaches. In this post I tackle one such argument, show that it is wrong in general, and then I demonstrate numerous different methods that all lead to the same (correct) answer.
- Simulating a non-homogeneous Poisson process. For some project I had to simulate a non-homogeneous Poisson process. A bit of searching on the web lead to a nice paper, but the paper did not contain actual code, and it was also slightly more general than I needed for my project. This post contains math and code to simulate piece-wise constant Poisson proceses.
- Solving a game with a MIP solver. Mixed integer programming problems find many applications in Operations Research. They can also be used to solve games as Sudoku, or the one of this page.
- Integration with indicators and Fubini. This posts demonstrates how to use indicator functions and Fubini's theorem to rewrite \(\E X\) and \(\E{X^2}\) in terms of the survivor function \(G\) of \(X\).
- Density estimation and kernels. I investigate two ways to make a plot of the probability mass function that is bases on real-valued observations. One is simple, and works well, the other is complicated, and seems not to work out of the box.
- Metropolis-Hastings algorithm. I found the idea behind the Metropolis-Hastings algorithm somewhat unclear, in particular because for most of the problems I work on, it is impossible (?) to provide a functional specification of the stationary probability, up to the normalization constant. However, if this functional form is known, the Metropolis-Hastings algorithm can be used. Here I provide an example.