1
$\begingroup$

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?

example

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.

  • 0
    yes, that would be the lower bound. a brujin sequence is the most condensed form where you get all pairs.2012-10-15

1 Answers 1

1

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.