Category Archives: Probability

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 »

Notating “conditional” probabilities

By | February 27, 2018

Let $p$ denote a probability density with support $x \in \mathcal{X}$, and let $\theta \in \mathbf{T}$ parametrize $p$. It is common in the literature to express this situation using the notation $p(x\mid \theta)$. However, this “conditional” notation using the vertical bar (or mid in LaTeX) is often used ambiguously. Notation with the conditional symbol $p(x… Read More »

A pair of probability problems

By | January 15, 2018

Let $w = (w_1,w_2,\dots)$ be an infinite sequence of nonnegative numbers that sums to unity. Consider the function $$f_w(u) = \sum_{j=1}^{\infty}\mathbf{I}(u < w_j).$$ Prove that $f_w$ is a probability density in $u > 0$. Describe a simulation technique for generating a random variable $U \sim f_w(u)$.

A thought experiment with the Bayesian posterior predictive distribution

By | January 29, 2017

Let $\pi(\theta)$ be a prior for parameter $\Theta$, and $p(x|\theta)$ a likelihood which generates an exchangeable sequence of random variables $(X_1,X_2,X_3\dots)$. Given a set of observations $D := \lbrace X_0=x_0, X_1=x_1, \dots, X_{N-1}=x_{N-1}\rbrace$, the posterior predictive distribution for the next random variable in the sequence $X_N$ is defined as $$p(X_{N}=s | D) = \int p(X_{N}=s… Read More »