4 ms·

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

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.

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.