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
    a/b is a pair. not a fraction. how can i express that more clearly?2012-10-08
  • 0
    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?2012-10-08
  • 0
    The fractions in your drawing should be pairs also?2012-10-08
  • 0
    yes you are right. the fractions in the drawing are pairs also.2012-10-08
  • 0
    Have you listed all possible pairs of $M$ in your example? What about $(1,2)$ and $(1,1)$?2012-10-08
  • 0
    $(1,2)$ is not unique, (1,1) are not next to each other. added into the question2012-10-08
  • 0
    @tarrasch : Do you distinguish (a,b) from (b,a) in your pairs or not?2012-10-08
  • 0
    yes those are two pairs.2012-10-08
  • 0
    @tarrasch I think it is called [De Bruijn sequence](http://en.wikipedia.org/wiki/De_Bruijn_sequence#cite_note-1) (or Maximum length sequence, M-sequece), the number of such sequences have been calculated by some mathimaticians.2012-10-14
  • 0
    the De Bruijn sequence is used for creating a sequence that consists of these pairs. what i would like is to analyse the distribution of those numberpairs2012-10-15
  • 0
    @tarrasch Isn't the probability equals to (the number of all possible De Bruijin sequences)/(the number of all sequences)? One slightly change should be made because De Bruijin sequence is cyclic.2012-10-15
  • 0
    sorry, I misunderstood, that should be the lower bound2012-10-15
  • 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