Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.