TYI 31 – Rados Radoicic’s Rope Problem

 

Ropemaker (source)

Rados Radoicic wrote me:

“Several years back, I heard the following puzzle that turns out to be rather ‘classical’:

“There are N ropes in a bag. In each step, two rope ends are picked uniformly at random, tied together and put back into a bag. The process is repeated until there are no free ends. What is the expected number of loops at the end of the process?”

Before moving on, please try to answer this question.

Let me go on with Rados’ email:

“Upon hearing this puzzle, I came up with and have been wondering (for years now) about the following “natural” variation:

“What if at each step, each end is picked with the probability proportional to the length of its rope?”

I made no epsilon-worthy progress on this problem since then. A properly-trained probabilist (unlike me) might find it easy, but somehow my gut feeling tells me it may be very interesting and not simple at all.”

The challenges are to test yourself on the first question and try to answer the second. No polls this time; comments and thoughts on both versions are welcome.

Advertisements
This entry was posted in Combinatorics, Probability, Test your intuition and tagged , . Bookmark the permalink.

7 Responses to TYI 31 – Rados Radoicic’s Rope Problem

  1. Andrey Kolmogorov says:

    I think it should be 1 + 1/3 + … + 1/(2n – 1).

    How? Let L = L_1 + … L_n denote the number of loops. L_i is an indicator that denotes if a loop was generated in the ith round. There are 2i ends left and after choosing one end, only another specific end is going to give us a loop. So probability is 1/(2i – 1). This completes the argument.

  2. Asvin G. says:

    For the first problem, let us denote f(n) by the expected number of loops you end up with if you started with n ropes. Then it is easy to build the recurrence relation: f(n) = 1/(2n-1) + f(n-1) because at each step:
    You either first pick one end and then you have a probability 1/(2n-1) to pick the other end of the same rope at which point you have one new loop and n-1 ropes (giving a contribution of (f(n-1)+1)/(2n-1) )

    OR you pick some other rope end at which point you have no new loops and n-1 ropes (giving a contribution of f(n-1)(1- 1/(2n-1)).

    Now how about this approach for the second problem:

    Let f(n_1,n_2,n_3…) denote the expected number of loops when you begin with n_k ropes of length k. So we want to find f(n,0,0,0…). We can run the same kind of recurrence again.

    The probability of picking a end of a rope of length k is kn_k/(n_1 + 2n_2 + 3n_3 …) and we can just go through the cases as before. I think you will end up with a linear recurrence relation…

  3. James Martin says:

    Very nice question. I believe that in Rados’s second model, the number of loops at the end is typically on the order of N^{1/3}. It’s a sort of random graph question in disguise, and there is an interesting “self-organised criticality” aspect to it.

    Consider a graph with vertex set [N], starting with no edges. Now add edges one by one – each time you add, choose the two endpoints independently and uniformly from [N]. Looking at the connected components of the graph gives a “multiplicative coalescent”: if you consider two components with sizes A and B, the number of ways of choosing endpoints of an edge which would join them together is 2AB, so components are coalescing with probability proportional to the product of their sizes. (These coalescences correspond to joining of two strings in Rados’s model.)

    Such an “Erdos-Renyi process” has several interesting “phases” for large N. Let M be the number of edges added. If M~cN for some c1/2, then we have the “supercritical phase” – there is one “giant component” whose size is on the order of N, and the rest of the components are small (order log(N) again). Suppose c=1/2, or in fact more precisely suppose that M=N/2+O(N^{2/3}). Then we are in the “critical window”: the largest component is on the order of N^{2/3}, and the same is true of the 2nd-largest, 3rd-largest, etc.

    To arrive at Rados’s model, we need one more element. The number of ways of choosing an edge with both endpoints WITHIN a currently existing component of size A is A^2. If this happens, suppose we agree to “freeze” the component; it is never going to be allowed to connect to any other component. (This corresponds to joining the two ends of a string into a loop).

    This is closely related to the “mean-field frozen percolation” models considered e.g. by Balazs Rath at https://arxiv.org/abs/0812.2750 . One sees a sort of “self-organised criticality”. In the subcritical phase, not much is different from the Erdos-Renyi process: the components are small and it’s very rare to see an edge within an existing component. Once we reach the critical point, suddenly things are different. A giant component is trying to emerge, but every time a component gets big, it gets high probability of getting hit with an internal edge, which “freezes” it. The critical window, which used to be a fleeting moment, now becomes a semi-permanent state. The coalescence creating bigger components is counteracted by the freezing which removes components when they get too big.

    In Balazs’s model, the freezing is done proportional the size of a component, rather than to the square of the size. The precise mechanics of Rados’s model are rather nice: the probability of freezing a component (i.e. looping a string) of size aN^{2/3} is on the same order as the probability of merging two components (i.e. joining two strings) of size aN^{2/3} and bN^{2/3}. Then the “self-organised” state should be precisely in the critical window phase where the largest component is of size order N^{2/3}. A typical frozen component (loop) is then of size of order N^{2/3}. (That is non-obvious, but I think sound, though the explanation is a bit long to include.) By the end of the process, the number of frozen components (loops) should then be like N^{1/3}. (Quite a few things to check here!! perhaps not easy!!…)

    To look for further related results by by Balazs, Balint Toth, and others, you can search also for things like “mean-field forest-fire model” and “multiplicative coalescent with deletion”.

  4. John Sullivan says:

    I’d also like to know the probability that the loops are knotted!

  5. ameyerowitz says:

    Let H(k) be the sum of the first k unit fractions. The recurrence mentioned above for the simple problem shows that the answer equals H(2n)-H(n)/2 although it does not derive it in that form. I wonder if there is a natural approach which does arrive at that formula.

  6. Gil Kalai says:

    Many thanks for all the comments and especially for James Martin’s definite insights on Rados’ problem.

    Rados wrote on the first problem “Of course, the linearity of expectation argument gives 1 + 1/3 + 1/5 + … + 1/(2n-1)”.

    For his version he wrote: “Sometime ago, a student of mine made a simulation that showed that the expected number of loops fits n^{\alpha} very nicely, where \alpha is a nice fraction, that I fail to recall, unfortunately.” In view of James’s answer the nice fraction is 1/3.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s