In wiki, PTM are defined with two transition functions and a fair coin toss which determines which one is used at each step. One can also define them, much like NDTM, using a transition relation where in each step the machine chooses from its next possible configurations using a fair probabilistic choice. My question is: how are these equivalent? If there is, say 10 possible next configurations at a given step how could you encode this in a PTM which only has 2 transition functions?


1 Answer 1


The translation is a bit subtle because it doesn't preserve worst-case running time, but does preserve expected running time up to a constant. I'll consider your example of a state with 10 possible transitions. To simulate this transition in a coin-flip (binary) model, we essentially need to use a fair coin to generate a random number between 1 and 10.

There are many ways to do so, but the most obvious is to repeatedly generate a number between 1 and 16 (the next power of 2), using 4 coin flips. If the number is between 1 and 10, terminate the sub-procedure and transition to the next state as appropriate. If it's between 11 and 16, try again. This sub-procedure requires only a constant number of states (at least 16 to record the 4 coin flips, perhaps more as the Turing machine has to stay in place after each flip and if the model does not allow a Stay instruction, we need to move Left and then back Right again to stay in place). But it is guaranteed to terminate in expected finite time.

It is impossible to generate a random number uniformly between 1 and 10 using coin flips using worst-case finite time. To see this, note that if the worst-case running time is bounded by, say, $k$, then there are $2^k$ possible coin flips, so $2^k$ possible outcomes, which is never a multiple of $10$, so we can never assign numbers between $1$ and $10$ to the $2^k$ outcomes in a uniform (fair) manner.

In practice, the definition of running time we care about for probabilistic Turing machines is one of two possibilities:

  1. Expected running time -- this definition is used in the complexity class ZPP. For this possibility, the above translation will be valid.
  2. Worst-case finite running time -- this definition is used in the complexity class BPP. In this case, the above translation is not good as it will not preserve worst-case running time. Here we need a different translation which instead tolerates some error: we cut off the procedure to generate a random number between 1 and 10 after a certain constant $k$ number of iterations, and we keep track of the error involved. Since $k$ can depend on the input, we can make it large enough that the error is small enough that we don't care, at least for the purposes of the complexity class BPP, which is defined to be problems that can be solved to within a small probability of error.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.