### Solving IMO 1989 #6 using Probability and Expectation

IMO 1989 #6: A permutation $$\{x_1, x_2, \ldots , x_m\}$$ of the set $$\{1, 2, \ldots , 2n\}$$, where $$n$$ is a positive integer, is said to have property $$P$$ if $$| x_i - x_{i+1} | = n$$ for at least one $$i$$ in $$\{1, 2, ... , 2n-1\}$$. Show that for each $$n$$ there are more permutations with property $$P$$ than without.

Solution: We first observe that the expected number of pairs $$\{i, i+1\}$$ for which $$| x_i - x_{i+1} | = n$$ is $$E = 1$$. To see this note if $$j$$, $$1 \leq j \leq n$$, appears in position $$1$$ or $$2n$$ it's adjacent to one number, otherwise two. Thus the probability it's adjacent to its partner $$j+n$$ in a random permutation is \eqalign{ e_j &= \frac{2}{2n}\cdot \frac{1}{2n-1} + \frac{2n-2}{2n}\cdot \frac{2}{2n-1} \\ &= \frac{2(2n-1)}{2n(2n-1)} \\ &= \frac{1}{n}. } By linearity of expectation we overall have the expected number of $$j$$ adjacent to its partner $$j+n$$ is $$\sum_{j=1}^{n} e_j = n\cdot\frac{1}{n} = 1$$.

More is true. By the same argument, if we remove any partner pair $$\{j,j+n\}$$, the expected number of partner pairs in a random permutation of the remaining integers is still 1. This is the critical observation.

Conditional on the partner pair $$\{j,j+n\}$$ appearing in a random permutation, what is the expected number of partner pairs $$e$$? Observe that if $$n>1$$ it must be less than 2, since as before the expected number of partner pairs ignoring $$\{j,j+n\}$$ is 1, and the probability the $$\{j,j+n\}$$ pair where they appear has separated another partner pair is greater than 0.

Putting this together, if $$n=1$$ the property $$P$$ obviously holds. For $$n>1$$, note the expected number of partner pairs $$E = p\cdot e$$, where $$p$$ is the probability that a random permutation has property $$P$$ and $$e$$ is as before. But we already know $$E=1$$, and by the previous argument if $$n>1$$ we have $$e<2$$, hence $$1 = p\cdot e < 2p$$ and we conclude $$p > \frac{1}{2}$$.

### A Bayes' Solution to Monty Hall

For any problem involving conditional probabilities one of your greatest allies is Bayes' Theorem. Bayes' Theorem says that for two events A and B, the probability of A given B is related to the probability of B given A in a specific way.

Standard notation:

probability of A given B is written $$\Pr(A \mid B)$$
probability of B is written $$\Pr(B)$$

Bayes' Theorem:

Using the notation above, Bayes' Theorem can be written: $\Pr(A \mid B) = \frac{\Pr(B \mid A)\times \Pr(A)}{\Pr(B)}$Let's apply Bayes' Theorem to the Monty Hall problem. If you recall, we're told that behind three doors there are two goats and one car, all randomly placed. We initially choose a door, and then Monty, who knows what's behind the doors, always shows us a goat behind one of the remaining doors. He can always do this as there are two goats; if we chose the car initially, Monty picks one of the two doors with a goat behind it at random.

Assume we pick Door 1 and then Monty sho…

### Notes on Setting up a Titan V under Ubuntu 17.04

I recently purchased a Titan V GPU to use for machine and deep learning, and in the process of installing the latest Nvidia driver's hosed my Ubuntu 16.04 install. I was overdue for a fresh install of Linux, anyway, so I decided to upgrade some of my drives at the same time. Here are some of my notes for the process I went through to get the Titan V working perfectly with TensorFlow 1.5 under Ubuntu 17.04.

Old install:
Ubuntu 16.04
EVGA GeForce GTX Titan SuperClocked 6GB
2TB Seagate NAS HDD

New install:
Ubuntu 17.04
Titan V 12GB
/ partition on a 250GB Samsung 840 Pro SSD (had an extra around)
/home partition on a new 1TB Crucial MX500 SSD
New WD Blue 4TB HDD