# Probability distribution of windowed cross-correlation

This question is in the context of time-delay estimation. Say I have a stationary Gaussian stochastic process $g$, and I know its autocorrelation function $R_g(\tau)$. To do time-delay estimation, I'm computing a windowed cross correlation between $g$ and a delayed version of it. In other words, $$g_1 = g(x-D) \\ \phi(\tau) = \int_{-T/2}^{T/2} g(x) g_1(x + \tau)$$ and I'm going to determine the delay by finding the maximum of $\phi$.

My question is, is it possible to get an expression for the probability distribution of $\phi$?

• $\{\phi(\tau)\}$ is a non-stationary nonGaussian random process. I doubt there is any simple answer (or even a rather complicated one) even for a fixed value of $\tau$. – Dilip Sarwate Feb 28 '12 at 21:38
• Are you truly performing autocorrelation, which is what you describe? That is, do you have one signal that you are correlating with itself at some time lag $\tau$? Most practical systems where you might want to calculate time-difference of arrival actually have two input signals with some deterministic component that is common to them. They might be corrupted by noise, but the common assumption is that the noise terms in each sample are jointly independent of each other and the signal components, so that can allow for some simplification. Can you describe your scenario more closely? – Jason R Feb 29 '12 at 2:09
• @Jason R - in my full problem, which is motion tracking in ultrasound images, I am concerned with additional noise on each signal, as well as other sources of corruption in the deterministic part of the signal. But I didn't want to complicate this question with that - here I'm simply wondering whether we can determine the distribution of the cross-correlation function, in as simple a scenario as I could devise. – Matt Feb 29 '12 at 15:58
• To clarify further, my signal $g$ is deterministic in that it remains the same for the same piece of tissue being imaged, but I model it as a stochastic process because the tissue microstructure that creates a scattered signal is semi-random. – Matt Feb 29 '12 at 16:04
• Also asked on stats.SE – Dilip Sarwate Mar 1 '12 at 21:54

Expanding on my comment, $\{\phi(\tau)\}$ is a non-stationary nonGaussian random process, and I doubt that there is any simple answer (or even a rather complicated one) for the probability density function of the random variable $\phi(\tau)$ for an arbitrary value of $\tau$. But, the (time-varying) mean function of the process is easy to calculate. We have

\begin{align*} E[\phi(\tau)] &= E\left[\int_{-T/2}^{T/2} g(t)g(t-D+\tau)\, \mathrm dt\right]\\ &= \int_{-T/2}^{T/2} E[g(t)g(t-D+\tau)]\, \mathrm dt\\ &= \int_{-T/2}^{T/2} R_g(\tau-D)\, \mathrm dt\\ &= T\cdot R_g(\tau-D) \end{align*}

where $R_g(\cdot)$ is the autocorrelation function of the input process $\{g(t)\}$. Note that it is not necessary that the input process be Gaussian for this to hold; wide-sense-stationarity is enough. Since autocorrelation functions have a peak at the origin, we see that $\phi(D)$ has the largest mean value. Also, the mean value decays away symmetrically about $D$: that is, $E[\phi(D+\epsilon)] = E[\phi(D-\epsilon)]$ and $$|E[\phi(\tau)]| \leq E[\phi(D)] = T\cdot R_g(0).$$

Finding the variance of $\phi(\tau)$ is a much messier calculation that may or may not be included in the paper cited by Charna (which is behind a paywall).

• Right, for variance you need to start looking at fourth moments of g, and of course it gets messier for higher moments. But from what I know of higher moments, it seems like you could derive all of them (though it would get messy), which made me wonder if there is a simple-ish expression for the distribution of $\phi$. As you suspect though, maybe there isn't. – Matt Mar 28 '12 at 21:18

I do not know the answer to your question, but perhaps this paper can help. I realize that you are not using single bit random waveforms, but the formulation on the distribution they calculated is fairly through.

"Probability distribution of the crosscorrelation function of finite-duration single-bit random waveforms"

Abstract The detection errors of a digital crosscorrelator, utilizing severely clipped, bandlimited Gaussian waveforms are investigated, and the probability distribution of the correlator output due to finite-duration waveforms and distortion by wideband Gaussian noise is derived and compared with experimental results.

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4235873

• Interesting paper. It is hard for me to see though how their derivations for single-bit functions could be extended for functions with a continuous range. – Matt Mar 28 '12 at 21:12