Can we derive an expression for Pcrit based on the actual number of interim inversions (those remaining after the first pass)?
For example, the initial number of inversions for a random collection of N elements is N(N-1)/4. A perfect encoding scheme should result in zero interim inversions. What we want is a number of interim inversions which is O(N). But is that possible?
If p is the probability that h(x)-h(y) has same sign as x-y, then p relates to a pair, not an individual. So, I think the best we can do is to reduce the number of inversions to (1-p) N(N-1)/4. Obviously, this can never be linear.
Can anyone think of a better way to think about this? Maybe set up an experiment that could measure this.
Can we derive an expression for Pcrit based on the actual number of interim inversions (those remaining after the first pass)?
For example, the initial number of inversions for a random collection of N elements is N(N-1)/4. A perfect encoding scheme should result in zero interim inversions. What we want is a number of interim inversions which is O(N). But is that possible?
If p is the probability that h(x)-h(y) has same sign as x-y, then p relates to a pair, not an individual. So, I think the best we can do is to reduce the number of inversions to (1-p) N(N-1)/4. Obviously, this can never be linear.
Can anyone think of a better way to think about this? Maybe set up an experiment that could measure this.