patternMinor
Intuitive proof for Floyd's cycle detection algorithm
Viewed 0 times
floydcycleintuitivealgorithmfordetectionproof
Problem
I am trying to understand Floyd's cycle detection algorithm. I can see why the algorithm works.
When the Hare moves twice as fast as Tortoise, if there is cycle, they will meet definitely at some point in the cycle.
Is there any proof that proves the above point? I mean, without assuming that Hare and Tortoise meet at some point when Hare moves twice the speed of Tortoise and then proving.
In the wiki, I can understand the following paragraph.
The key insight in the algorithm is that, for any integers $i ≥ μ$ and $k ≥ 0, x_i = x_{i + kλ}$, where λ is the length of the loop to be found and μ is the index of the first element of the cycle
But it is followed by the following point which I could not understand.
in particular, $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ
How does the author come to conclusion that $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$
Can somebody please help me in understanding this?
When the Hare moves twice as fast as Tortoise, if there is cycle, they will meet definitely at some point in the cycle.
Is there any proof that proves the above point? I mean, without assuming that Hare and Tortoise meet at some point when Hare moves twice the speed of Tortoise and then proving.
In the wiki, I can understand the following paragraph.
The key insight in the algorithm is that, for any integers $i ≥ μ$ and $k ≥ 0, x_i = x_{i + kλ}$, where λ is the length of the loop to be found and μ is the index of the first element of the cycle
But it is followed by the following point which I could not understand.
in particular, $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ
How does the author come to conclusion that $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$
Can somebody please help me in understanding this?
Solution
By definition, $x_0,\ldots,x_{\mu+\lambda-1}$ are all distinct, and for $i \geq \mu$, we have $x_{i+\lambda} = x_i$. Now let us prove the claim:
Let $i \geq 1$. Then $x_i = x_{2i}$ if and only if $i \geq \mu$ and $i = k\lambda$ for some $k \geq 1$.
$\Longleftarrow$ Suppose that $i \geq \mu$ and $i = k\lambda$. Since $i \geq \mu$, we have $x_{i+t\lambda} = x_i$ for all $t \geq 0$. In particular, choosing $t := k$, we get $x_{2i} = x_{i+k\lambda} = x_i$.
$\Longrightarrow$ Suppose that $x_i = x_{2i}$. If $i < \mu$ then $x_j = x_i$ if and only if $j = i$. Since $2i \neq i$ (as $i \neq 0$), this contradicts the assumption $x_i = x_{2i}$, showing that $i \geq \mu$.
Since $i \geq \mu$, $x_i = x_{\mu + [(i-\mu) \bmod \lambda]}$. Similarly, $x_{2i} = x_{\mu + [(2i-\mu) \bmod \lambda]}$. Since $x_\mu,\ldots,x_{\mu+\lambda-1}$ are all distinct, it follows that $i-\mu \bmod \lambda = 2i-\mu \bmod \lambda$, and so $i$ is a multiple of $\lambda$.
Let $i \geq 1$. Then $x_i = x_{2i}$ if and only if $i \geq \mu$ and $i = k\lambda$ for some $k \geq 1$.
$\Longleftarrow$ Suppose that $i \geq \mu$ and $i = k\lambda$. Since $i \geq \mu$, we have $x_{i+t\lambda} = x_i$ for all $t \geq 0$. In particular, choosing $t := k$, we get $x_{2i} = x_{i+k\lambda} = x_i$.
$\Longrightarrow$ Suppose that $x_i = x_{2i}$. If $i < \mu$ then $x_j = x_i$ if and only if $j = i$. Since $2i \neq i$ (as $i \neq 0$), this contradicts the assumption $x_i = x_{2i}$, showing that $i \geq \mu$.
Since $i \geq \mu$, $x_i = x_{\mu + [(i-\mu) \bmod \lambda]}$. Similarly, $x_{2i} = x_{\mu + [(2i-\mu) \bmod \lambda]}$. Since $x_\mu,\ldots,x_{\mu+\lambda-1}$ are all distinct, it follows that $i-\mu \bmod \lambda = 2i-\mu \bmod \lambda$, and so $i$ is a multiple of $\lambda$.
Context
StackExchange Computer Science Q#83577, answer score: 3
Revisions (0)
No revisions yet.