max min probability

Let \(X_1,X_2,X_3\) be random variables. Find \[\max \min \{\Pr[X_1>X_2], \Pr[X_2>X_3], \Pr[X_3 > X_1]\}\]

Claim. The maximal value is \(2/3\).

Let \(Y_{ij}\) denote the indicator random variable for \(X_i>X_j\). Clearly \(Y_{12}+Y_{23}+Y_{31} \leq 2\) so \(\mathop{\mathrm{\mathbb{E}}}[\sum Y_{i, i+1}]\leq 2\). This means that \(\max\min \mathop{\mathrm{\mathbb{E}}}[Y_{i,i+1}] \leq 2/3\). Of course \(\mathop{\mathrm{\mathbb{E}}}[Y_{ij}] = \Pr[X_i > X_j]\), so we cannot do better than \(2/3\).

We can achieve \(2/3\) as follows:

  • With probability \(1/3\), \(X_1<X_3<X_2\)
  • With probability \(1/3\), \(X_3<X_3<X_1\)
  • With probability \(1/3\), \(X_2<X_1<X_3\).

coin flip sum parity

Claim. Let \(X_i\) be independent Bernouli’s. Claim: the sum has odd parity with probability \(1/2\) iff one of the \(X_i\)’s has odd parity with probability \(1/2\).

Clearly if one of random variables, say \(X_n\), has an equal chance of being either parity, then the sum has equal chance of having either parity: the sum has some distribution before the addition of \(X_n\), and then adding \(X_n\) makes the parity even or odd with equal probability.

To show that one of the random variables must have \(p_i=1/2\) for the parity to be equally likely odd or even, we proceed by induction. Consider r.v.s that have odd parity with probability \(p_1,p_2\). For the parity of the sum to be equally likely odd or even we must have \[p_1p_2 + \bar{p_1}\bar{p_2} = p_1\bar{p_2} + \bar{p_1}p_2.\] But this implies \[p_1(p_2 - \bar{p_2}) = \bar{p_1} (p_2 - \bar{p_2}).\] In other words, either \(p_1 = \bar{p_1}\) or \(p_2 = \bar{p_2}\). Therefore we inductively find that adding independent random variables whose parity is not equally likely to be odd or even can never result in a random variable with equal probability of being even or odd.

weights

Claim. You have weights \(2^0,2^1, \ldots, 2^{n-1}\). You put them on a scale in some order such that the right pan of the scale is never heavier than the left. How many ways can this be done?

Proof.

Let \(f(n)\) denote the number of valid ways to place the weights. Say that the \(i\)-th weight placed is of weight \(2^0\). If \(i=1\) then the weight must be left pan or the right pan would be heavier. After placing this weight on the left pan though, we would be in essentially the same position but with \(n-1\) instead of \(n\), because \(2^0\) is so small compared to all the other weights that it can never affect which way the scales tip in the future, i.e. at any future state the scale will tip the same way even if we ignore the \(2^0\) weight. On the other hand, if we place the \(2^0\) weight at some position \(1<i\leq n\), then we can place it on the right or the left scale: either way is fine. In this situation it suffices to compute a method for placing the \(2^1,\ldots, 2^n\) weights, and then we can just insert this new weight.

Thus we derive the recurrence: \[f(n) = (2(n-1)+1)f(n-1) = (2n-1)f(n-1).\] We have as the base case \(f(0) = f(1) = 1\). We remark that \(f(n)\) is sometimes called the “double factorial” written \(n!!\).