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

<p>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.</p>

CC BY-SA 4.0
2018-11-15T18:32:46.607Z
2018-11-15T18:32:46.607Z
D.W.
<p>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 <span class="math-container">$[0, 1]$</span> 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 <span class="math-container">$\epsilon$</span> of the approximation.)</p>

<p>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?</p>

<randomized-algorithms><randomness>
What forms of randomness are 'allowed' in FPRASs?
Timon Knigge
# What forms of randomness are 'allowed' in FPRASs?

(Asked by: username_0 on 2018-11-15)

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?

**Tags:** randomized-algorithms, randomness


---

## 1 answers

### Answer by username_1 on 2018-11-15. Score: 1

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.


---

