While considering solving the following standard question in probability in an alternative way, I get stuck with a recurrence relation. The problem is as follows:
A bag contains $N$ ropes. We pick up two randomly chosen ends and tie them together until no untied ropes are left. The problem is to find the expected number of loops.
Now there is a standard and neat solution to the above problem. I tried to solve it instead by first finding the probability $p_{k,l}$ of getting $l$ loops at the $k$th stage, where both $k$ and $l$ can take the values $0,1,2,...N$. Further, it follows that at any time $l\le k$. Since with $N$ loops the probability of addition of a loop at the first step is ${N}/{\binom{2N}{2}}$, and at the the kth stage we have effectively $N-k$ ropes (possibly some consisting of more than one of the original ropes tied), we have the following recurrence relation:
$$p_{k,l}=p_{k-1,l} \cdot \text{Prob(No loop is added at $k$th stage)} +p_{k-1,l-1}\cdot\text{Prob(a loop is added at $k$th stage)}.$$
This above gives us $$p_{k,l}=p_{k-1,l} \frac{2N-2k-2}{2N-2k-1} + p_{k-1,l-1} \frac{1}{2N-2k-1}$$
Now, with the base conditions $p_{1,1}=\frac{1}{2N-1}$ and $p_{1,o}=\frac{2N-2}{2N-1}$, how can we find $p_{N,l}$ in terms of $N$ and $l$?
One sentence. Another sentence.and not like this:One sentence.Another sentence.) – ShreevatsaR Dec 20 '17 at 18:59