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)}. 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>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<p<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 captu

Answer to Question 1

We can assume without loss of generality that the original ordering is the usual one: $a_1 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 &= p, \\
q_2 &= p + p^2 - p^3, \\
q_3 &= p + 2p^2 - p^3 - 4p^4 + 4p^5 - p^6, \\
q_4 &= 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.

StackExchange Computer Science Q#104686, answer score: 2