# Detecting Traffic Incidents Using Persistence Diagrams
## 3 Description of the Algorithm
Then there exist \(\mu_{j},\sigma_{j},\eta_{j}^{+}\), and \(\eta_{j}^{-}\) such that_  
\[\overline{d}_{j}\stackrel{{\mathbb{P}}}{{\longrightarrow}}\mu_{ j},\,s_{j}\stackrel{{\mathbb{P}}}{{\longrightarrow}}\sigma_{j}\]  
_as \(N\longrightarrow\infty\), and for all \(\varepsilon>0\),_  
\[\lim_{N\rightarrow\infty}\mathbb{P}[h_{j}\in(\eta_{j}^{-}-\varepsilon,\eta_{ j}^{+}+\varepsilon)]=1.\]  
Proof. : Define the random variable \(d_{j}\) on \(\Omega\) by  
\[d_{j}(\beta,\mathbf{y})=W(\beta,\beta\setminus\{\mathbf{y}\}\cup\{\mathbf{x}_ {j}\}).\]  
We have that \(d_{j,1},d_{j,2},...,d_{j,N}\stackrel{{ d}}{{=}}d_{j}\) are i.i.d. random variables. Since \(|\Omega|<\infty\) and there are no infinite points in \(\mathbf{D}\), \(d_{j}\) is bounded. The three limits are consequences of the Weak Law of Large Numbers, which requires a sequence of i.i.d. random variables with finite expectation. In particular, let \(\mu_{j}:=\mathbb{E}[d_{j}]<\infty\) and \(\sigma_{j}^{2}=\mathrm{Var}[d_{j}]<\infty\). Since the \(\{d_{jk}\}_{k=1}^{N}\) are i.i.d. with finite mean \(\mu_{j}\), by the Weak Law of Large Numbers,  
\[\overline{d}_{j}=\frac{1}{N}\sum_{k=1}^{N}d_{j,k}\stackrel{{ \mathbb{P}}}{{\longrightarrow}}\mu_{j}\]as \(N\to\infty\). To prove the second limit, we start by writing  
\[s_{j}^{2}=\frac{1}{N-1}\sum_{k=1}^{N}(d_{j,k}-\overline{d}_{j})^{2}=\frac{N}{N-1 }\left(\frac{1}{N}\sum_{k=1}^{N}d_{j,k}^{2}-\overline{d}_{j}^{2}\right). \tag{1}\]  
Since \(\{d_{j,k}^{2}\}_{k=1}^{N}\) are i.i.d with \(\mathbb{E}[d_{j,k}^{2}]=\sigma_{j}^{2}+\mu_{j}^{2}<\infty\), it follows from the Weak Law of Large Numbers that \(\frac{1}{N}\sum_{k=1}^{N}d_{j,k}^{2}\stackrel{{\mathbb{P}}}{{ \longrightarrow}}\sigma_{j}^{2}+\mu_{j}^{2}\) as \(N\) tends to infinity. Since we have established \(\overline{d}_{j}\stackrel{{\mathbb{P}}}{{\longrightarrow}}\mu_ {j}\) as \(N\to\infty\), it follows that \(\overline{d}_{j}^{2}\stackrel{{\mathbb{P}}}{{\longrightarrow}} \mu_{j}^{2}\) as \(N\) tends to infinity. Adding up the terms in (1), this means \(s_{j}\to\sigma_{j}\) in probability. For the third equation, first define  
\[\eta_{j}^{-}:=\sup\left\{\eta:\mathbb{P}[d_{j}\leq\eta]<\frac{1}{2}\right\}, \ \eta_{j}^{+}:=\inf\left\{\eta:\mathbb{P}[d_{j}\leq\eta]>\frac{1}{2}\right\}.\]  
For any \(\varepsilon>0\), we have \(\mathbb{P}[d_{j,k}>\eta_{j}^{+}+\varepsilon]=\alpha<1/2\). We can define \(b_{j,k}=1\) if \(d_{j,k}>\eta_{j}^{+}+\varepsilon\), and \(b_{j,k}=0\) otherwise. It follows that \(b_{j,1},b_{j,2},...,b_{j,N}\stackrel{{\text{iid}}}{{\sim}}\text {Bernoulli}(\alpha)\). Since \(h_{j}\) is the sample median of \(\{d_{j,k}\}_{k=1}^{N}\), it follows that  
\[\mathbb{P}[h_{j}>\eta_{j}^{+}+\varepsilon] \leq\mathbb{P}\left[\sum_{k=1}^{N}b_{j,k}>\frac{N}{2}\right]= \mathbb{P}\left[\sum_{k=1}^{N}b_{j,k}-N\alpha>\frac{N}{2}-N\alpha\right]\] Figure 2:0 Figure 2:1  
Since \(\frac{1}{2}-\alpha>0\), we apply the Weak Law of Large Numbers to \(b_{j,1},...,b_{j,N}\) to see that \(\lim_{N\to\infty}\mathbb{P}[h_{j}>\eta_{j}^{+}+\varepsilon]=0\). Similarly, we have \(\mathbb{P}[d_{j,k}<\eta_{j}^{-}-\varepsilon]=\delta<1/2\), Thus, if we instead define \(b_{j,k}=1\) if \(d_{j,k}<\eta_{j}^{-}-\varepsilon\), we have \(b_{j,1},b_{j,2},...,b_{j,N}\stackrel{{\text{iid}}}{{\sim}}\text {Bernoulli}(\delta)\). Much like what we had in (2), we find  
Figure 2:2  
Since \(\frac{1}{2}-\delta>0\), we again have from the Weak Law of Large Numbers applied to \(b_{j,1},...,b_{j,N}\) that \(\lim_{N\to\infty}\mathbb{P}[h_{j}<\eta_{j}^{-}-\varepsilon]=0\). **Remark 2**: _Since we are sampling from a discrete probability distribution, it is not guaranteed that the distribution producing the \(\{d_{j,k}\}\) has a true median. Hence we must settle for convergence of the sample median to some interval. In the case where there exists \(\eta\) such that \(\mathbb{P}[d_{j,k}\geq\eta],\mathbb{P}[d_{j,k}\leq\eta]\geq\frac{1}{2}\), then \(\eta_{j}^{+}=\eta_{j}^{-}=\eta\) and the sample median converges in probability to \(\eta\).