Is there any commonly accepted method to derive probabilities of sequences that are not dependent on length?


I'm trying to generate sequences of symbols from the individual probabilities of occurrences of each symbol. These probabilities are conditioned on the symbols that came before the current one.

I want to generate the most-likely sequences, where each sequence is not necessarily the same length. Currently I'm just multiplying the individual character occurrences to calculate the probability of the sequence.

I realize this is wrong, since the probabilities are not independent, but don't know how to correct it at this point.

My main problem is that using this method, shorter sequences necessarily have a higher probability, and I'd like the sequence probability not to depend on its length.



I do not believe that the probabilities of shorter sequences are necessarily higher than those of longer sequences, but I do believe that the most probable shorter sequence are necessarily higher than the most probable longer sequence. This is assuming your independence assumption.


To kick you off. You can just use conditional probabilites using a markov assumption. For example, I have a sequence of length 3, $x_0x_1x_2$. The probability distribution of sequence of length 3 is $P(x_0,x_1,x_2)=P(x_2,x_1|x_0)P(x_0)= P(x_2|x_1,x_0)P(x_1|x_0)P(x_0) =P(x_2|x_1)P(x_2|x_0)P(x_0)$. This can be easily generalised for a sequence of length $n$.

From then, you would have to pick an appropriate model for the conditionals and a prior. For example, the $P(x_0)$ can be a discrete uniform distribution and $P(x_2|x_1) \sim Pois(x_1)$ and $P(x_1|x_0) \sim Pois(x_0)$. Whatever constructed distribution you please ; you seem to seek something with finite support of sample set of symbols.


Effectively, you can get rid of the dependence of length by creating an event such as randomly sampling a variable $S$ from a uniform discrete distribution with maximum value of 10. Then you can construct a distribution,

$P(x_0,x_1,x_2, \dots, S) = \frac{ P(S)p(x_0) \large \prod_i \small p(x_{i+1}|x_i) }{\sum_{S=1, \dots ,10} \int_{i \in S,\dots} P(x_0,x_1,x_2, \dots| S)} $

The choice of distribution of $S$ is essential. By picking $S$ to be a discrete uniform, you remove the dependence on the length or at least you can select distributions for each length sequence. Although in the case that you seek an infinite range, you can choose $S$ to be like a poisson, where depending on your choice of parameter longer sequences might be more likely than shorter sequences but up to a point then shorter sequences will be more likely than longer sequences.

The most likely sequences will be conditional on the distributions you choose. This needs investigation depending on your choice. Perhaps if you specify more clearly how short and long lengths could vary I could help a little more, but I am confident you will be able to find a counter example in which the maximum probability will not always be less likely for sequences which are longer.

| cite | improve this answer | |

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.