Large deviations for template matching between point processes. (English) Zbl 1068.60035

Assume \(X\) is a stationary ergodic process and \(Y\) is a homogeneous Poisson point process. Let \(d\) be the Euclidean distance and denote \( X_a^b = X \cup [a,b)\). For \(t>0\), \(X_0^l \neq 0 \) and \(f\) nonincreasing define \(\rho_l(X_0^l, Y_t^{t+l}) = 1/l \sum_{y \in Y_t^{t+l}} f(d(y-t,X_0^l))\) and \(W_l(\theta, X, Y) = \inf \{t\geq 0 : \rho_l(X_0^l, Y_t^{t+l}) \geq \theta \}.\)
The author proves the large deviation principle for the waiting time \(W_l\) as \(l\) increases, in both cases: \(f\) is scalar and \(f\) is vector-valued. Furthermore, he gives a strong approximation for \(-\log P(W_l(\theta) =0)\). In the case where a certain mixing condition is met, the process \(X\), properly normalized, satisfies a central limit theorem and an a.s. invariance principle. The variance of the normal distribution is given for the case where \(X\) is a homogeneous Poisson process as well.


60F10 Large deviations
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)


waiting time
Full Text: DOI arXiv


[1] Abeles, M. and Gerstein, G. M. (1988). Detecting spatiotemporal firing patterns among simultaneously recorded single neurons. J. Neurophysiol. 60 909–924.
[2] Chi, Z. (2001). Stochastic sub-additivity approach to conditional large deviation principle. Ann. Probab. 29 1303–1328. · Zbl 1018.60026 · doi:10.1214/aop/1015345604
[3] Chi, Z., Rauske, P. L. and Margoliash, D. (2003). Pattern filtering for detection of neural activity, with examples from hvc activity during sleep in zebra finches. Neural Computation 15 2307–2337. · Zbl 1085.68618 · doi:10.1162/089976603322362374
[4] Comets, F. (1989). Large deviation estimates for a conditional probability distribution. Applications to random interaction Gibbs measures. Probab. Theory Related Fields 80 407–432. · Zbl 0638.60037 · doi:10.1007/BF01794432
[5] Daley, D. J. and Vere-Jones, D. (1988). An Introduction to the Theory of Point Processes . Springer, New York. · Zbl 0657.60069
[6] Dayan, P. and Abbott, L. F. (2001). Theoretical Neuroscience . MIT Press. · Zbl 1051.92010
[7] Dembo, A. and Kontoyiannis, I. (1999). The asymptotics of waiting times between stationary processes, allowing distortion. Ann. Appl. Probab. 9 413–429. · Zbl 0940.60033 · doi:10.1214/aoap/1029962749
[8] Dembo, A. and Kontoyiannis, I. (2002). Source coding, large deviations, and approximate pattern matching. IEEE Trans. Inform. Theory 48 2276–2290. · Zbl 1062.94020 · doi:10.1109/TIT.2002.800493
[9] Dembo, A. and Zeitouni, O. (1992). Large Deviations Techniques and Applications . Jones and Bartlett, Boston, MA. · Zbl 0793.60030
[10] Louie, K. and Wilson, M. A. (2001). Temporally structured replay of awake hippocampal ensemble activity during rapid eye movement sleep. Neuron 29 145–156.
[11] Nádasdy, Z., Hirase, H., Czurkó, A., Csicsvari, J. and Buzsáki, G. (1999). Replay and time compression of recurring spike sequences in the hippocampus. J. Neurosci. 19 9497–9507.
[12] Rio, E. (1995). The functional law of the iterated logarithm for stationary strongly mixing sequences. Ann. Probab. 23 1188–1203. JSTOR: · Zbl 0833.60024 · doi:10.1214/aop/1176988179
[13] Yang, E.-H. and Kieffer, J. C. (1998). On the performance of data compression algorithms based upon string matching. IEEE Trans. Inform. Theory 44 47–65. · Zbl 0905.94018 · doi:10.1109/18.650987
[14] Yang, E.-H. and Zhang, Z. (1999). On the redundancy of lossy source coding with abstract alphabets. IEEE Trans. Inform. Theory 45 1092–1110. · Zbl 0959.94014 · doi:10.1109/18.761253
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.