Consider a simpler version, where you flip a coin three times, then four times, then five times, etc., and you stop if you ever get the same side for every flip in a given turn. The probability that you'll stop is equal to 1/4 + 1/8 + 1/16 + ... which is 50%. If you do this forever then you'll eventually see a run of ten trillion heads or tails, but you probably won't see that run before your ten trillionth turn.
So I think the question is, does the anti-hydra sequence ever diverge sufficiently from randomness?
This is true.
But it would still halt. Infinity is weird like that. To be clear, I mean the sequence of coin flips where the total value of heads/tails is 2:1.
The probability of having a 2:1 ratio of heads/tails - at some point - in an infinite sequence of fair flips is 1, is it not?
The anti-hydra may have a bias, and only if that bias is against the halt condition do we have a case where we can conclude that the anti-hydra does not halt.
This problem is equivalent to a one-dimensional random walk where the terminating condition is reaching a value equal to the number of steps you've taken divided by 3. I'm not quite sure how to calculate the probability of that.
Intuitively, I'd expect this to have a finite probability. The variance grows with sqrt(n), which gets arbitrarily far away from n/3.
Looking at it another way, this should be very similar to the gambler's ruin problem where the gambler is playing against an infinitely rich house and their probability of winning a dollar is 2/3. If the gambler starts with $1 then the probability of ever reaching zero is 1 - (1/3)/(2/3) = 50%. Reference for that formula: https://www.columbia.edu/~ks20/FE-Notes/4700-07-Notes-GR.pdf
For example, randomly picking the number 0.5 out of the interval of real numbers [0,1] has probability 0, and yet it might happen. The probability of picking an irrational number instead was 1 (because almost all real numbers are irrational), but that didn't happen.
Even if you consider a countably infinite number of events, as with the coinflip example, it might just happen that the coin flips to one side forever.
Since the machines under consideration just represent one specific sequence of events, probabilistic arguments may be misleading.
Relevant xkcd: https://xkcd.com/221/
What are you tring to say?
> The probability of having a 2:1 ratio of heads/tails - at some point - in an infinite sequence of fair flips is 1, is it not?
Yes, but "probability = 1" absolutely does not mean "will happen eventually" in pure mathematics. Infinity is weird like that.
In other words, an unbiased random walk should almost surely return to the origin, but a biased random walk will fail to return to the origin with nonzero probability. This can be considered a biased random walk [0], since the halting condition linearly moves further and further away from the expected value of the 50/50 walk.
That said, empirically and in all current analyses, the Antihydra's parity behaves as if it were roughly fair over long spans (neither a proven odd nor even bias), and the short-range statistics look pseudo-random. Non-halting is overwhelmingly plausible... but a concrete proof seems out of reach.
The sequence is (truly/fairly) random in its distribution of mods 1/2.
Even fair coins flipped infinitely would - on occasion - have arbitrary long results of heads or tails.
So the question becomes, is the anti-hydra sequence 'sufficiently' random?