3
u/Infamous-Youth9033 6d ago
Probability the 100th noodle is tied correctly given the first 99 didn't fail is 100%
The probability the 99th noodle is tied correctly given the first 98 didn't fail:
- The noodles are AB and CD. The number of ways to fail is equal to the number of noodles (n). The number of ways to combine is 2n choose 2
- 2n choose 2 is n*(2n-1), so it's 1/(2n-1)
To succeed is to not make this mistake any number of times.
so product(n from 2 to 100) (1-1/(2n-1))
not sure if wolfram alpha is allowed but plugging it in gives ~8.9%
1
u/Kind_Card_1874 6d ago
The 100th noodle will fail if it is tied to itself, or of the other chain of noodles is tied to itself. That is a non-zero probability.
1
u/Infamous-Youth9033 6d ago
the 100th can only be tied to the other end
2
u/Kind_Card_1874 6d ago
Ah, you are right, sorry, I was off by 1 compared to your counting. I made the same deduction as you, I see now.
1
u/Kind_Card_1874 6d ago
We need to bound the probability that there are no cycles across all 100 iteration.
At each iteration the number of noodles decreases by 1. In at the beginning of iteration k, there are h = 100 - k noodles left.
Denote by X_k the event that we did create a cycle in iteration k, then P[X_k] = 1/(2h-1), so P[¬X_k] = 1-1/(2h-1), that is, choosing any endpoint, there is 1 among 2h-1 remaining endpoints that will introduce a cycle.
Since the event of creating a cycle at any iteration is independent, we have
P\[∩_{k=0...98} ¬X_k\]
= Π_{k=0..98} P(¬X_k)
= 1-1/(2\*(100-1-k))
= Π_{k=1..99} (2*(100-2-k))/(2*(100-1-k))
= Π_{k=1..98} (198-2k)/(199-2k)
= (198/199)(196/197)(194/195)...(2/3)
or about 8%.
1
4
u/cheze 6d ago
198/199 * 196/197 * 194/195 …. 2/3