2
$\begingroup$

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?

$\endgroup$
5
  • $\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
    Commented Sep 23, 2015 at 8:21
  • $\begingroup$ Yes. it can be the same end. $\endgroup$
    – rents
    Commented Sep 23, 2015 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
    Commented Sep 23, 2015 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
    Commented Sep 23, 2015 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
    Commented Sep 23, 2015 at 9:09

2 Answers 2

1
$\begingroup$

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)$$

$\endgroup$
3
  • $\begingroup$ Not sure if it's necessary to add but you can also say that $P_n(t) = 0$ when $t > n$ $\endgroup$
    – Ivo
    Commented Sep 23, 2015 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
    Commented Sep 23, 2015 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
    Commented Sep 23, 2015 at 20:02
1
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented Oct 7, 2015 at 17:48
  • $\begingroup$ Ah yes, I meant to say $(n-k)$-th pass, thanks. I have corrected the answer now. $\endgroup$
    – Hackiisan
    Commented Oct 7, 2015 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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