Conditional probability and recursion

72 Views Asked by At

There are n unstable molecules in a row, $m_1,m_2,...,m_n$. One of the $n− 1$ pairs of neighbours, chosen at random, combines to form a stable dimer; this process continues until there remain $U_n$ isolated molecules.

a) Show that the probability that $m_1$ remains isolated is

$\sum_{k=0}^{n-1} \frac{(−1)^{k}}{k!}$

1

There are 1 best solutions below

0
On BEST ANSWER

There is probably a more elegant way to do this, but here is one method that works:

Let $p_n$ be the desired probability.

At each choice we imagine that the left most member of the pair is being specified.

On the first move you choose any of the first $n-1$ points as the left most element of your first pair. Equal probability, of course. Then we can ignore what happens to the right and we have a shorter block in the front. It follows that the probability satisfies the recursion $$p_n=\frac 1{n-1}\sum_{i=1}^{n-1}p_{i-1}=\frac 1{n-1}\sum_{i=0}^{n-2}p_i$$

where we use the convention $p_0=0$.

Easy to see that your expression matches this for small $n$. To see that it matches for all $n$ note that our expression quickly implies the recursion $$(n-1)p_n-(n-2)p_{n-1}=p_{n-2}$$ Letting $a_n=\sum_{k=0}^{n-1}\frac {(-1)^k}{k!}$ we now seek to prove that the $a_n$ satisfy the same recursion. We check that $$(n-1)a_n-(n-2)a_{n-2}=(n-1)\times \sum_{k=0}^{n-1}\frac {(-1)^k}{k!}-(n-2)\times \sum_{k=0}^{n-2}\frac {(-1)^k}{k!}$$$$=(n-1)\times \frac {(-1)^n}{(n-1)!}+\sum_{k=0}^{n-2}\frac {(-1)^k}{k!} =\frac {(-1)^{n}}{(n-2)!}+a_{n-3}$$ And, since $(-1)^{n-2}=(-1)^n$ we are done.