Random observations of a total ordering, how much they tell us? Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}&lt;a_{\pi(2)}&lt;...&lt;a_{\pi(n)}$. But we don't know $\pi$. What we know is a set of random observations from pairwise order of the elements. The observation matrix $B\in\{0,1\}^{n\times n}$ is  generated randomly as follows:
$$B_{i,j} \sim \begin{cases} \text{Bernoulli}(p)\qquad  \text{ if } i&gt;j \\ 0  \qquad \qquad \qquad \text{ otherwise} \end{cases}$$
in which $p\in[0,1]$ is a constant. The formula above means that elements above diagonal are drawn iid from $\text{Bernoulli}(p)$ and the rest of the elements are $0$. Matrix $B$ denotes our observations of the ordering, i.e. if $B_{i,j}=1$ we know the the the order of $a_i$ and $a_j$, and otherwise don't. The reason that elements on the lower triangle of $B$ are zero is because symmetric observations are reduntant.

Question 1

Let $K$ denote the number of orderings of $a_1,..., a_n$ that are consistent with our partial observations. Since $B$ is a random variable, $K$ is also a random variable. The question is, what the expected value of $K$ and what is its concentration around the mean as a function of $p$? There are two extreme cases: (1) if $p=0$ all orderings are valid and hence $K=n!$ (2) if $p=1$ we have the complete ordering and $K=1$. 

For $0&lt;p&lt;1$ however $K$ would not be a constant. My guess is that for sufficiently large $n$ if $p\gg \mathcal{O}(\frac{\log n}{n})$ would lead to to $\mathbb{E}[K]\to 1$. The rationale behind this is that we would have $\omega(np) = \omega(n \log n)$ comparisons which is an asymptotically larger than the number of comparisons most sorting algorithms make. However, this is far from clear since the observations are taken at random.  

The answer is ideally a distribution with parameter $p$ for the number of possibilities. But if that's not possible, tail bounds or the expected value and variance are also acceptable. 

Question 2

The motivation behind the definition of $K$ was to capture how much uncertainty is left. But it seems to be overestimating it or not express it very well, because if we don't know a few pairs $K$ will grow exponentially with this number. So I was thinking of another natural way to define it. 

Let $O\in\{0,1\}^{n\times n}$ be the result of our observations, in which $O_{i,j}=1$ designates that we have observed $a_i&lt;a_j$. From this matrix we can compute the transitive closure $O^\star$, which applies transitive property to find all the "smaller-than" relations in the data. For example if we have $O_{i,j}=1$ and $O_{j,k}=1$ we will have $O^\star_{i,k}=1$. This holds also for a chain of arbitrary length. 

Let $S$ be the sum of all elements of $O^\star$. If we can conclude the relations between all pairs, $S$ will attain its maximum value of $S=n(n-1)/2$, and so $I=\frac{S}{(n(n-1)/2)}$ is a value which will show how much we know about the ordering, with $1$ meaning we exactly know the ordering, and $0$ meaning we don't know anything. Now the question is: what is its mean $\mathbb{E}[I]$ as a function of $n$ and $p$? And if it's possible to analyze, what is the concentration of $I$ around its mean? Also, what is the threshold for $p$ as a function of $n$ that makes $\mathbb{E}[I]$ jump to $0$ or $1$? 

By simulations I found that when $n\to\infty$, even for a small value of $p=\frac{\log n}{n}$ leads to $I\to1$ with high probability. The reason for this seeming discrepancy between $I$ and $K$ is that if we have $m$ unknown pairs in $O^\star$, then $K$ will grow exponentially w.r.t $m$ while $S$ will only be affected linearly. Although the $I$ and $\log K$ are related, I don't think there is an exact relationship between them.
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.