# Counting frequencies of occurrence of patterns within a sequence using harmonic analysis?

Assume that we are given a sequence $\mathbf x := X_1,\dots,X_n \in \mathbb N^n$ for some $n \in \mathbb N$. I am interested in calculating the frequency of occurrence of some fixed sequence $\mathbf y:=Y_1,\dots,Y_m \in \mathbb N^m$ $m \leq n \in \mathbb N$ within $\mathbf x$.

That is, I would like to calculate $$\frac{1}{n-m+1}\sum_{j=1}^{n-m+1}\mathbb I\{X_j,\dots,X_{j+m} = \mathbf y\}$$ where $\mathbb I\{u\} = 1$ if $u$ is true and it's zero otherwise.

For example if $\mathbf x= 00110101$ and $\mathbf y = 01$ then the frequency of $\mathbf y$ in $\mathbf x$ would be $\frac{3}{7}$.

I wonder if there is an obvious way to reformulate this using harmonic analysis.

How about the simpler case where $\mathbf y \in \mathbb N$ is a simply a natural number?

Thanks!

-