There are n strings in a bag. In one pass, you randomly pick one end of a string and then one more string.

Then you tie these two ends together and put the resulting string back into the bag.

Then you do another pass and so on. The game ends, when there are no loose ends remaining in the bag.

What is the probability that there will be exactly $t$ loops at the end?

  • $\begingroup$ Can the "one more string" in the first pass be the other end of the same string? (Otherwise the problem is trivial heh) $\endgroup$ – Hackiisan Sep 23 '15 at 8:21
  • $\begingroup$ Yes. it can be the same end. $\endgroup$ – rents Sep 23 '15 at 8:31
  • $\begingroup$ Just a thought, there will atleast one loop at the end. If we think for N=1,2... there should/might be a pattern. But not sure how I can apply this for the probability of getting t loops. $\endgroup$ – rents Sep 23 '15 at 8:34
  • $\begingroup$ I don't understand why there should be at least one loop at the end. Suppose $n=2$. Name the ends $a,b,c,d$ where one string contains $a,b$ and a different string contains $c,d$. Then picking $a,c$ will result in no loops. $\endgroup$ – Lawrence Sep 23 '15 at 9:06
  • $\begingroup$ @Lawrence you then end up with string $b,d$. when you do another pass, you're guaranteed to join $b$ and $d$ to form a loop. $\endgroup$ – Miff Sep 23 '15 at 9:09

You can certainly get a recurrence relationship, I can't immediately see how to get an explicit formula from it.

Let $P_n(t)$ be the probability of making $t$ loops from $n$ strings. It's clear that $P_0(t)=P_n(0)=0$ for $t>0, n>0$, and $P_0(0)=1$.

After picking the end of the first string, there are $2n-1$ ends to select from, of which one will form a loop, and the remainder will join two strings to effectively become one, so $$P_n(t)=\frac{1}{2n-1}P_{n-1}(t-1)+\frac{2n-2}{2n-1}P_{n-1}(t)$$

  • $\begingroup$ Not sure if it's necessary to add but you can also say that $P_n(t) = 0$ when $t > n$ $\endgroup$ – Ivo Beckers Sep 23 '15 at 14:42
  • $\begingroup$ @IvoBeckers It is necessary for the recurrence relationship. Note that, $P_n(n)=$ $\frac{1}{2n-1}P_{n-1}(n-1)$ $+$ $ \frac{2n-2}{2n-1}P_{n-1}(n)$ We need it for the $P_{n-1}(n)$ term. $\endgroup$ – Rohcana Sep 23 '15 at 17:15
  • $\begingroup$ @Anachor, thinking about it I don't think it is really necessary but it does make it simpler. because even though you might think it's needed for the $P_{n-1}(t)$ part, when you extend that further it will always lead to the "$P_0(t)=0$ for $t>0$"-case because every recursion will have $t>n$. $\endgroup$ – Ivo Beckers Sep 23 '15 at 20:02

Here's a partial answer.

If we count tied-together strings as a single string, each pass reduces the number of strings by 1. The probability of not picking the same string on the $(n-k)$-th pass is $\frac{2k-2}{2k-1}$. Otherwise, it is $\frac{1}{2k-1}$. Therefore, the probability of getting only one loop is:

$$P[t=1] = \frac{2^{n-1}(n-1)!}{(2n-1)!!}$$

To get $t-1$ more loops, we need to divide $P[t=1]$ by any $t-1$ numerators out of the $n-1$ numerators we have (thus replacing the $2k-2$ on the $(n-k)$-th pass with a $1$). There are $\binom{n-1}{t-1}$ ways to achieve this, and each of them are equally likely. We therefore have:

$$ \begin{align*} P[t] &= \frac{2^{n-1}(n-1)!}{(2n-1)!!}\cdot\sum_{j=1}^{\binom{n-1}{t-1}} \frac{1}{2^{t-1} S_j(n-1,t-1)} \\ &= \frac{2^{n-t}(n-1)!}{(2n-1)!!}\cdot\sum_{j=1}^{\binom{n-1}{t-1}} \frac{1}{S_j(n-1,t-1)} \\ &= \frac{2^{n-t}}{(2n-1)!!} \cdot \sum_{j=1}^{\binom{n-1}{n-t}}{ S_j(n-1,n-t)} \end{align*} $$

where $S_j(n,k)$ is the product of some distinct combination of $k$ numbers between $1$ and $n$, inclusive. For the case of $t=2$, the sum on the second line is the $n-1$-th harmonic number. I don't know how to reduce this for higher values of $t$ (hence the partial answer).

Edit: Instead of dividing out the $2k-2$s we don't want, we can directly multiply the appropriate numerators together. This gives us the equivalent (but slightly simplified) expression on the third line I appended to the equation block.

  • $\begingroup$ Shouldn't the probability of not picking the same string on kth pass be: 2N-2K-2/2N-2k-1. Because there will be (N-K) strings left at that point $\endgroup$ – rents Oct 7 '15 at 17:48
  • $\begingroup$ Ah yes, I meant to say $(n-k)$-th pass, thanks. I have corrected the answer now. $\endgroup$ – Hackiisan Oct 7 '15 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.