3
$\begingroup$

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<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>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 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<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.

$\endgroup$
  • $\begingroup$ In your definition of $B$, do you mean $a_i>a_j$ instead of $i>j$? As it stands $B_{i,j}$ provides no information on the total ordering of the $a$'s (i.e., no information on $i_1,\dots,i_n$). Perhaps notation would be cleaner if you used $1,\dots,n$ instead of $a_1,\dots,a_n$ and said that there is an unknown permutation $\pi$ on $\{1,\dots,n\}$. $\endgroup$ – D.W. Feb 21 at 22:59
  • 1
    $\begingroup$ Let $a',a''$ be two consecutive elements in the total ordering. If $B_{a'',a'}=0$, then we have no information on the relative order of $a',a''$: we cannot distinguish whether $a'$ should appear before or after $a''$. So, we need to have $B_{a'',a'}=1$ for all pairs of consecutive elements $a',a''$. There are $n-1$ such consecutive elements, so this happens with probability at most $p^{n-1}$. Therefore, with probability $\ge 1 - p^{n-1}$, we'll have $K>1$. This suggests you need $p \ge 1-1/n$ to have a large probability that $K=1$, which contradicts your guess. $\endgroup$ – D.W. Feb 21 at 23:06
  • $\begingroup$ The difference is that sorting algorithms carefully choose which pairs of elements to compare; whereas in your model, we obtain the result of comparisons for some randomly chosen pair of elements. It's not surprising that we can sort using fewer comparisons if the elements to compare are chosen smartly rather than randomly. $\endgroup$ – D.W. Feb 21 at 23:07
  • 1
    $\begingroup$ For similar reasons, I would expect to have $\mathbb{E}[K] \ge 2^{c(1-p)n}$ for some constant $c$ (maybe $c \to 1/2$ or $c \to 1$ as $n \to \infty$, I'm not sure exactly). $\endgroup$ – D.W. Feb 21 at 23:11
  • 1
    $\begingroup$ I understand. I'm just responding to your sentence beginning "The rationale behind this...", and explaining why it's perhaps unsurprising that this rationale leads to an inaccurate prediction. $\endgroup$ – D.W. Feb 22 at 1:40
2
$\begingroup$

Answer to Question 1

We can assume without loss of generality that the original ordering is the usual one: $a_1 < a_2 < \cdots < a_n$. Some ordering $\pi$ is compatible with our observations if whenever $\pi(i) < \pi(j)$ for some $i > 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.

$\endgroup$
  • $\begingroup$ Thank you so much for the answer. For the reasons mentioned in the update, I've asked for a different quantity that seems to be better suited. I would really appreciate if you have an answer. $\endgroup$ – Ameer Jewdaki Feb 25 at 11:00
  • 1
    $\begingroup$ You seem to have completely changed your question, thus invalidating this answer. Please ask a new question instead. $\endgroup$ – Yuval Filmus Feb 25 at 15:49
  • $\begingroup$ thanks! actually I was exactly looking for a threshold for $p$ that makes $\mathbb{E}[I]$ jump from $0$ to $1$ for sufficiently large $n$. Experiments showed $p=\log n/n$ leads to $1$. which is quite surprising. because it means from an expected number of random $n \log n$ observations we can "almost" sort the elements. "almost" here refers to $I\to1$. What do you think? $\endgroup$ – Ameer Jewdaki Feb 25 at 20:03
  • $\begingroup$ I think you should ask this as a separate question. $\endgroup$ – Yuval Filmus Feb 25 at 20:03
  • $\begingroup$ ok, should I delete the question 2 part and post it separately? $\endgroup$ – Ameer Jewdaki Feb 25 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.