Sphagetti Breakfast
Source: Very standard problem in Quant interviews (Taken from quantnet, xkcd forums)
Problem:
A bowl of spaghetti contains n strands. Thor picks two ends at random and joins them together. He does this until no ends remain.
What is the
a) expected number of spaghetti loops in the bowl?
b) expected average length of the loops? (in strands)
c) expected number of k-hoops? ( a k-hoop is a loop made from k strands)
Problem:
A bowl of spaghetti contains n strands. Thor picks two ends at random and joins them together. He does this until no ends remain.
What is the
a) expected number of spaghetti loops in the bowl?
b) expected average length of the loops? (in strands)
c) expected number of k-hoops? ( a k-hoop is a loop made from k strands)
Solution:
Highlight the part between the * symbols for the answer.
* a) Expected number of loops = 1 + 1/3 + 1/5 + ... + 1/(2n-1) (the sum of the first n odd reciprocals, about (ln n)/2 + ln 2 + gamma/2). When m strands (2m ends) remain, pick any end: the other end you join it to is uniformly one of the 2m - 1 remaining ends, and exactly one of those closes a loop. So a loop is created with probability 1/(2m-1) at that step, and summing the indicators over m = n, n-1, ..., 1 gives the answer (NG's recurrence; Rudradev Basak's generating function F(x) = prod_{i=0}^{n-1} (x + 2i)/(2i+1) encodes the full distribution, and F'(1) gives the same sum).
b) Expected average loop length = n / (expected number of loops), i.e. n / (1 + 1/3 + ... + 1/(2n-1)); the exact E[n/L] is n times the integral of F(x)/x from 0 to 1 with F as above (Rudradev's formula).
c) Expected number of k-hoops = C(n,k) * (k-1)! * 2^(k-1) * (2n-2k-1)!! / (2n-1)!!. Reason: fix k strands; their 2k ends must pair only among themselves into a single cycle: (k-1)! * 2^(k-1) of the (2k-1)!! pairings do this, and the remaining 2n - 2k ends pair arbitrarily. (Equivalent to avinash's n*P_k/k formula.) Check: k=1 gives n/(2n-1), and summing over k reproduces part (a).
Solution by NG, Rudradev Basak and avinash from the comments. *
Fi(k) = probability of k loops after i steps
ReplyDeleteFi(0) = π [2(n-i)/{2(n-i)+1}]
Fi(k)= [F(i-1)(k-1)] *[2(n-i)/{2(n-i)+1}] + [F(i-1)(k)] * [1/ {2(n-i) + 1}]
..
Solve the above recursion to obtain the solution for part (a)
Still figuring out a way for rest parts
Here is solution for the first part of puzzle. Rest I've not been able to solve yet.
ReplyDeleteDenote f(k) as a random variable denoting number of loops formed when there are K acyclic strands left.
Now f(k) = p * ( 1 + f(k-1) ) + (1-p) * f(k-1) where p is probability of selecting both ends of the same strand.
p is k / ( 2k * (2k-1) / 2) = 1 / (2k-1)
So f(k) = 1/(2k-1) + f(k-1)
Taking expectation,
E( f(k) ) = 1/(2k-1) + E( f(k-1) )
We need E( f(n) ) which is just : 1/1 + 1/3 + .... 1/ (2n-1)
For the second part, what we need is n*(Summation P(k)*(1/k)) where P(k) is the probability that there are exactly k loops. Lets try to define a generating function for this.
ReplyDeleteNote that at the (i)th stage there are i open strands and 2i open ends. There is a 1/(2i-1) probability of increasing the number of loops by choosing two ends of the same strand, and (2i-2)/(2i-1) probability of not increasing the number of loops. Hence this corresponds to the expression (x + (2i-2))/(2i-1).
Therefore the entire generating function for the number of loops become F(x) = ( (x+(2n-2))*(x+(2n-4))*...*(x+2)*(x+0) )/( (2n-1)*(2n-3)*...*(3)*(1) )
The coefficient of x^k in the above gives us P(k)
Note that to obtain the answer of the first part (Summation P(k)*k), we can differentiate F(x), and put in x=1. Derivative of F(x) is F(x)/(x+2n-2) + F(x)/(x+2n-4) + ... + F(x)/(x+2) + F(x)/(x+0). F(1)=1. So the above expression becomes 1/(2n-1) + 1/(2n-3) + ... + 1/3 + 1/1.
To obtain the answer of the second part, we need to integrate F(x), but after first dividing by x, and then plugging in x=1. However I am not able to find a closed form at the moment.
Two small corrections.
ReplyDeleteThere are i open strands and 2i open loops at the (n-i)th stage
And for the second part, we also need to multiply by n at the end. (Ans = n*(Integral of F(x)/x at 1))
So the most I can simplify the answer for second part is :
ReplyDeleten * ( 1/n + S(1)/(n-1) + S(2)/(n-2) ... + S(n-1)/1 )/((2n-1)*(2n-3)*...*(3)*(1))
where S(k) is Sum of (n choose k) products of k terms each taken from {2,4,..,2n-2}
Eg. For n=5, S(3) = 2*4*6 + 2*4*8 + 2*6*8 + 4*6*8
Consider the random variable Xi=1/k if i'th strand is present in a loop of k strands for k={1,2,..n}.
ReplyDeleteso Xi= 1/k with prob Pk(say)
E(no of loops)=n*E(Xi) as all the strands are identically distrib.
a) First to calculate Pk let us look at I(n)-> Total no of ways of forming loops with n strands = [(2n,2)*(2n-2,2)....*(2,2)]/n!
=[2n!]/[(2^n)*n!]
b) Pk
No.of ways of forming a k-hoop is (n-1,k-1)*(k-1)!*2^(k-1)} *I(n-k))
hence Pk=above expression/I(n).
a) E(no.of loops)=n*exp(Xi)
=n*sum(Pk/K) sum for k over{1,2,3..n}
c) E(no.of k-hoops) can be computed by slightly altering Xi=1/k if it is part of a k-hoop or else 0.
so E(no.of hoops)=n*Pk/k
where as given earlier
Pk=Perm(n-1,k-1)*2^(k-1)*I(n-k)/I(n).
Comments: Closed form in 'c' but in 'a' trying to see if i can get a closed form.And numerically 'a' is matching with NG's solution.
'b' - still figuring out..
If we simplify
ReplyDeleteE(no.of k hoops)=1/2K)*(1+1/(2*n-1))*(1+1/(2*n-3))+(1+1/(2*n-5))+......(1+1/(2*n-2*k+1)).
Disclaimer: I haven't verified all the solutions above, but since this seems to be just an instantiation of a well known problem in Discrete Math/Theoretical CS, I though I would point this out.
ReplyDeleteThis seems to me to be a simplified version of what is called the Configuration Model in the theory of Random Regular Graphs.
Consider each strand as a "vertex" consisting of a set of two "nodes". The process then can be described as randomly pairing these 2n nodes (2 for each strand or "vertex") into n pairs, and assuming there is an "edge" between two "vertices" if a node from paired with a node from the other. Thus, self loops are allowed in this hypergraph.
Now notice that a k-length loop in the problem just corresponds to a length k cycle in the random hypergraph constructed above. The expected number of length $k$ cycles in these hypergraphs (even when each vertex has any number $d$ of nodes) is a standard calculation in this setting, and is done roughly in the way Avinash suggested above. We call a "positioning" of a k-cycle to be a collection of paired nodes which project to some k-cycle on the vertices of the hypergraph. The number of possible "positionings" in the hypergraph of an oriented k-cycle with a distinguished first vertex is 2kN_k = n_k * 2^k, where n_k = n(n-1)...(n-k+1), and N_k is the number of positionings without a distinguished first vertex and without considering orientation. This is because you can chose the vertices in n_k ways, and then select the nodes that get paired in each direction for each of the k vertices in 2^k ways, and then you have to divide by 2k to take care of the multiple counting of the same cycle due to the orientation and the distinguished first vertices.
Now the probability p_k that these 2k nodes are actually matched as required by such a "positioning" is p_k = (2n-2k)!!/(2n)!!, where (2l)!! is the number of pairings of 2l objects, given by (2l)!! = (2l)!/(2^l l!).
Thus, the expectation of $X_k$, the number of $k$-hoops is $E[X_k] = p_k*N_k$ and expectation of the the number of hoops is $\sum_{k=1}^n p_k N_k$. The same calculation can be done if each strand has "degree" $d > 2$, and is very useful in random graph theory. A reference is the chapter on random regular graphs in the book Random Graphs by Svante Janson et al.
However, I am not sure of the vanilla calculations above apply to part (b). The reason is that we now have a very different beast: the expectation of the inverse of random variables, and I can't think of anything beyond the generating function method proposed by Rudradev above.
In fact, I am not immediately sure how to do something better even in the asymptotic (n->\infty) setting. In this case, it can be shown that for any fixed $k$, the distribution of (X_1, X_2, .....X_k) converges to the distribution of independent Poisson random variables (Z_1, Z_2, ....Z_k) where Z_i ~ Po(1/2i). However, we would need to handle non-constant k to solve b and so this does not seem to be of much help.
At each step, we either loop an existing strand or join two strands together. So, 1 strand goes out of the picture at each iteration. Or think of it in this way; after step i, you are left with only N-i strands. Now, probablity that you make a loop at step i, is 1/(N-i+1) where i varies from 1 to N. Summing this up gives us logN approximately. Just to be clear, I have used the logic of indicator random variables.
ReplyDeleteThe recursion skeleton is right, but NG's expectation-first version below is much easier to solve than tracking the full distribution: with m strands left, the two ends you pick belong to the same strand with probability 1/(2m-1), so E[loops] = sum over m of 1/(2m-1) = 1 + 1/3 + ... + 1/(2n-1). (replied using AI)
ReplyDeleteCorrect - clean solution. With k strands remaining, pick an end uniformly: 1 of the other 2k-1 ends is its own partner, so a loop closes with probability 1/(2k-1). Expected number of loops = 1 + 1/3 + ... + 1/(2n-1) ~ (1/2)(ln n + gamma + 2 ln 2). (replied using AI)
ReplyDeleteThanks for the corrections - strand/end bookkeeping matters here. For part (b) though, watch out: E[average loop length] is not n/E[number of loops] - the expectation of the ratio is not the ratio of expectations. avinash's per-strand approach below handles (b) and (c) more directly. (replied using AI)
ReplyDeleteThat is a heroic expansion - elementary symmetric sums over the even numbers. It is correct in shape but painful; compare avinash's closed product below, which compresses the same content via the pairing count I(n) = (2n)!/(2^n n!). (replied using AI)
ReplyDeleteThis is the right machinery. The pairing count I(n) = (2n)!/(2^n n!) is exact (that is the number of perfect matchings of 2n ends), and your per-strand indicator X_i converts loop statistics into expectations by linearity. E[number of k-hoops] = n * P_k / k... with P_k as you wrote - the counting is sound. (replied using AI)
ReplyDeleteNice closed form - a finite product of (1 + 1/(2m-1)) terms. Spot-checks against small cases work out. So the full story: E[loops] = sum of odd reciprocals, E[k-hoops] = your product, and the expected average length follows from E[loops] and these jointly. (replied using AI)
ReplyDeleteRight method (indicators), wrong denominator: with m strands left there are 2m ends, and after picking one end, exactly 1 of the remaining 2m-1 ends closes a loop - so P(loop at that step) = 1/(2m-1), not 1/m. Summing 1/(2m-1) over m = 1..n gives (1/2)(ln n) + (gamma/2) + ln 2 + o(1) - about half of your log N. (replied using AI)
ReplyDelete