30 ms·

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The comp

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable. To borrow your phrasing: If you only have a stochastic algorithm, I think you should have to say so.

geysersam 1y ago
You can relax the constraints to bound the cost. If I asked a someone gambling, does it matter if this coin is biased 0.0001%, they will probably say no. And just like that, the algorithm is now guaranteed to terminate. It's a bit unfair to talk about the case (100% T) because in that case you don't have a source of randomness anymore, we've dropped the assumption that you have a source of randomness, and as expected you can't make one from nothing.
- zmgsabst 1y ago
  You have a source of randomness — you just got exceptionally unlucky. A truly random source can produce the same value indefinitely. My point is that you have stochastic termination, but not guaranteed termination. Those are different things.
  - Dylan16807 1y ago
    > My point is that you have stochastic termination, but not guaranteed termination. Those are different things. You missed their suggestion about that. If you rephrase the algorithm as one that almost almost almost almost almost completely eliminates bias, you can guarantee termination by giving up after a certain number of repetitions.
    - zmgsabst 1y ago
      Sure — but now we’re back in the case the person above me was calling out and I was emphasizing by pointing out the stochastic nature: you moved the goal posts. From their comment: > Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed. You can have an arbitrarily small bias, at the cost of increased runtime — but you can’t have a zero bias algorithm that always terminates. You have to move the goalposts (allowing some bias or exceedingly rare cases to not terminate). I’m not sure why people have such a hard time admitting that.
      - Dylan16807 1y ago
        I don't think the termination thing is moving the goalposts. If you have infinite time, then you can wait for it to take more than a few hundred iterations. If you don't have infinite time, it won't take more than a few hundred iterations. Also "constant time" wasn't even part of the original promise! If a goalpost was moved, it was by the person that decided on that requirement after the fact.
        dataflow 1y ago
        > If you have infinite time, then you can wait for it to take more than a few hundred iterations. To be clear, you're making this argument while also arguing "this wouldn't happen in the real world". [1] You can't have it both ways. > Also "constant time" wasn't even part of the original promise! We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than unbounded! A simulator that can't even promise to get to step #2 of the simulation in any bounded amount of time very much needs a giant proactive asterisk on its labeling, because that's not what people understand to be a simulator. Again, if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back. [1] https://news.ycombinator.com/item?id=44228568 https://news.ycombinator.com/item?id=44228568
        Dylan16807 1y ago
        > You can't have it both ways. I addressed that in my next sentence! The whole point of making it two sentences was to split up the real world and not real world cases. Come on. > We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than this! N is 1. Every bound is a constant bound. > if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back. They would not be entitled to a penny back because it's impossible for them to hit the failure case. Even if they could hit it, nobody is getting a refund for "it crashes once per googolplex runs".
  - geysersam 1y ago
    A random source can produce the same value indefinitely, but it cannot produce the same value forever. It is impossible in the sense that the probability that it will happen is zero. That is, even the unbiased version of the algorithm will terminate with 100% probability.
antics 1y ago
Kind of, kind of not. I think it's fair to argue a lot of theory people would argue that it is effectively guaranteed to terminate, for any reasonable definition of "guaranteed." As I mention elsewhere, for a coin where P(H)=0.75, with 600 flips, the probability of not having received an answer is less than 1 divided by the number of atoms in the universe. While this is not 0, neither is the probability of the atoms of the coin lining up just right that it falls through the table, producing neither H or T. Theoretically and practically we do generally consider these kinds of things immaterial to the problem at hand, perhaps papering over them with terms-of-art like "with high/extremely high/arbitrarily high/ probability". They all mean roughly the same thing: this algorithm is "essentially guaranteed" to terminate after n flips.
- deleted 1y ago
  [deleted]
Dylan16807 1y ago
> the worst case (100% T) You're no longer randomly flipping a coin to get heads or tails at that point. There's a good argument that this is not within the original scenario.
- zmgsabst 1y ago
  Yes you are — you just have exceptionally bad luck to generate that sequence.
  - Dylan16807 1y ago
    Oh, I thought you were saying the coin bias was 100%. I misread how you were using complexity class. Still, when a worst case is physically impossible I don't think it needs a mandatory disclaimer.
    - zmgsabst 1y ago
      All infinite sequences are physically impossible, but they’re the basis of asymptotics; arbitrary failure and non-production of entropy are still physically possible.

geysersam 1y ago

You can relax the constraints to bound the cost. If I asked a someone gambling, does it matter if this coin is biased 0.0001%, they will probably say no. And just like that, the algorithm is now guaranteed to terminate. It's a bit unfair to talk about the case (100% T) because in that case you don't have a source of randomness anymore, we've dropped the assumption that you have a source of randomness, and as expected you can't make one from nothing.

zmgsabst 1y ago
You have a source of randomness — you just got exceptionally unlucky. A truly random source can produce the same value indefinitely. My point is that you have stochastic termination, but not guaranteed termination. Those are different things.
- Dylan16807 1y ago
  > My point is that you have stochastic termination, but not guaranteed termination. Those are different things. You missed their suggestion about that. If you rephrase the algorithm as one that almost almost almost almost almost completely eliminates bias, you can guarantee termination by giving up after a certain number of repetitions.
  - zmgsabst 1y ago
    Sure — but now we’re back in the case the person above me was calling out and I was emphasizing by pointing out the stochastic nature: you moved the goal posts. From their comment: > Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed. You can have an arbitrarily small bias, at the cost of increased runtime — but you can’t have a zero bias algorithm that always terminates. You have to move the goalposts (allowing some bias or exceedingly rare cases to not terminate). I’m not sure why people have such a hard time admitting that.
    - Dylan16807 1y ago
      I don't think the termination thing is moving the goalposts. If you have infinite time, then you can wait for it to take more than a few hundred iterations. If you don't have infinite time, it won't take more than a few hundred iterations. Also "constant time" wasn't even part of the original promise! If a goalpost was moved, it was by the person that decided on that requirement after the fact.
      - dataflow 1y ago
        > If you have infinite time, then you can wait for it to take more than a few hundred iterations. To be clear, you're making this argument while also arguing "this wouldn't happen in the real world". [1] You can't have it both ways. > Also "constant time" wasn't even part of the original promise! We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than unbounded! A simulator that can't even promise to get to step #2 of the simulation in any bounded amount of time very much needs a giant proactive asterisk on its labeling, because that's not what people understand to be a simulator. Again, if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back. [1] https://news.ycombinator.com/item?id=44228568 https://news.ycombinator.com/item?id=44228568
        Dylan16807 1y ago
        > You can't have it both ways. I addressed that in my next sentence! The whole point of making it two sentences was to split up the real world and not real world cases. Come on. > We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than this! N is 1. Every bound is a constant bound. > if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back. They would not be entitled to a penny back because it's impossible for them to hit the failure case. Even if they could hit it, nobody is getting a refund for "it crashes once per googolplex runs".
- geysersam 1y ago
  A random source can produce the same value indefinitely, but it cannot produce the same value forever. It is impossible in the sense that the probability that it will happen is zero. That is, even the unbiased version of the algorithm will terminate with 100% probability.

antics 1y ago

Kind of, kind of not. I think it's fair to argue a lot of theory people would argue that it is effectively guaranteed to terminate, for any reasonable definition of "guaranteed." As I mention elsewhere, for a coin where P(H)=0.75, with 600 flips, the probability of not having received an answer is less than 1 divided by the number of atoms in the universe. While this is not 0, neither is the probability of the atoms of the coin lining up just right that it falls through the table, producing neither H or T. Theoretically and practically we do generally consider these kinds of things immaterial to the problem at hand, perhaps papering over them with terms-of-art like "with high/extremely high/arbitrarily high/ probability". They all mean roughly the same thing: this algorithm is "essentially guaranteed" to terminate after n flips.

deleted 1y ago
[deleted]

Dylan16807 1y ago

> the worst case (100% T) You're no longer randomly flipping a coin to get heads or tails at that point. There's a good argument that this is not within the original scenario.

zmgsabst 1y ago
Yes you are — you just have exceptionally bad luck to generate that sequence.
- Dylan16807 1y ago
  Oh, I thought you were saying the coin bias was 100%. I misread how you were using complexity class. Still, when a worst case is physically impossible I don't think it needs a mandatory disclaimer.
  - zmgsabst 1y ago
    All infinite sequences are physically impossible, but they’re the basis of asymptotics; arbitrary failure and non-production of entropy are still physically possible.