This is really wonderful, thank you so much for sharing. I have been playing with your code.
The probability that their is only one loop is also very interesting. I worked out something, which feels like it is probably already well known, but not to me until now, for the simplest case.
In the simplest case is one tile. The orange lines are the “edging rule”. Pick one black point and connect it to another at random. This has a 1⁄13 chance of immediately creating a closed loop, meaning more than one loop total. Assuming it doesn’t do that, the next connection we make has 1⁄11 chance of failure. The one after 1⁄9. Etc.
So the total probability of having only one loop is the product: (12/13) (10/11) (8/9) (6/7) (4/5) (2/3), which can be written as 12!! / 13!! (!! double factorial). For a single tile this comes out at 35% ish. (35% chance of only one loop).
If we had a single shape with N sides we would get a probability of (N-2)!! / (N-1)!! .
The probability for a collection of tiles is, as you say, much harder. Each edge point might not uniformly couple to all other edge points because of the multi-stepping in between. Also loops can form that never go to the edge. So the overall probability is most likely less than (N-2)!!/(N-1)!! for N edge dots.
So, I’m actually thinking about something closer to this for “one loop”:
This is on a single square tile, with four ports of entry/exit. What I’ve done is doubled the rope in each connection, so there is one connection going from the top to the bottom and a different connection going from the bottom to the top. Then you tie off the end of each connection with the start of the connection just clockwise to it.
Some friends at MIT solved this problem for a maths class, and it turns out there’s a nice recurrence. Let P(n,ℓ) be the probability there are ℓ loops in a random knot on a single tile with 2n sides. Then
P(n,ℓ)=2n+1P(n−1,ℓ−1)+n−1n+1P(n−2,ℓ).
So, if you’re looking for exactly one loop, you’d have
P(n,1)=n−1n+1P(n−2,1)⟹P(n,1)={1n+1n is even0n is odd.
I can’t really explain where this recurrence comes from; their proof was twenty pages long. It’s also too complicated to really apply to multiple tiles. But, maybe there’s a more elementary proof for this recursion, and something similar can be done for multiple tiles.
I think I am not understanding the question this equation is supposed to be answer, as it seems wrong to me.
I think you are considering the case were we draw arrowheads on the lines? So each line is either an “input” or an “output”, and we randomly connect inputs only to outputs, never connecting two inputs together or two outputs? With those assumptions I think the probability of only one loop on a shape with N inputs and N outputs (for a total of 2N “puts”) is 1/N.
The equation I had ( (N-2)!! / (N-1)!!) is for N “points”, which are not pre-assigned into inputs and outputs.
These diagrams explain my logic. On the top row is the “N puts” problem. First panel on the left, we pick a unmatched end (doesn’t matter which, by symmetry), the one we picked is the red circle, and we look at the options of what to tie it to, the purple circles. One purple circle is filled with yellow, if we pick that one then we will end up with more than one loop. The probability of picking it randomly is 1⁄7 (as their are 6 other options). In the next panel we assume we didn’t die. By symmetry again it doesn’t matter which of the others we connected to, so I just picked the next clockwise. We will follow the loop around. We are now looking to match the newly-red point to another purple. Now their are 5 purples, the yellow is again a “dead end”, ensuring more than one loop. We have a 1⁄5 chance of picking it at random. Continuing like this, we eventually find that the probability of having only one loop is just the probability of not picking badly at any step, (6/7)x(4/5)x(2/3) = (N-2)!! / (N-1)!!.
In the second row I do the same thing for the case where the lines have arrows, instead of 8 ports we have 4 input ports and 4 output ports, and inputs can only be linked to outputs. This changes things, because now each time we make a connection we only reduce the number of options by one at the next step. (Because our new input was never an option as an output). The one-loop chance here comes out as (3/4)x(2/3)x(1/2) = (N-1)! / N! = 1/N. Neither expression seems to match the equations you shared, so either I have gone wrong with my methods or you are answering a different question.
The bottom row is close to what I imagine, but without IO ports on the same edge being allowed to connect to each other (though that is also an interesting problem). These would be the three diagrams for the square:
The middle one makes a single loop which is one-third of them, and n=4/2=2 in this case. My guess for how to prove the recurrence is to “glue” polygons together:
There are n+1 pairs of sizes (k,n+1−k) we can glue together (if you’re okay with 2-sided polygons), but I haven’t made much progress in this direction. All I’ve found is gluing two polygons together decreases the number of loops by zero, one or two.
This is really wonderful, thank you so much for sharing. I have been playing with your code.
The probability that their is only one loop is also very interesting. I worked out something, which feels like it is probably already well known, but not to me until now, for the simplest case.
In the simplest case is one tile. The orange lines are the “edging rule”. Pick one black point and connect it to another at random. This has a 1⁄13 chance of immediately creating a closed loop, meaning more than one loop total. Assuming it doesn’t do that, the next connection we make has 1⁄11 chance of failure. The one after 1⁄9. Etc.
So the total probability of having only one loop is the product: (12/13) (10/11) (8/9) (6/7) (4/5) (2/3), which can be written as 12!! / 13!! (!! double factorial). For a single tile this comes out at 35% ish. (35% chance of only one loop).
If we had a single shape with N sides we would get a probability of (N-2)!! / (N-1)!! .
The probability for a collection of tiles is, as you say, much harder. Each edge point might not uniformly couple to all other edge points because of the multi-stepping in between. Also loops can form that never go to the edge. So the overall probability is most likely less than (N-2)!!/(N-1)!! for N edge dots.
So, I’m actually thinking about something closer to this for “one loop”:
This is on a single square tile, with four ports of entry/exit. What I’ve done is doubled the rope in each connection, so there is one connection going from the top to the bottom and a different connection going from the bottom to the top. Then you tie off the end of each connection with the start of the connection just clockwise to it.
Some friends at MIT solved this problem for a maths class, and it turns out there’s a nice recurrence. Let P(n,ℓ) be the probability there are ℓ loops in a random knot on a single tile with 2n sides. Then
P(n,ℓ)=2n+1P(n−1,ℓ−1)+n−1n+1P(n−2,ℓ).So, if you’re looking for exactly one loop, you’d have
P(n,1)=n−1n+1P(n−2,1)⟹P(n,1)={1n+1n is even0n is odd.I can’t really explain where this recurrence comes from; their proof was twenty pages long. It’s also too complicated to really apply to multiple tiles. But, maybe there’s a more elementary proof for this recursion, and something similar can be done for multiple tiles.
I think I am not understanding the question this equation is supposed to be answer, as it seems wrong to me.
I think you are considering the case were we draw arrowheads on the lines? So each line is either an “input” or an “output”, and we randomly connect inputs only to outputs, never connecting two inputs together or two outputs? With those assumptions I think the probability of only one loop on a shape with N inputs and N outputs (for a total of 2N “puts”) is 1/N.
The equation I had ( (N-2)!! / (N-1)!!) is for N “points”, which are not pre-assigned into inputs and outputs.
These diagrams explain my logic. On the top row is the “N puts” problem. First panel on the left, we pick a unmatched end (doesn’t matter which, by symmetry), the one we picked is the red circle, and we look at the options of what to tie it to, the purple circles. One purple circle is filled with yellow, if we pick that one then we will end up with more than one loop. The probability of picking it randomly is 1⁄7 (as their are 6 other options). In the next panel we assume we didn’t die. By symmetry again it doesn’t matter which of the others we connected to, so I just picked the next clockwise. We will follow the loop around. We are now looking to match the newly-red point to another purple. Now their are 5 purples, the yellow is again a “dead end”, ensuring more than one loop. We have a 1⁄5 chance of picking it at random. Continuing like this, we eventually find that the probability of having only one loop is just the probability of not picking badly at any step, (6/7)x(4/5)x(2/3) = (N-2)!! / (N-1)!!.
In the second row I do the same thing for the case where the lines have arrows, instead of 8 ports we have 4 input ports and 4 output ports, and inputs can only be linked to outputs. This changes things, because now each time we make a connection we only reduce the number of options by one at the next step. (Because our new input was never an option as an output). The one-loop chance here comes out as (3/4)x(2/3)x(1/2) = (N-1)! / N! = 1/N. Neither expression seems to match the equations you shared, so either I have gone wrong with my methods or you are answering a different question.
The bottom row is close to what I imagine, but without IO ports on the same edge being allowed to connect to each other (though that is also an interesting problem). These would be the three diagrams for the square:
The middle one makes a single loop which is one-third of them, and n=4/2=2 in this case. My guess for how to prove the recurrence is to “glue” polygons together:
There are n+1 pairs of sizes (k,n+1−k) we can glue together (if you’re okay with 2-sided polygons), but I haven’t made much progress in this direction. All I’ve found is gluing two polygons together decreases the number of loops by zero, one or two.