# Probability that two numbers do not follow each other and are distributed over a sequence

Assume a sequence $S$ of numbers out of the set $N={1..n}$.

Example: $$S = "123312"$$

Set of all pairs would be: $$M = (2,3),(3,3), (3,1)$$

Not in $M$:

$(1,1)$ : not occuring in the sequence next to each other.

$(1,2)$ : occuring twice

Numbers are order-dependent. $(1,2)$ != $(2,1)$

What is the probability that all pairs $(a$,$b)$ out of the set $M$ that occur only once in $S$ are evenly distributed over the length of the sequence $S$? How do i model "evenly distributed" over $S$ best?

(In reality i would like an even distance between the pairs $(a$,$b)$. Or at least the probability for that.) Should i model it as part of Quintiles with bins in which the pairs fall(like i highlighted in this example? What would be the mathematical term for such a distribution?

The arrow represents the sequence $S$ made up of instances of $N$ of length $L$. The yellow circles denote the position $p$ of a pair $(a$,$b)$ that only once occurs in $S$. The horizontal arrow denotes the distance $D$ between two yellow circles.

I also would like to plug into this different probabilities from the set N={1..n} with pN=p(1..n).

What i have tried so far is computing the probability that a pair occurs in a certain part of the sequence and not in the other parts. I them sum this up over all possible pairs. However the equations get pretty nasty somehow and mathematica cannot simplify them by much. Pretty sure, that there should be a solution that is not too complicated.

-
a/b is a pair. not a fraction. how can i express that more clearly? – tarrasch Oct 8 '12 at 7:29
Say $(a,b)$ if it is the pair you consider. I guess it should be a pair out of $N^2$, not $N$, then. $S$ is a set of pairs, right? – Ewan Delanoy Oct 8 '12 at 7:31
The fractions in your drawing should be pairs also? – Ewan Delanoy Oct 8 '12 at 7:33
yes you are right. the fractions in the drawing are pairs also. – tarrasch Oct 8 '12 at 8:07
Have you listed all possible pairs of $M$ in your example? What about $(1,2)$ and $(1,1)$? – Raskolnikov Oct 8 '12 at 8:27

I will only consider the question, 'How do i model "evenly distributed" over $S$ best?' and even for that question I will just give you a search term. If you have a finite collection of numbers $$\{{x_1,x_2,\dots,x_n\}}$$ with $0\le x_i\lt1$ for $i=1,2,\dots,n$, then you can calculate a quantity called the discrepancy of the set, which will give you a measure of how far it is from being evenly distributed. So my advice is that you hunt around for discussions of the mathematical concept of discrepancy.