Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an infinite sequence $a_n$ of uniformly random integers $0$ to $9$, what is the probability there exist an integer $m$ such that the sequence $a_1$ to $a_m$ is equal to that from $a_{m+1}$ to $a_{2m}$?

What if we restrict to two symbols, or $k$ symbols?

share|improve this question
1  
You probably want the squence $a_1$ to $a_m$ and $a_{m+1}$ to $a_{2m}$ so the lengths match and you don't insist that the first and last digits are the same. Also, is "rnaomd" supposed to be a random version of "random"? –  Ross Millikan Oct 23 '12 at 18:31
2  
Rnaomd was a wonderfully serendipitous typo! –  Brian M. Scott Oct 23 '12 at 18:42
1  
At first blush, 1/9 suggests itself: 1/10+1/100+1/1000+... but this isn't right because the probabilities are not independent. So it appears the answer is between 1/10 and 1/9. –  Fixee Oct 23 '12 at 19:16
    
@Fixee yup, I think so too, well at least we can conclude that eventually it will never repeat again... –  Jean-Sébastien Oct 23 '12 at 19:27
    
@Fixee: That calculation assumes that the events are disjoint, not independent. It would predict a probability of $1$ in the binary case. (See also my answer.) –  joriki Oct 24 '12 at 9:23

2 Answers 2

up vote 4 down vote accepted

I can't give an exact answer, but an interesting connection and some numerical results.

Some dabbling with short examples shows that the events for different integers $m$ are nearly but not exactly independent. For instance, some sequences that don't repeat at $m=3$ repeat at $m=2$ but not at $m=1$, whereas for sequences that do repeat at $m=3$ repetition at $m=2$ implies repetition at $m=1$. However, the effect from the dependence appears quite small, so

$$ \prod_{m=1}^\infty(1-k^{-m}) $$

should be a good approximation to the probability that there is no repetition. Incidentally, if $k$ is a prime power, this is the probability that a large random square matrix over $\mathbb F_k$ is invertible; see Probability that a random binary matrix is invertible. In that answer, I computed the product for $k=2$ to be approximately $0.288788$, which would make the probability for a binary sequence to exhibit repetition approximately $0.711212$.

Here are numerical results for $k=2$ for repetitions up to $m=17$. Each row contains the number of strings of length of $2m$ that repeat, the number of strings that don't repeat, the proportion $p_m$ of strings that repeat, and a value $\alpha_m=-\log_2(1-(1-p_m)/(1-p_{m-1}))$ that would be $m$ if repetition at $m$ were independent of previous repetitions (here's the code):

$$ \begin{array}{rrrlr} m&\text{repeating}&\text{non-repeating}&\text{proportion}&\alpha_m\\\hline 1 & 2 & 2 & 0.5 & 1.00000\\ 2 & 10 & 6 & 0.625 & 2.00000\\ 3 & 44 & 20 & 0.6875 & 2.58496\\ 4 & 182 & 74 & 0.7109375 & 3.73697\\ 5 & 738 & 286 & 0.720703125 & 4.88753\\ 6 & 2972 & 1124 & 0.7255859375 & 5.83794\\ 7 & 11924 & 4460 & 0.7277832031 & 6.96450\\ 8 & 47768 & 17768 & 0.7288818359 & 7.95290\\ 9 & 191214 & 70930 & 0.7294235229 & 8.96725\\ 10 & 765136 & 283440 & 0.7296905518 & 9.98483\\ 11 & 3061104 & 1133200 & 0.7298240662 & 10.98340\\ 12 & 12245530 & 4531686 & 0.7298904657 & 11.99044\\ 13 & 48984342 & 18124522 & 0.7299235761 & 12.99397\\ 14 & 195941804 & 72493652 & 0.7299401015 & 13.99640\\ 15 & 783776080 & 289965744 & 0.7299483567 & 14.99761\\ 16 & 3135122038 & 1159845258 & 0.7299524820 & 15.99838\\ 17 & 12540523572 & 4639345612 & 0.7299545438 & 16.99901\\ \end{array} $$

The agreement with $0.711212$ is OK but not marvelous. As suggested by the $m=3$ example, the dependence slightly increases the probability of repetition because a repetition implies correlations between the conditions of repetition at lower values of $m$; but this effect is strongest at $m=3$ and becomes negligible at higher values of $m$, where $\alpha_m\approx m$ shows that almost exactly the expected proportion of sequences repeat for the first time. Thus we can get an accurate estimate of the limit probability from $p\approx p_{17}+(p_{17}-p_{16})\approx0.7299566056$, which should be accurate to eight or nine digits.

I checked OEIS for the sequences of both the repeating and the non-repeating counts; no hit.

P.S.: Note that as t.b. pointed out in a comment under the answer linked to above, by the pentagonal number theorem the above product is given by

$$ \begin{align} \prod_{m=1}^\infty(1-k^{-m})&=\sum_{j=-\infty}^\infty(-1)^jk^{-j(3j-1)/2)}\\&=1-k^{-1}-k^{-2}+k^{-5}+k^{-7}-k^{-12}-k^{-15}+k^{-22}+k^{-26}-\dotso\;, \end{align} $$

which leads to an interesting pattern of digits in its representation in base $k$:

$$ \begin{align} \prod_{m=1}^\infty(1-2^{-m})&=0.01001001111011100000010000111111110111110000000000100\ldots_2\;, \\ \prod_{m=1}^\infty(1-10^{-m})&=0.89001009999899900000010000999999998999990000000000100\ldots_{10}\;. \end{align} $$

share|improve this answer

(I'm not an expert on this (I'm a newbie), but I suddenly hit something while reading the question, it may be wrong)

Assuming $_m$ is a constant:

It will depend on how big $_m$ is. If the $_m = 1$, then the probability would be $\frac1{10}$. If $_m = 2$, then $\frac1{100}$. (ie if you had $19$ as the first two, there are $100$ possibilties of the second two, so the probability of $19$ coming up is $\frac1{100}$.

Therefore, the probablity is $$\frac1{10^m}$$

If $_m$ can be any number:

Then..... I don't know how to work that out. (Unless I suddenly have a brainwave...)

(This is my first answer, I like mathjax.)

share|improve this answer
    
It depends on how you see the question, in your example for $m=2$, say you got $11$ instead. Then you already had a repeating sequence. Your idea is the right one I think, you want to compute the probability for each $m$, and then sum over all $m's$ to get the probability that it ever repeats. –  Jean-Sébastien Oct 23 '12 at 19:03
    
@Jean-Sébastien, yeah I think you're right. However, if $_m$ can change, I see all sorts of compliacted stuff, and I don't think I can work that out. –  ACarter Oct 23 '12 at 19:08

Your Answer

 
discard

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.