Category Archives: Tutorial

How fast can you skip to your favorite song?

By | December 12, 2019

Zach Wissner-Gross’ column “The Riddler” over at FiveThirtyEight poses the following interesting question, attributed originally to Austin Chen: You have a playlist with exactly 100 tracks (i.e., songs), numbered 1 to 100. To go to another track, there are two buttons you can press: (1) “Next”, which will take you to the next track in… Read More »

Programming and probability: Sampling from a discrete distribution over an infinite set

By | September 2, 2018

This post is an introductory tutorial which presents a simple algorithm for sampling from a discrete probability distribution $p(k)$ defined over a countably infinite set. We also show how to use higher-order programming to implement the algorithm in a modular and reusable way, and how to amortize the cost of sampling using memoization. Introduction and… Read More »

Metropolis-Hastings with Gaussian drift proposal on bounded support

By | February 13, 2016

Professor Darren Wilkinson has an excellent blog post on a common implementation issue that arises when the standard random-walk Metropolis Hastings algorithm, with a Gaussian proposal, is modified to sample from a target distribution $p(x)$ where $$\text{supp}(p) = \lbrace x : p(x) > 0 \rbrace = (0, \infty).$$ In this blog post, we are going to briefly review the… Read More »