1

I am looking for theoretical results regarding how easy it is to detect alteration of a random sequence.

The permutation I am most interested in is where a subsequence of the random numbers is sorted, or permuted based on values. The random numbers are drawn from a known distribution.

It seems clear to me that excessive reordering must be possible to detect. At the same time it seems like it could be difficult to detect minor alterations.

In between these two I am gessing that there must be some theoretical results.

user239558
  • 113
  • It obviously depends a lot on what kind of random sequence it is and the nature of the alteration. What random sequence do you have in mind? – jerad Mar 11 '13 at 20:40
  • 1
    Sorting is detected by the sequence of signs of the changes in values. The distribution of such sequences is well known (at least when the "known distribution" is continuous) and independent of your distribution; it is the basis of a runs test. – whuber Mar 12 '13 at 03:30

1 Answers1

2

Sounds like your values are basically equivalent to ranks (e.g. we can decide if $X_i < X_j$).

There are various tests for trend (including a spearman correlation or a kendall tau, though there are other trend tests) and dependence (such as runs up and down, runs above and below some known quantile ...); you can generally compute power properties at particular alternatives, depending on what characteristics of permutations you most want sensitivity to.

Glen_b
  • 282,281