MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.