# Conflict and Computation on Wikipedia:
## 2 Methods
### Subspaces, Trapping Time, and Viterbi Reconstruction for HMMs  
In general, as a system evolves in the HMM paradigm, it will spread out over its internal state space. A characteristic feature of this spreading out is the so-called relaxation time, which determines how long the system stays confined in a particular subspace of its possible internal states before returning to its characteristic stationary distribution. Once the best-fit HMM has been found, we can compute the relaxation time, \(\tau\), by reference to the second eigenvalue of the transition matrix, \(\lambda_{2}\),  
\[\tau=\frac{1}{1-\lambda_{2}}. \tag{1}\]  
Informally, and for the cases we consider here, when \(\lambda_{2}\) is very close to unity (small spectral gap), the system can take a long time to return to the stationary distribution (see Appendix C for further discussion). This can be understood by writing down an approximation for the probability that the system will be found in a particular state at time \(t\), \(\vec{v}(t)\),  
\[\vec{v}(t) \propto v^{(1)}+\alpha v^{(2)}\lambda_{2}^{t}+\ldots, \tag{2}\] \[\approx v^{(1)}+\alpha v^{(2)}e^{-t/(\tau-\frac{1}{2})}+\ldots\]  
where \(v^{(1)}\) is the stationary distribution of the chain, equal to the first eigenvector of the transition matrix, \(v^{(2)}\) is the second eigenvector, and \(\alpha\) depends on the initial conditions. The remaining terms are exponentially suppressed relative to \(v^{(2)}\); the approximation in the second line holds in the limit that \(\lambda_{2}\) is close to unity. The second eigenvector, \(v^{(2)}\), describes the perturbation that takes the longest time to die away. It allows us to split the system into two subspaces based on the signs of its entries; we define all of the states where \(v^{(2)}\) is, say, positive, as \"subspace one\", and the remaining states as \"subspace two\". One set of states is associated with the positive \(v^{(2)}\) values; the complementary set with those that are strictly negative. Informally, initial conditions that are weighted towards states solely in one of these two sets (all positive \(v^{(2)}\) values or all negative) take the longest to decay to the stationary distribution. It is these two spaces that will define the system epochs. The use of the sign structure of an HMM's eigenvectors is a natural way to identify these subspaces; similar methods have been applied to, for example, the identification of metastable states in chemical reaction networks through what is called Perron Cluster Cluster Analysis (PCCA) [37; 38; 39]. Use of just the second eigenvector naturally splits the system into the two most significant subspaces. The sign structure of the third and higher eigenvectors can be used to further decompose the space in a hierarchical fashion, potentially subdividing these larger modules (see, e.g., [40]). In this paper, we focus solely on the first division, and do not attempt to identify substructures within either of the two main clusters. Once we know the parameters of the HMM, we can use Viterbi path reconstruction [41] to reconstruct the maximum-likelihood path through the state space. We then know, at any point in the time series, where we are in the underlying computational state space. This allows us to associate an internal state of the HMM to each step in the time series and, thus, to each edit on the page itself. We can also pinpoint when a transition from one subspace to the other occurs. When a system switches subspaces, there can be some flickering, with rapid shifting back and forth between subspaces before the system settles down. We only count a transition from one subspace to another when the system remains in the new subspace for more than ten time steps. Given this definition, we can then study time spent within each subspace; we call this empirical quantity the \"trapping time\", \(\tilde{\tau}\); per the definition of \(\tau\) and the Levin-Peres-Wilmer theorem (see Appendix C), we expect the trapping time to be of order \(\tau\).