5
$\begingroup$

If I randomly generate a substring (example "ATGCAGC") with equal probability (1/X where X=4) for each digit with length (L) digits: What is the formula for finding the probability (P) of randomly generating that sequence (T) times, given a total string length (N)?

Example: Given "ATGCAGC" string length L=7, number of possible characters X=4 with equal probability of being randomly generated 1/X.

In a case where N characters are generated, what is the probability that an exact substring with length L will occur T times?

If I have randomly, sequentially generated N=7000 characters, what is the probability that any exact substring length L=7 "ATGCAGC" will occur T=2,3,4... times?

P is my dependent variable. L, T, N, X are independent.

In terms of dice:

Example: If I sequentially roll a X=6 sided die N=7000 times: What is the P=probability I will roll the die sequentially the same (1,4,6,5,3,2,3) with sequence length L=7 for T=2 sequentially identical occurrences in the N=7000 sequential rolls of a single die?

What is the probability in 7000 rolls I will have any 2 runs of 7 throws that have an exact sequential match? Example: (1,4,6,5,3,2,3 on rolls 201-207) and (1,4,6,5,3,2,3) on rolls 5001-5007. It could be any number of (T) occurrences, on any roll numbers in (N) total die rolls.

I am specifically solving for the probability, given any values for the independent variables. Overlapping or non-overlapping substrings or both are great.

My question is related to (How many times will a consecutive sequence of throws randomly appear if I throw a four-sided die N times?)

$\endgroup$
  • 2
    $\begingroup$ The English used in this question is incomprehensible. $\endgroup$ – Batman Jul 2 '14 at 7:12
  • $\begingroup$ What are those four(X) possibilities, Lenght is L? Do you need to have the same four letters ATGC or all 26 alphabets?. If such sequences were generated, they are all equally likely with the same probability. Give an example if you cannot communicate properly? $\endgroup$ – Satish Ramanathan Jul 2 '14 at 7:24
  • $\begingroup$ Sorry for the confusion. Have I clarified any with the edit? $\endgroup$ – 12345678910111213 Jul 2 '14 at 7:35
  • $\begingroup$ The 4 possibilities could be anything. The number of possibilities is X and the probability of being randomly generated is 1/X. In this case they are A, or T, or G, or C with equal 1/4 probability of being randomly generated. $\endgroup$ – 12345678910111213 Jul 2 '14 at 7:45
  • $\begingroup$ Exact formulas valid for every (X,N,T) and every substring, do not exist. Can you solve the case T=1 for the substring in your post? Or are you only interested in asymptotics? $\endgroup$ – Did Jul 3 '14 at 8:46
1
$\begingroup$

The question of a probability of a pattern repeating exactly $T$ times does not have a simple formula. I have obtained the probability for the pattern ``ATGCAGC''

A directed graph was used to keep track of the patterns. For $T=1$ itself it's big:

\begin{align*} A_1 &= \left(\begin{array}{rrrrrrrrrrrrrr} 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{align*}

for $T=2$,

\begin{align*} A_2 &= \left(\begin{array}{rrrrrrrrrrrrrrrrrrrrr} 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{align*}

That pattern of matrix continues for $T=3,4,\ldots$, and the entries of interest are the last 7 entries of the first row in $A^{7000}$. Adding those and dividing by $4^{7000}$ gives the required probabilities. Below are the probabilities obtained on computing:

\begin{align*} \begin{array}{|l|c|}\hline T & P \\\hline 1 & 0.278730925452149 \\ 2 & 0.059428898295207 \\ 3 & 0.008431600808656 \\ 4 & 0.000895516555326\\ \hline \end{array} \end{align*}

$\endgroup$
  • $\begingroup$ While looking for an answer to this question, I have become interested in the different ways people have approached this. Can you share why you think this problem is difficult to express mathematically? Do you think a variant of this question could be asked which would have an answer with simpler methods? $\endgroup$ – 12345678910111213 Jul 4 '14 at 23:19
  • 1
    $\begingroup$ I thought about this problem and couldn't find an easier way. For every different pattern, length and number of repetitions, it would have a different formula. An easier variant might be computing the probability of occurence of a given pattern at least once -- which can be written as an absorbing markov chain, but here also the formula depends on the pattern. All we can do for now is to write a program which would give us the matrix for the given pattern and number of possible characters, and use a CAS for computation. $\endgroup$ – gar Jul 5 '14 at 3:20
  • $\begingroup$ @gar, I have been scratching my head as to how you got the matrix A. If you have time could you explain to me how you got this matrix as absorbing markov chain. Thank you very much. $\endgroup$ – Satish Ramanathan Feb 7 '15 at 6:43
0
$\begingroup$

Very Crude method:

If there are X characters, there can be $X^L$ different number of ways you can generate a sequence with each X have $\frac{1}{X}$ probability. Then each such sequence is equally likely.

Thus the probability that a sequence would appear out of the $X^L$ different ways is $\frac{1}{x^L}$.

Then the total number of characters N that are generated will be split into $[\frac{N}{L}]$ blocks of those substrings.

The probability that a substring other than the desired happens in any block is $(1-\frac{1}{X^L})$.

Now define the the random variable T, the number of times such substring should occur where t = 0,1,... [N/L].

Take a case when T = 2, this substring should occur twice and the rest of the $[\frac{N}{L}] - T$ blocks should be other substrings of length L other than the desired for which we calculated the probability a couple of steps above. For N = 100 and L = 5, you will have 20 blocks with 5 strings each. You check the desired substring in each of these blocks. Then shift 1 character and check from 2-6,7-11,... and again shift 1 character from 3-8, 9-12,.... This you do it till you shift 5 times then you get to the original sequence 6-10,11-15,... Now you have in a way scanned all the N characters in 20 blocks five times to cover all consecutive appearances. Once way you could accomodate is to multiply (the probability of finding substring) by L which in this case is 5.

Now we can safely assume these appearances of substrings to be a Binomial Distribution.

Thus

$$P( T = t) =\left({[\frac{N}{L}]\choose t} {(L*\frac{1}{x^L})}^t {(1-L*\frac{1}{X^L})}^{[\frac{N}{L}]-t}\right)$$

I hope this gives a real good approximation for the task that you have laid out.

Thanks

Satish

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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