Number of Patterns

The original desktop instructions sometimes refer to buttons that open separate input windows. In this single-window web version, enter those same values directly in the text boxes or tables on the current tab. The mathematical meaning of the inputs and outputs is unchanged.

This app computes exact probabilities for the number of occurrences of one or more patterns in a finite sequence. The sequence has S possible states, labeled 1, 2, ..., S. A pattern is a finite string of these state labels.

The main probability reported by the app is:

    P(N_n < r)

where N_n is the number of selected pattern occurrences in the first n trials, and r is the occurrence threshold entered in the box labeled r. Equivalently, this is the waiting-time probability:

    P(W_r > n)

where W_r is the waiting time until the r-th occurrence of any entered pattern. Therefore, if the app reports Probability = 0.72, this means there is probability 0.72 that the r-th occurrence has not happened by time n.

The complementary probability is:

    P(N_n >= r) = P(W_r <= n) = 1 - Probability

This complement is often the probability that at least r occurrences have appeared by time n.

1. m-state trials Enter the number of possible states S.

The valid state labels are:

       1, 2, ..., S

   Example:
       If S = 2, patterns can use only symbols 1 and 2.
       If S = 4, patterns can use only symbols 1, 2, 3, and 4.

   Important:
       Do not use 0 as a state label in this app unless the function has
       been specially modified. The standard format uses 1-based labels.

2. Number of Patterns Enter the number L of different patterns to be studied.

   Example:
       If L = 1, you will enter one pattern, such as:
           1 2 1

       If L = 3, you will enter three patterns, such as:
           1 1
           2 2
           1 2 1

After entering L, click Enter The Patterns.

3. r Enter the occurrence threshold r.

The app computes:

       P(N_n < r)

   Examples:
       r = 1 means the probability that no entered pattern occurs by time n.
       r = 2 means the probability that the total number of occurrences is
             0 or 1 by time n.
       r = 3 means the probability that the total number of occurrences is
             0, 1, or 2 by time n.

If you want the probability that at least r occurrences happen by time n, use:

       1 - Probability

4. Length of Sequence Enter n, the sequence length or time point.

   Example:
       n = 20 means the app studies the first 20 trials of the sequence.

Click Enter The Patterns to open the pattern-entry window. Enter one pattern in each pattern box.

Use spaces between state labels.

Correct examples:

    1 2 1
    2 2
    1 3 2 1

For S = 4, a DNA-style coding could be:

    A = 1
    C = 2
    G = 3
    T = 4

Then the biological pattern A C G would be entered as:

    1 2 3

After saving the patterns, the main app displays them in the Patterns box. You can also click View the Pattern(s) to check what has been saved.

The app supports two counting conventions.

1. Over Overlapping occurrences are counted.

   Example:
       Sequence: 1 1 1
       Pattern:  1 1

       Occurrences under Over counting:
           positions 1-2: 1 1
           positions 2-3: 1 1

       Total occurrences = 2.

2. Non-over Overlapping occurrences are not both counted. After one occurrence is counted, the next occurrence must start after that occurrence ends.

   Example:
       Sequence: 1 1 1
       Pattern:  1 1

       Occurrences under Non-over counting:
           positions 1-2: 1 1

       The overlapping positions 2-3 occurrence is not counted.
       Total occurrences = 1.

Use Over if overlapping patterns are allowed. Use Non-over if patterns must be separated and cannot share symbols.

The app has two probability models for the sequence.

1. Independent Each trial is independent and has the same state-probability vector.

You enter:

       P = [P(State 1), P(State 2), ..., P(State S)]

The vector must have S entries, all entries must be nonnegative, and the entries must sum to 1.

Example for S = 2:

       P = [0.6 0.4]

This means:

       P(X_t = 1) = 0.6
       P(X_t = 2) = 0.4

Example for S = 4:

       P = [0.25 0.25 0.25 0.25]

This gives equal probability to all four states.

2. Markov Dependent The next state depends on the current state through a transition matrix.

You must enter two objects:

       Initial P
       Transition P

Initial P is the distribution of X_1:

       Initial P = [P(X_1=1), P(X_1=2), ..., P(X_1=S)]

Transition P is an S-by-S matrix:

       Transition P(i,j) = P(X_t = j | X_{t-1} = i)

Each row of the transition matrix must sum to 1.

Example for S = 2:

       Initial P = [0.7 0.3]

       Transition P =
           [0.8  0.2
            0.4  0.6]

   Interpretation:
       If the current state is 1, then the next state is 1 with probability
       0.8 and state 2 with probability 0.2.

       If the current state is 2, then the next state is 1 with probability
       0.4 and state 2 with probability 0.6.

Goal:
    Compute the probability that the pattern 1 2 1 does not occur by time
    n = 20 in an independent two-state sequence.

Mathematically, this is:

    P(W_1 > 20) = P(N_20 < 1)

Inputs:

    m-state trials       = 2
    Number of Patterns   = 1
    r                    = 1
    Length of Sequence   = 20
    Counting             = Over
    Dependency           = Independent
    Pattern              = 1 2 1
    Probability P        = [0.5 0.5]

Steps:

    1. Click Clear all items.
    2. Enter m-state trials = 2.
    3. Enter Number of Patterns = 1.
    4. Enter r = 1.
    5. Enter Length of Sequence = 20.
    6. Select Over.
    7. Select Independent.
    8. Click Enter The Patterns.
    9. Enter the pattern:
           1 2 1
   10. Click Save.
   11. Click Enter the probability P.
   12. Enter:
           P(State 1) = 0.5
           P(State 2) = 0.5
   13. Click Save.
   14. Click Calculate the Probability.

Output interpretation:

    Probability = P(N_20 < 1) = P(no occurrence of 1 2 1 by time 20).

The probability of at least one occurrence by time 20 is:

    1 - Probability

Goal:
    Compute the probability that the pattern 1 1 occurs fewer than two times
    by time n = 15.

Inputs:

    m-state trials       = 2
    Number of Patterns   = 1
    r                    = 2
    Length of Sequence   = 15
    Counting             = Over
    Dependency           = Independent
    Pattern              = 1 1
    Probability P        = [0.6 0.4]

Meaning:

    The app computes P(N_15 < 2).

That includes the cases:

    N_15 = 0 occurrences
    N_15 = 1 occurrence

The complement is:

    P(N_15 >= 2) = 1 - Probability

which is the probability that the pattern 1 1 occurs at least twice by time 15.

Goal:
    Compute the probability that fewer than three total occurrences of a
    collection of patterns appear by time n = 30.

Inputs:

    m-state trials       = 3
    Number of Patterns   = 3
    r                    = 3
    Length of Sequence   = 30
    Counting             = Over
    Dependency           = Independent
    Probability P        = [0.2 0.5 0.3]

Patterns:

    Pattern 1: 1 2
    Pattern 2: 2 3
    Pattern 3: 3 1 2

Steps:

1. Enter m-state trials = 3.
2. Enter Number of Patterns = 3.
3. Enter r = 3.
4. Enter Length of Sequence = 30.
5. Select Over and Independent.
6. Click Enter The Patterns and enter the three patterns above.
7. Click Enter the probability P and enter [0.2 0.5 0.3].
8. Click Calculate the Probability.

Output interpretation:

    Probability = P(total number of occurrences of all three patterns < 3).

The total count combines all entered patterns. For example, if pattern 1 occurs once and pattern 2 occurs twice by time n, then the total count is 3.

Goal:
    Compute the probability that the pattern 1 2 1 has not occurred by time
    n = 25 in a Markov-dependent two-state sequence.

Inputs:

    m-state trials       = 2
    Number of Patterns   = 1
    r                    = 1
    Length of Sequence   = 25
    Counting             = Over
    Dependency           = Markov Dependent
    Pattern              = 1 2 1

Initial P:

    [0.7 0.3]

Transition P:

    [0.8 0.2
     0.4 0.6]

Steps:

    1. Click Clear all items.
    2. Enter m-state trials = 2.
    3. Enter Number of Patterns = 1.
    4. Enter r = 1.
    5. Enter Length of Sequence = 25.
    6. Select Over.
    7. Select Markov Dependent.
    8. Click Enter The Patterns and enter:
           1 2 1
    9. Click Enter the Initial P and enter:
           0.7   0.3
   10. Click Enter the Transition P and enter:
           0.8   0.2
           0.4   0.6
   11. Click Calculate the Probability.

Output interpretation:

    Probability = P(W_1 > 25) = P(the first occurrence of 1 2 1 happens
    after time 25).

The probability that 1 2 1 occurs at least once by time 25 is:

    1 - Probability

Suppose the states represent DNA bases:

    1 = A
    2 = C
    3 = G
    4 = T

Goal:
    Compute the probability that the pattern A C G, entered as 1 2 3, does
    not occur by time n = 100.

Inputs:

    m-state trials       = 4
    Number of Patterns   = 1
    r                    = 1
    Length of Sequence   = 100
    Counting             = Over
    Dependency           = Independent
    Pattern              = 1 2 3
    Probability P        = [0.25 0.25 0.25 0.25]

Output interpretation:

    Probability = P(no A C G pattern occurs in the first 100 positions).

The probability that A C G occurs at least once is:

    1 - Probability

Let the pattern be:

    1 1

and suppose the sequence begins:

    1 1 1 1

Under Over counting, the pattern 1 1 occurs at:

    positions 1-2
    positions 2-3
    positions 3-4

so the count is 3.

Under Non-over counting, the occurrences cannot share symbols. One possible non-overlapping count is:

    positions 1-2
    positions 3-4

so the count is 2.

For highly self-overlapping patterns such as 1 1, 1 1 1, or 1 2 1 2, the choice between Over and Non-over can significantly change the probability.

After clicking Calculate the Probability, the app displays output in the Results panel.

Typical output:

    Probability = 0.4321
    Mean = ...

The Probability line means:

    P(N_n < r) = P(W_r > n)

The Mean line is the mean value returned by the FMCI calculation for the same input model and pattern-counting convention.

The app also prints the inputs used to the MATLAB Command Window. This is helpful for checking that the correct patterns, probabilities, and transition matrix were used.

The EigValue/vector button is used for eigenvalue and eigenvector information associated with the FMCI transition matrix. This information is useful for large-n approximations and for checking the structure of the imbedded Markov chain.

For ordinary probability calculations, you usually only need the Calculate the Probability button.

Click Clear all items before starting a new example. This clears the visible input boxes. If your version also clears saved pattern and probability data, you should re-enter patterns and probabilities after clearing.

A safe workflow is:

    Clear all items
    Enter S, L, r, and n
    Enter patterns
    Enter probabilities
    Calculate

1. Using 0 as a state label This app uses states 1, 2, ..., S. For S = 2, use states 1 and 2, not 0 and 1.

2. Pattern symbol outside the allowed range If S = 3, the pattern 1 4 is invalid because state 4 does not exist.

3. Probability vector has the wrong length If S = 4, the probability vector must have four entries.

4. Probability vector does not sum to 1
   Example invalid vector:
       [0.2 0.2 0.2]
   because it sums to 0.6.

5. Transition matrix rows do not sum to 1 In the Markov case, each row of Transition P must sum to 1.

6. Forgetting to re-enter probabilities after changing S If you change the number of states, re-enter Initial P and Transition P.

7. Entering the wrong number of patterns If Number of Patterns = 3, fill all three pattern boxes before saving.

8. Misinterpreting r r is not the length of the pattern. It is the occurrence threshold. Pattern length is determined by how many symbols you type in the pattern entry window.

9. Misinterpreting the displayed Probability The displayed Probability is P(N_n < r), not P(N_n = r).

10. Forgetting the complement If you want the probability that at least r occurrences happen by time n, compute 1 - Probability.

Independent case:

    Select Independent
    Enter probability P
    P has length S and sums to 1

Markov dependent case:

    Select Markov Dependent
    Enter Initial P
    Enter Transition P
    Each row of Transition P sums to 1

Probability interpretation:

    Probability = P(N_n < r) = P(W_r > n)

Complement:

    1 - Probability = P(N_n >= r) = P(W_r <= n)