KindiakMath

Several Probability Puzzles

Problem 1. Let X_1,\dots, X_n \sim \mathcal U(0, 1) be i.i.d.. Let g : [0,1]^n \to [0,1]^n denote the permutation

g(x_1,\dots, x_n) = (y_1,\dots, y_n)

such that y_1 \leq \dots \leq y_n. Denoting (Y_1,\dots, Y_n) = g(X_1, \dots, X_n), evaluate \mathbb E[Y_i] for each i.

(Click for Solution)

Solution. Since \mathbb P (X_i = X_j) = 0 whenever i \neq j, we can assume Y_1 < \dots < Y_n.

We will obtain the distribution of Y_i. Fix x \in [0, 1]. Let V_x \sim \mathrm{Bin}(n-1, x) denote the number of sample points that are less than x, which follows a binomial distribution. It follows that \{ Y_i = x \} = \{ V_x = i-1 \}, so that

\displaystyle f_{Y_i} (x) = \mathbb P(V_x = i-1) = {n-1 \choose i-1} x^{i-1} (1-x)^{n-i}.

Hence, by recalling the properties of the Beta distribution,

\begin{aligned} \mathbb E[Y_i] &= \int_0^1 x \cdot f_{Y_i} (x)\, \mathrm dx \\ &= \int_0^1 x \cdot {n-1 \choose i-1} x^{i-1} (1-x)^{n-i}\, \mathrm dx \\ &= \int_0^1 {n-1 \choose i-1} x^i (1-x)^{n-i}\, \mathrm dx \\ &= {n-1 \choose i-1} \int_0^1 x^i (1-x)^{n-i}\, \mathrm dx \\ &= \frac{\Gamma(n)}{\Gamma(i) \cdot \Gamma(n-i+1)} \cdot \frac{\Gamma(i+1) \cdot \Gamma(n-i+1)}{ \Gamma(n+1) } \\ &= \frac{\Gamma(n)}{\Gamma(i) \cdot \Gamma(n-i+1)} \cdot \frac{i \cdot \Gamma(i) \cdot \Gamma(n-i+1)}{ (n+1) \cdot \Gamma(n) } = \frac{i}{n+1}. \end{aligned}

Problem 2. Calculate the average number of rolls of a fair six-sided die that you need to roll in order for the sum of all rolls to be a multiple of 6.

(Click for Solution)

Solution. Let \xi_i denote the i-th roll and X_n := \sum_{i=1}^n \xi_i denote the sum of the first n rolls. Define the stopping time N by

$latex\displaystyle N := \inf_{n \in \mathbb N} \{6 \mid X_n\}.$

We claim that N \sim \mathrm{Geom}(1/6). For any n \in \mathbb N,

\{N = n\} = \{6 \nmid X_1, \dots, 6 \nmid X_{n-1}, 6 \mid X_n\}.

For each i,

\{ 6 \nmid X_{i-1}, 6 \mid X_i\} = \{ \xi_i = X_i - X_{i-1} \},

which is one of the six possible numbers with equal probability:

\mathbb P(N = n) = \mathbb P(\{6 \nmid X_1, \dots, 6 \nmid X_{n-1}, 6 \mid X_n\}) = (5/6)^{n-1} \cdot (1/6).

Therefore, N \sim \mathrm{Geom}(1/6) so that \mathbb E[N] = 1/(1/6) = 6 as well.

Problem 3. What is the probability of getting an odd number of heads out of n independent flips of a fair coin?

(Click for Solution)

Solution. Let X \sim \mathrm{Bin}(n, 1/2) denote the number of heads out of n independent flips of a fair coin. Then the required probability is

\begin{aligned} p_{\text{odd}} &= \sum_{k\, \text{odd}}^{n} \mathbb P(X = k) = \sum_{ k\, \text{odd} }^{ n } {n \choose k} \frac 1{2^n}. \end{aligned}

Using properties involving the binomial coefficient,

\begin{aligned} 0 = (1+(-1))^n &= \sum_{k=0}^n {n \choose k} (-1)^k \\ &= \sum_{k\, \text{odd}}^n {n \choose k} (-1)^k + \sum_{k\, \text{even}}^n {n \choose k} (-1)^k \\ &= \sum_{k\, \text{odd}}^n {n \choose k} \cdot (-1) + \sum_{k\, \text{even}}^n {n \choose k} \cdot 1 \\ &= -\sum_{k\, \text{odd}}^n {n \choose k} + \sum_{k\, \text{even}}^n {n \choose k}. \end{aligned}

Therefore,

\displaystyle \sum_{k\, \text{odd}}^n {n \choose k} = \sum_{k\, \text{even}}^n {n \choose k}.

In particular,

\begin{aligned} p_{\text{even}} &= \sum_{ k\, \text{even} }^{ n } {n \choose k} \frac 1{2^n} = p_{\text{odd}}. \end{aligned}

Since p_{\text{odd}} + p_{\text{even}} = 1, we must have p_{\mathrm{odd}} = 1/2, as required.

Problem 4. Given X_1, X_2 \sim \mathcal U(0, 1), calculate \mathbb E[\min\{X_1,X_2\}].

(Click for Solution)

Solution. Denoting Y = \min\{X_1, X_2\}, we observe that

\displaystyle \mathbb P(Y > y) = \mathbb P(X_1 > y, X_2 > y) = \mathbb P(X_1 > y) \cdot \mathbb P(X_2 > y) = (1-y)^2.

Therefore, by the tail integral for expectation,

\begin{aligned} \mathbb E[Y] &= \int_0^1 \mathbb P(Y > y) \cdot \mathbb I_{[0, 1]}(y) \, \mathrm dy = \int_0^1 (1-y)^2\, \mathrm dy = \int_0^1 y^2\, \mathrm dy = 1/3. \end{aligned}

Problem 5. You’re the second-best player in a single-elimination tournament with 2^n players. Assume the brackets are randomly seeded, and the better player always wins each match. What is the probability you reach the finals?

(Click for Solution)

Solution. Each tournament will have n stages, and at stage i, there will be 2^{n+1-i} players. In order to reach the final stage, we need to be in a different “bracket” with the best player. At stage 1, there are two “brackets”, and each bracket has 2^{n-1} players. Therefore, the required probability is

\displaystyle \frac{2^{n-1}}{2^n - 1}.

Problem 6. Consider the sample space \{0, 1\} and the sequence of random variables X_0, X_1,\dots with the property that

\mathbb P(X_{n+1} = 1 \mid X_n = 1) = p,\quad \mathbb P(X_{n+1} = 0 \mid X_n = 0) = q.

Assuming that X_n has identical distribution, evaluate \mathbb P(X_n = 1).

(Click for Solution)

Solution. Denote \mathbb P(X_n = 1) = s. By the law of total probability,

\begin{aligned} \mathbb P(X_{n+1} = 1) &= \mathbb P(X_{n+1} = 1 \mid X_n = 1) \cdot \mathbb P(X_n = 1) \\ &\phantom{==} + \mathbb P(X_{n+1} = 1 \mid X_n = 0) \cdot \mathbb P(X_n = 0) \\ s &= p \cdot s + (1 - q) \cdot (1-s) \\ (1- p) \cdot s &= (1-q) - (1-q) \cdot s \\ (2 - p - q) \cdot s &= 1 - q \\ s &= \frac{1-q}{2-p-q}. \end{aligned}

—Joel Kindiak, 17 Oct 25, 1947H


Published by

joelkindiak

Leave a comment