Category Probability

Expectation of minimum of n i.i.d. uniform random variables

Let  be independent uniform random variables from , and consider the random variable . Computing the expectation is a routine computation: . However, there a slick way of computing this expectation. Let be another uniform random variable in . Consider the probability . On the one hand due to symmetry, it is equal to , on […]

Fair allocation of a pizza

An observation on edge densities of the union of isomorphic copies of a fixed graph

Consider a fixed graph with vertices and edges respectively. Assume that is balanced which means that the maximum edge density among all possible subgraphs of is achieved from $H$. Take two copies of , call them and create a new graph . In case the two copies are edge disjoint then the edge density of […]

Giant component with Depth First Search

I just finished reading a short paper of Michael Krivelevich and Benny Sudakov, two leading experts in probabilistic combinatorics, which appeared in Arxiv about a month ago [1]. It is a simple proof of the classical result that the random binomial graph exhibits a phase transition around . When then the largest component has size […]

The Ballot Theorem

Today’s post is going to be about politics. Consider an election where there are two candidates, call them A and B, who receive votes respectively, and let us assume that . Assume that all possible “trajectories” are equally likely. What is the probability that candidate B is ahead of A throughout the vote counting procedure? […]

Martingales & Coins: Waiting for Heads-Tails-Heads

Consider the following simple problem: let be a sequence of independent fair coin tosses. How many times do we have to toss the coin in expectation in order to observe the sequence HTH (H stands for heads and T for tails)? We will answer this question here with three different ways. The first way is […]

Humans and Randomness

To be honest, this is an experiment I had though of as being an interesting one but never went into the trouble of doing. Dan Meyer however made it happen and thanks to him we can see that a human despite its good effort to imitate a coin cannot do that well. Why though? Subconscious? For […]