# Text Indexing for Regular Expression Matching
## 3 A Regular Expression Index
### Querying Matches via Graph Traversal
#### 3.4.2 Preserving High Probability of Success  
We know that our matrix-vector multiplication algorithm from [20] succeeds with probability \(1-\frac{1}{|T|^{z}}\) for some \(\varepsilon>0\). Our algorithm performs matrix-vector multiplication up to \(\frac{|p|}{\tau}\leq|p|\) times. We assume the correctness of these matrix multiplications is independent. In the worst case, each of these has to be correct for our final answer to be correct. The probability that these are all correct is given by  
\[\bigg{(}1-\frac{1}{|T|^{\varepsilon}}\bigg{)}^{\frac{|p|}{\tau}}\geq 1-\frac{|p| }{\tau}\cdot\frac{1}{|T|^{\varepsilon}}\quad\text{ for }\ \frac{|p|}{\tau}>1\ \text{ and }\ \frac{1}{|T|^{\varepsilon}}<1.\]  
Using the assumption that \(|p|\leq|T|^{z}\), this is bound below by \(1-\frac{1}{|T|^{\varepsilon-z}}\). We will aim to preserve success whp by 'amplifying' \(\varepsilon\) to some \(\varepsilon^{\prime}>z\). The technique we will use to do this is repeating each matrix multiplication a sufficient number (denoted by \(k\)) of times and using the most frequently resulting vector (the mode) as the solution.  
Let \(X_{i}\) be the random variable which is 1 if the multiplication on trial \(i\) is correct and 0 otherwise. Let \(1-\frac{1}{|T|^{z}}=:q>\frac{1}{2}\) be the probability with which the original matrix-vector multiplication algorithm is correct. The probability that the mode is correct is greater or equal to the probability that the correct solution is outputted at least \(\frac{k}{2}\) times. We write the latter quantity as one minus the probability that the correct answer gets outputted less than half the time. Applying Chernoff bound, we get  
\[1-Pr\Bigg{(}\sum_{i=1}^{k}X_{i}\leq\bigg{\lfloor}\frac{k}{2}\bigg{\rfloor} \Bigg{)}\geq 1-e^{-\frac{k}{2q}(q-\frac{1}{2})^{2}}.\]  
Recall that we want our probability to be at least \(1-\frac{1}{|T|^{\varepsilon^{\prime}}}\) for some \(\varepsilon^{\prime}>z\). Therefore we set the right-hand-side to \(1-\frac{1}{|T|^{\varepsilon^{\prime}}}\) and solve for \(\varepsilon^{\prime}\) to obtain  
\[\varepsilon^{\prime}=\frac{k}{2q\ln|T|}\bigg{(}q-\frac{1}{2}\bigg{)}^{2}.\]Since we want \(\epsilon^{\prime}>z\), it suffices then that we find the number of trials \(k\) such that  
\[\frac{k}{2q\ln|T|}\left(q-\frac{1}{2}\right)^{2}>z\qquad\text{or, equivalently}\qquad k>\frac{2 qz\ln|T|}{\left(q-\frac{1}{2}\right)^{2}}.\]  
For \(|T|^{\epsilon}>2\) we can easily bound \(q\) away from \(1/2\), making \(2 qz\ln|T|/(q-1/2)^{2}=\Theta(z\log|T|)\). Hence, repeating each matrix multiplication \(k=\Theta(z\cdot\log|T|)\) times and taking the mode provides the desired \(1-1/poly(|T|)\) probability of success.  
**Obtaining Starting and Ending Positions.** For each precomputed solution, we consider the edges reversed and the corresponding adjacency matrix as being precomputed. After constructing the final solution graph, we reverse all of its edges and add a single source vertex \(t\) and edges \(\{(v_{i}^{2},t)\mid 1\leq i\leq|T|+1\}\) (see Figure 4). We call this graph \(G^{R}\). Using the same traversal techniques on \(G^{R}\) as used on \(G\) yields the set of reachable starting vertices in \(V_{1}\).