The paper http://projects.laas.fr/METROSEC/DOC/WA1_1.pdf uses a simple technique to detect intrusions in computer systems. I will briefly explain it and ask a question:

The paper proposes a simple 1-order markov chain modeling approach to detect if a given sequence $S = S_1S_2S_3...S_n$ is an anomaly (Here $S_i$'s are unix system commands) . The author determines the likelihood of $S$, $P(S)$, using the following equation

$P(S)=q_{S_1}\prod_{t=2}^{|S|}p_{S_{t-1}S_t}$

where $q_{S_1}$ is the probability of observing the symbol $S_1$ in the training set and $p_{S_{t-1}S_t}$ is the probability of observing the symbol  $S_t$ after symbol $S_{t−1}$ in the
training set. The inverse of $P(S)$ is the anomaly score for $S$. 

(The description above is taken from http://cucis.ece.northwestern.edu/projects/DMS/publications/AnomalyDetection.pdf)

And my question:
How can we handle the case if the sequences are of different sizes (the paper assumes sequences of fixed sizes). The problem is that longer sequences will have smaller probability values compared to shorter ones. So, longer sequences will more likely to be treated as anomalous. I think we need to apply a kind of normalization but I could not figure out what kind of normalization to apply.

Thanks