Random observations of a total ordering, how much they tell us?
Answer to Question 1

We can assume without loss of generality that the original ordering is the usual one: $a_1 &lt; a_2 &lt; \cdots &lt; a_n$. Some ordering $\pi$ is compatible with our observations if whenever $\pi(i) &lt; \pi(j)$ for some $i &gt; j$, this observation is missing. In other words, $\pi$ is compatible with probability $(1-p)^{\operatorname{inv}(\pi)}$, where $\operatorname{inv}(\pi)$ is the number of inversions of $\pi$. Using the generating function of the number of inversions, we get that the expected number of compatible orderings is exactly
$$
\mathbb{E}[K] = \prod_{m=2}^n \frac{1-(1-p)^m}{p}.
$$
In the same way you might be able to compute larger moments of $K$, and so obtain some concentration bounds. Whether one should expect good concentration, and for which values of $p$, remains to be seen, though perhaps it's best to perform some numerical experiments to get a feel for how this behaves.



Answer to Question 2

Let $q_\delta$ be the probability that $O^*$ contains $(i,i+\delta)$. We can compute by brute force
\begin{align*}
q_1 &amp;= p, \\
q_2 &amp;= p + p^2 - p^3, \\
q_3 &amp;= p + 2p^2 - p^3 - 4p^4 + 4p^5 - p^6, \\
q_4 &amp;= p + 3p^2 - 11p^4 + p^5 + 30p^6 - 42p^7 + 26p^8 - 8p^9 + p^{10},
\end{align*}
and so on. Consulting the OEIS, we find the sequence of coefficients (for $-q_\delta(-p)$) as A214670.

Given the $q_\delta$, it is easy to compute the expectation of $I$, though since there isn't a particularly nice formula for $q_\delta$, this won't result in a reasonable formula for $\mathbb{E}[I]$.

You could ask for the threshold behavior of $\mathbb{E}[I]$, that is, at what value of $p$ does the expectation jump from 0 to 1, and how quickly. This is a different and interesting question.