<p>The latter would imply that the statement holds for <em>every</em> random oracle; the former statement only asserts it is true for &quot;most&quot; random oracles, with some vanishingly small fraction that don't satisfy the claim.</p>
<p><s>For example: &quot;a randomly chosen integer is non-zero with probability 1&quot; is true, because the odds of picking 0 from all infinitely many integers is 0. But &quot;a randomly chosen integer is non-zero&quot; is false, because we could pick 0.</s></p>
<p>Edit: as pointed out in the comments, a correct example distribution would instead be a uniform distribution over <span class="math-container">$[0,1]$</span>. A number selected from this distribution is non-zero with probability 1, but not all numbers in this distribution are non-zero.</p>

CC BY-SA 4.0
2022-07-07T13:03:49.550Z
I can't make sense of the example. There is no probability measure on the integers such that every individual number has probability 0. What makes it possible in the result in question that "probability 1" does not mean "all" is that the space of all oracles is uncountable.
Emil Jeřábek
CC BY-SA 4.0
2022-07-07T13:15:35.317Z
@EmilJeřábek Just switch his example to uniform distribution on $[0,1] \subseteq \mathbb{R}$.
mathworker21
CC BY-SA 4.0
2022-07-07T13:40:03.997Z
Though there are distributions on the integers where 0 has probability 0, so uncountability is not required. :)
Geoffrey Irving
CC BY-SA 4.0
2022-07-07T16:23:33.943Z
@GeoffreyIrving Yes, I was being sloppy. I should have written "all elements of support".
Emil Jeřábek
CC BY-SA 4.0
2022-07-07T11:49:40.143Z
2022-07-07T14:41:46.260Z
2022-07-07T14:41:46.260Z
Jake
<p>As I was browsing the Complexity Zoo, I came across this statement:</p>
<blockquote>
<p>Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86].</p>
</blockquote>
<p>What confused me was the addition of &quot;with probability 1&quot;. What does that mean and why is the current formulation different from</p>
<blockquote>
<p>Relative to a random oracle, PH is strictly contained in PSPACE [Cai86].</p>
</blockquote>
<p>A related question: is there a difference between saying something is deterministic or some process succeeds with probability one?</p>

<cc.complexity-theory>
Containment: deterministic versus with probability one
nippon
# Containment: deterministic versus with probability one

(Asked by: username_0 on 2022-07-07)

As I was browsing the Complexity Zoo, I came across this statement:

> Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86].

What confused me was the addition of "with probability 1". What does that mean and why is the current formulation different from

> Relative to a random oracle, PH is strictly contained in PSPACE [Cai86].

A related question: is there a difference between saying something is deterministic or some process succeeds with probability one?

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2022-07-07. Score: 4 | Accepted answer

The latter would imply that the statement holds for *every* random oracle; the former statement only asserts it is true for "most" random oracles, with some vanishingly small fraction that don't satisfy the claim.

~~For example: "a randomly chosen integer is non-zero with probability 1" is true, because the odds of picking 0 from all infinitely many integers is 0. But "a randomly chosen integer is non-zero" is false, because we could pick 0.~~

Edit: as pointed out in the comments, a correct example distribution would instead be a uniform distribution over $[0,1]$. A number selected from this distribution is non-zero with probability 1, but not all numbers in this distribution are non-zero.

> **Comments:**
> **username_2**: I can't make sense of the example. There is no probability measure on the integers such that every individual number has probability 0. What makes it possible in the result in question that "probability 1" does not mean "all" is that the space of all oracles is uncountable.  
> **username_3**: @EmilJeřábek Just switch his example to uniform distribution on $[0,1] \subseteq \mathbb{R}$.  
> **username_4**: Though there are distributions on the integers where 0 has probability 0, so uncountability is not required. :)  
> **username_2**: @GeoffreyIrving Yes, I was being sloppy. I should have written "all elements of support".  

---

