0
$\begingroup$

I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able to generate uniformly random numbers in the unit interval is strictly stronger than being able to generate random bits. Is this true? Or can you approximate the uniform distribution over $[0, 1]$ sufficiently well with dyadic rationals? (Note that I'm explicitly talking about approximation schemes, so maybe you're able to hide an error term in your probability distribution in the $\epsilon$ of the approximation.)

If it is true that one form of randomness is stronger than the other, what forms of randomness are generally assumed to be available to an (F)PRAS?

$\endgroup$

1 Answer 1

1
$\begingroup$

It's the standard model for any randomized algorithm, e.g., generate a random bit.

You can't generate a uniformly random number in the unit interval in the standard model. You can't even represent a real number in a finite amount of space. If you want to compute with real numbers, you need a different model of computation designed for reasoning about computation with real numbers.

$\endgroup$

Your Answer

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

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