Matching Probability

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 the matching probability between two sequences X and Y using finite Markov chain imbedding.

At each position t, the two sequences are compared:

    match at t      if X_t = Y_t
    mismatch at t   if X_t ~= Y_t

Let L_n be the longest run length of consecutive matches among positions 1, 2, ..., n.

The app computes:

    P(L_n < k)

where:

    n = length of each sequence
    k = match-run length threshold

So the result is the probability that there is NO run of k or more consecutive matches.

The app calls:

    [prob, lambda1, eta1, N, M] = ...
        fmci_matching_probability(n, k, 'markov', distX, distY)

where:

    prob    = P(L_n < k)
    lambda1 = dominant eigenvalue of the transient matrix N
    eta1    = corresponding right eigenvector
    N       = transient-to-transient substochastic matrix
    M       = full transition matrix including absorption

For Markov sequences, the inputs are structures:

    distX.init  = ini_X
    distX.trans = P_X
    distY.init  = ini_Y
    distY.trans = P_Y

No of States
    Enter S, the number of possible states in the common
    alphabet of X and Y.

    The states are labeled:
        1, 2, ..., S

Length of Sequence
    Enter n, the number of positions in each sequence.

Length
    Enter k, the match-run threshold.

    The app computes P(L_n < k), meaning the probability that
    the longest consecutive matching run has length less than k.

The app has four probability-input buttons:

    Enter ini_X
    Enter ini_Y
    Enter transitional P_X
    Enter transitional P_Y

You must enter all four before calculating.

ini_X is the initial distribution of X_1:

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

ini_Y is the initial distribution of Y_1:

    ini_Y = [P(Y_1=1), P(Y_1=2), ..., P(Y_1=S)]

Each initial vector must:
    1. have exactly S entries
    2. contain nonnegative probabilities
    3. sum to 1

Default equal probabilities are:

    [1/S, 1/S, ..., 1/S]

Example for S = 4:

    ini_X = [0.25 0.25 0.25 0.25]
    ini_Y = [0.25 0.25 0.25 0.25]

P_X is the transition matrix for sequence X. P_Y is the transition matrix for sequence Y.

For S states, each transition matrix is S-by-S.

For X:

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

For Y:

    P_Y(i,j) = P(Y_t = j | Y_{t-1} = i)

Each row must sum to 1.

Default equal transition probabilities are:

    every row = [1/S, 1/S, ..., 1/S]

Example for S = 2:

    P_X = [0.8 0.2
           0.3 0.7]

    P_Y = [0.6 0.4
           0.5 0.5]

Interpretation:

    P_X(1,2) = 0.2 means P(X_t=2 | X_{t-1}=1) = 0.2.
    P_Y(2,1) = 0.5 means P(Y_t=1 | Y_{t-1}=2) = 0.5.

Step 1. Click Clear all items
    This removes old inputs, saved probability vectors,
    saved transition matrices, results, and eigen output.

Step 2. Enter No of States
    Example:
        S = 2

Step 3. Enter Length of Sequence
    Example:
        n = 20

Step 4. Enter Length
    Example:
        k = 3

    This means the app computes P(L_20 < 3), the probability
    that there is no run of 3 or more consecutive matches.

Step 5. Click Enter ini_X
    Enter the initial distribution for X.

Step 6. Click Enter ini_Y
    Enter the initial distribution for Y.

Step 7. Click Enter transitional P_X
    Enter the transition matrix for X.

Step 8. Click Enter transitional P_Y
    Enter the transition matrix for Y.

Step 9. Click Calculate the Probability
    The result panel displays P(L_n < k).

Step 10. Optional: Click EigValue/vector
    The eigenvalue panel displays the dominant eigenvalue and
    the first entries of the right eigenvector of N.

The main probability result is:

    P(L_n < k)

where L_n is the longest consecutive matching run.

The app may also display:

    P(L_n >= k) = 1 - P(L_n < k)

This is the probability that at least one run of k or more consecutive matches occurs.

The function also returns the dominant eigenvalue lambda1 and right eigenvector eta1 of the transient matrix N.

The app writes this information into one scrollable text area inside the eigenvalue/vector panel. This avoids overlapping labels and keeps the output readable.

The full eigen information is saved to the MATLAB workspace as:

    MatchingProbabilityEigInfo

The full probability calculation is saved as:

    MatchingProbabilityResultInfo

Question:
    What is the probability that two length-20 Markov sequences
    do not have 3 consecutive matches?

Inputs:
    No of States          = 2
    Length of Sequence    = 20
    Length                = 3

Initial probabilities:
    ini_X = [0.5 0.5]
    ini_Y = [0.6 0.4]

Transition matrices:
    P_X = [0.8 0.2
           0.3 0.7]

    P_Y = [0.7 0.3
           0.4 0.6]

Steps:
    1. Enter S = 2.
    2. Enter n = 20.
    3. Enter k = 3.
    4. Enter ini_X and ini_Y.
    5. Enter P_X and P_Y.
    6. Click Calculate the Probability.

Output interpretation:
    P(L_20 < 3) is the probability that the two sequences have
    no matching block of length 3 or longer.

Question:
    For two length-50 sequences on four states, with equal
    initial probabilities and equal transition probabilities,
    what is P(L_50 < 4)?

Inputs:
    No of States          = 4
    Length of Sequence    = 50
    Length                = 4

Initial probabilities:
    ini_X = [0.25 0.25 0.25 0.25]
    ini_Y = [0.25 0.25 0.25 0.25]

Transition matrices:
    Each row of P_X = [0.25 0.25 0.25 0.25]
    Each row of P_Y = [0.25 0.25 0.25 0.25]

Output interpretation:
    P(L_50 < 4) is the probability that the longest matching
    run is at most 3.

For a DNA-style alphabet, you may label the states as:

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

Example inputs:
    No of States          = 4
    Length of Sequence    = 100
    Length                = 5

    ini_X = [0.30 0.20 0.20 0.30]
    ini_Y = [0.25 0.25 0.25 0.25]

    P_X = [0.70 0.10 0.10 0.10
           0.20 0.50 0.20 0.10
           0.10 0.20 0.50 0.20
           0.10 0.10 0.20 0.60]

    P_Y = [0.60 0.20 0.10 0.10
           0.10 0.70 0.10 0.10
           0.20 0.10 0.60 0.10
           0.25 0.25 0.25 0.25]

Output interpretation:
    P(L_100 < 5) is the probability that the two sequences
    never match for 5 consecutive positions.

1. ini_X and ini_Y must each have exactly S entries.

1. ini_X and ini_Y must each sum to 1.

1. P_X and P_Y must each be S-by-S matrices.

1. Every row of P_X and P_Y must sum to 1.

5. The same state labels must be used for both X and Y.
    State 1 in X is compared to state 1 in Y, etc.

1. Length k must be a positive integer.

1. Length of Sequence n must be a positive integer.

8. If you change S, re-enter ini_X, ini_Y, P_X, and P_Y.
    Old probability vectors or matrices may no longer have
    the correct size.

Click Clear all items to remove:
    input fields
    saved ini_X and ini_Y
    saved P_X and P_Y
    results panel output
    eigenvalue/vector panel output

In the web app, switch tabs or close the browser page to leave the Matching Probability app.