Online Publication Signal Processing Research Article http://werner.yellowcouch.org/Papers/sadvssip/
Other:  Papers, Dissertations, Presentations, Posters, Reports, Course notes, Proposals

Correlation between the inproduct and the sum of absolute differences is -0.8485 for uniform sampled signals on [-1:1]

Werner Van Belle1* - werner@yellowcouch.org, werner.van.belle@gmail.com

1- Personal Research; CH-9294 Basel, Switzerland

Abstract: While investigating relations between various comparators and the inproduct we found that the inproduct correlates strongly towards the absolute difference when the domain from which the values are taken come from a uniform distribution on [-1:1]. This useful relation might help to speed up block comparison in content databases and can be used as a valuable tool to estimate the inproduct based on the absolute difference and vice versa

Keywords: sum of absolute differences, sum of inproduct, landmark tracking, feature tracking
Reference: Werner Van Belle; Correlation between the inproduct and the sum of absolute differences is -0.8485 for uniform sampled signals on [-1:1]; Signal Processing; Yellowcouch Scientific; November 2006

1 Introduction

To compare two data-blocks (of size $ n$ ), two easy implementable techniques are widely used. The first is the summed inproduct (SIP), defined as $ \sum_{i=0}^{n-1}x_{i}y_{i}$ . The second one, termed the sum of absolute differences (SAD), is defined as $ \sum_{i=0}^{n-1}\vert x_{i}-y_{i}\vert$ . Depending on the application behind the comparison one might be favored over the other.

The absolute difference is a well known operator for block comparison within images and is one of the basic blocks used in MPEG coding [1]. It is often used for motion estimation by means of landmark detection [2,3,4,5] and many different hardware implementations of the absolute difference exist [6,7,8,9]. In general statistics, the absolute difference is also often used as a robust measure [10], with specialized application such as model evaluation of protein 3D structures [11].

In audio applications, the absolute difference could also be used, but for historical reasons, the standard inproduct seems to be favored, mainly because multiplication is a basic operation in digital filters [12]. The inproduct, and specifically convolution, has an interesting application in fuzzy pattern matching. There it is often used to find sub-patterns in a haystack of information. Convolution will then assess the correlation between every position and the pattern-to-be-found [13,14,15]. Since convolution itself can be efficiently implemented through a Fourier transform (or a sliding sliding window Fourier transform when the datasets are large), pattern matching becomes a faster operation than finding similar fragment by means of the absolute difference. To go somewhat into the details, we denote the Fourier transform as $ \mathcal{F}$ . On a block of size $ n$ it takes time complexity $ \mathcal{O}(n.$log$ _{2}n)$ [16]. The inproduct of two signals expressed in their frequency domain is the same as convolution of their information in the time domain [12]. As such, the function $ \mathcal{F}^{-1}(\mathcal{F}(A)\times\mathcal{F}(B)^{*})$ , in which $ \times$ denotes the inproduct and $ *$ denotes conjugation, will return a vector of which element $ j$ describes the correlation between signal $ A$ and signal $ B$ shifted $ j$ positions. This operation itself has time complexity $ \mathcal{O}\left(3n.\mbox{log}_{2}n+n\right)$ , which is much faster than the same process using an iteration of absolute differences, which would yield a time complexity of $ n^{2}$ .

As such, the two operations both have their advantages and disadvantages. The absolute difference can be quickly calculated, but it is difficult to optimize for many comparisons. The inproduct on the other hand is slower on individual comparisons, but has very efficient implementations for large volumes.

Aside from these trade-offs, both metrics behave very different. The sum of absolute differences will be small for similar blocks, while the inproduct instead will be large. Some other subtitles arise as well: the absolute difference is independent of any constant added to both vectors since $ \left\vert(x+c)-(y+c)\right\vert=\left\vert x-y\right\vert$ . The inproduct does not have such a property: $ (x+c)(y+c)$ and will provide different results for any two same values: $ a.a\neq b.b$ when $ a\neq b$ . In other words the strength of the reported similarity depends on the strength of the values themselves. Actually, the inproduct itself is strictly speaking not a metric since $ d(X,X)\neq0$ for most values of $ X$ .

Notwithstanding their completely different mathematical behavior, both are often used in very similar contexts and therefore, we became interested to understand the relation between a number of well known comparators such as the summed inproduct and the sum of absolute differences. This could make it possible to predict one in function of the other.

2 Empirical Testing

To study the relations between various comparators we created $ m$ data-blocks, each containing two vectors $ X_{j}$ and $ Y_{j}$ . The variables $ X$ and $ Y$ , both of size $ n$ and element from $ \mathbb{R}^{n}$ , were randomly sampled from the same multi-variate distribution. Based on such test vectors we measured the spearman rank order and linear pearson correlation. $ x_{i}$ and $ y_{i}$ annotate the elements of $ X$ and $ Y$ , with the variables $ x$ and $ y\in[l,h]\cap\mathbb{R}$ . americanFor 8-bit signed integers, $ x$ and $ y$ ranges within [-127,128], and for 16 bit signed integers the values come from [-32767,32768]. americanWe do not take into account the discrete nature of integers and will work with real numbers taken from $ \mathbb{R}$ . americanAll $ x$ and $ y$ values were drawn from the same distribution, which could be normal or uniform distributed.

All comparators are set up as a summation of some underlying operator $ \theta:\mathbb{R}^{2}\rightarrow\mathbb{R}$, which could be one of the following 6:

$\displaystyle \theta_{\left\vert-\right\vert}(x,y)=\vert x-y\vert$ (1)
$\displaystyle \theta_{\times}(x,y)=x.y$ (2)
$\displaystyle \theta_{da}(x,y)=\vert x\vert-\vert y\vert$ (3)
$\displaystyle \theta_{-}(x,y)=x-y$ (4)
$\displaystyle \theta_{\left\vert da\right\vert}(x,y)=\left\vert\left\vert x\right\vert-\left\vert y\right\vert\right\vert$ (5)
$\displaystyle \theta_{en}(x,y)=xy+(1-x)(1-y)$ (6)

The first operator $ \theta_{\left\vert-\right\vert}$ is the absolute difference. The second operator $ \theta_{\times}$ is the multiplication. The third operator $ \theta_{-}$ will provide us with insight on the relation between the absolute difference and the basic difference. The fourth operator $ \theta_{da}$ investigates the impact of signed to unsigned conversion in a comparison process and the last operator. $ \theta_{en}$ takes the inverse of the signal and puts it back into the equation as an attempt to balance the inequality that occurs when comparing identical couples with a different value.

The multidimensional comparator $ \Theta_{\theta}$ , based on $ \theta$ is defined as

$\displaystyle \Theta_{\theta}:\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}\qquad\Theta_{\theta}(X,Y)=\sum_{i=0}^{n-1}\theta(x_{i},y_{i})$

We tested the relations between every pair of comparators using $ m=10^{4}$ sequences each of $ n=10^{3}$ samples. The values for $ x$ and $ y$ were first drawn from a uniform distribution between $ -1$ and $ 1$ and then from a normal distribution. The random generators are ran2 and gasdev from [17]. In all cases, both the linear Pearson and spearman rank order correlations were similar. The programs to measure the correlations can be found in section appendix.

Table 1: The correlation coefficient between various block comparators, using $ 10^{4}$ vectors, each with $ 10^{3}$ values. Left) values uniformly sampled from $ [-1:1]$ . Right) values sampled from a normal distribution with mean 0 and width $ 1$ .
  uniform distribution normal distribution
$ r$ $ \Theta_{-}$ $ \Theta_{da}$ $ \Theta _{\left \vert-\right \vert}$ $ \Theta_{\left\vert da\right\vert}$ $ \Theta _{\times }$ $ \Theta_{en}$ $ \Theta_{-}$ $ \Theta_{da}$ $ \Theta _{\left \vert-\right \vert}$ $ \Theta_{\left\vert da\right\vert}$ $ \Theta _{\times }$ $ \Theta_{en}$
$ \Theta_{-}$ 1 0 0 0 0 0 1 0 0 0 0 0
$ \Theta_{da}$   1 0 0 0 0   1 0 0 0 0
$ \Theta _{\left \vert-\right \vert}$     1 -0.23 -0.83 -0.53     1 -0.53 -0.65 -0.53
$ \Theta_{\left\vert da\right\vert}$       1 0 0       1 0 0
$ \Theta _{\times }$         1 0.63         1 0.82
$ \Theta_{en}$           1           1

Table 1 presents our findings: none of the correlations are useful to predict one in function of the other, except one: when working with uniform distributed samples, the inproduct anti-correlates strongly towards to absolute difference. This should make it possible to estimate one in function of the other, however before we do so, we would like to verify whether this correlation is correct and if so, what its exact value is.

3 Correlation estimate between the inproduct and the sum of absolute differences

We now assume that both vectors $ X$ and $ Y$ are uniform distributed within range $ [l,h]$ , with $ h>l$ and $ h>0$ . $ t$ denotes the size of the interval ($ h-l$ ). The comparators $ \Theta _{\times }$ and $ \Theta _{\left \vert-\right \vert}$ , both depending on $ X$ and $ Y$ , will now be considered to be variables themselves. The correlation between them, $ r\left(\Theta_{\times},\Theta_{\left\vert-\right\vert}\right)$ , is given by

$\displaystyle \frac{\mathbb{E}[\Theta_{\times}.\Theta_{\left\vert-\right\vert}]... ...{\left\vert-\right\vert}^{2}]-\mathbb{E}[\Theta_{\left\vert-\right\vert}]^{2}}}$ (7)

Under the assumption that the various sample positions are independent from each other, one can easily show that $ r\left(\Theta_{\times},\Theta_{\left\vert-\right\vert}\right)=r\left(\theta_{\times},\theta_{\left\vert-\right\vert}\right)$ .

$\displaystyle \frac{\mathbb{E}[\theta_{\times}\theta_{\left\vert-\right\vert}]-... ...{\left\vert-\right\vert}^{2}]-\mathbb{E}[\theta_{\left\vert-\right\vert}]^{2}}}$

This reduces the 5 estimates we need to $ \mathbb{E}[x.y]$ , $ \mathbb{E}[\vert x-y\vert]$ , $ \mathbb{E}[\left(x.y\right)^{2}]$, $ \mathbb{E}[(x-y)^{2}]$ and $ \mathbb{E}[x.y.\vert x-y\vert]$. We will now determine those 5 values.

3.1 Estimate of $ \vert x-y\vert$

Estimates of a variable $ T$ can be calculated from probability functions as follows ($ p$ is the probability distribution function of the variable $ T$)

$\displaystyle \mathbb{E}[T]=\int_{-\infty}^{+\infty}x.p(x)dx$

To calculate the probability distribution function of $ \vert x-y\vert$ with both $ x$ and $ y$ uniform distributions over $ [l,h]$ , we must first obtain the probability function of $ x-y$ , which is given by [18]:

   PDF$\displaystyle _{x-y}(u)=\begin{cases} \frac{t-u}{t^{2}} & \mbox{for }u\in[0,t]\\ \frac{t+u}{t^{2}} & \mbox{for }u\in[-t,0]\end{cases}$

Since this probability distribution is symmetrical around $ u=0$ (the means of the two uniform distribution has been subtracted), we would get an expected value of 0, but then we would forget to take into account the absolute difference. englishThe absolute difference will flip the probability of all values below zero over the vertical axis and add them there. This will result in an increased slope to the right and a probability density of 0 for negative values [19].

Figure 1: PDF of $ \vert x-y\vert$ when $ l=-1$ and $ h=2$
\includegraphics[width=0.5\textwidth]{pdfad}

PDF$\displaystyle _{\vert x-y\vert}(u)=\begin{cases}2\frac{t-u}{t^{2}} & \mbox{for }u\in[0,t]\\ 0 & \mbox{otherwise}\end{cases}$ (8)

Figure 1 plots eq.8. englishThe expectancy can now be calculated

$\displaystyle \mathbb{E}[\left\vert x-y\right\vert]=\int_{0}^{h-l}2u\frac{t-u}{t^{2}}du=\frac{t}{3}$ (9)

Testing this empirically gives the following values: $ \left[0:256\right]\rightarrow85.2197$ , $ \left[0:65536\right]\rightarrow21841$, $ \left[-128,128\right]\rightarrow85.5316$ , $ \left[-1,1\right]\rightarrow0.666846$, $ \left[-0.25,0.6\right]\rightarrow0.282795$and $ \left[-32768,32768\right]\rightarrow21851.8$. Which is consistent to the above formula.

3.2 Estimate of $ \vert x-y\vert^{2}$

Given that for any function $ g:\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle \mathbb{E}[g(x)]=\int_{-\infty}^{+\infty}g(x)f(x)dx$ (10)

we can calculate $ \mathbb{E}[\vert x-y\vert^{2}]$ based on the previous probability density function (8) as

$\displaystyle \mathbb{E}[\vert x-y\vert^{2}]=\int_{0}^{h-l}2u^{2}\frac{t-u}{t^{2}}du=\frac{t^{2}}{6}$ (11)

Testing this empirically gives the following values: $ \left[0:256\right]\rightarrow10891.4$ , $ \left[0:65536\right]\rightarrow7.17436.10^{8}$, $ \left[-128,128\right]\rightarrow10918.2$ , $ \left[-1,1\right]\rightarrow0.665828$, $ \left[-0.25,0.6\right]\rightarrow0.120234$ and $ \left[-32768,32768\right]\rightarrow7.14998.10^{8}$ . Which is close to the results as given by eq. 11.

3.3 Estimate of $ x.y$

To determine $ \mathbb{E}[x.y]$ we will calculate the probability distribution function of $ x.y$ , which might appear as taking the long road when the probability distribution of uniform products on $ [0:1]$ is already known [20]. However, we will later on needs this probability distribution on $ [l:h]$ to determine $ \mathbb{E}[\left(x.y\right)^{2}]$ and $ \mathbb{E}[x.y\vert x-y\vert]$ and we can now introduce the technique we will also use in section 3.5.2.

The probability density function of $ x.y$ is defined as the differential of the cumulative probability function, which in turn is defined as

   CDF$\displaystyle _{x.y}(z)=Pr[x.y<z]$

Figure 2: 3D plot of $ x.y$ . The left plot has a cutoff value of $ z=1$ . The middle and right plots are cut off at $ z<0.5$ and $ z<0.25$
\includegraphics[width=0.3\textwidth]{xyz1} \includegraphics[width=0.3\textwidth]{xyz2} \includegraphics[width=0.3\textwidth]{xyz3}

Figure 2 illustrates how to find the number of values (of $ x.y$ ) located below a fixed $ z$ . The surface area that is not cut off at $ z$ directly reflects the probability that a value below $ z$ can be chosen because both $ x$ and $ y$ are uniformly distributed. Since the isoline of $ z$ is located at $ y=\frac{z}{x}$ , various forms of $ \int\frac{z}{x}dx$ can be combined. $ \int\frac{z}{x}dx$ suffers from a discontinuity at 0 when $ l.h<0$ and its calculation in this particular context is further complicated with a sudden quadrant-change of the isoline when $ z$ becomes negative. In which case quadrant 1 and 3 no longer contain the isoline. Instead, quadrant 2 and 4 will contain it (see figure 3 for an illustration). To approach this problem, we divided the calculation of CDF$ _{x.y}$ into three branches. The first with $ l>0$ ; The second with $ l<0\wedge z>0$ and the last with $ l<0\wedge z<0$ .

Figure 3: 2D plot of the isoline with $ xy=z$ Left) $ z=1$ , when $ z>0$ we are interested in the area below the curve (towards the x-axis). Right) $ z=-1$ ; when $ z<0$ we are interested in the area outside the curve (farthest away from the x-axis). Only there will we find values that are smaller than $ -1$ .
\includegraphics[width=0.5\textwidth]{xy1} \includegraphics[width=0.5\textwidth]{xy2}

Aside from these standard complications, we must also limit our $ x$ and $ y$ values to the range $ [l:h]$ . This restricts the maximal surface area we can find and requires a piecewice approach. We start out with a general solutions for rectangles originating in $ \left(0,0\right)$ and ending at a specific point. We have the following 4 sections:

\begin{displaymath} \begin{array}{cc} S_{1}:\, x,y\in[0:h,0:h] & S_{2}:\, x,y\in... ... S_{3}:\, x,y\in[0:l,0:l] & S_{4}:\, x,y\in[0:h,0:l]\end{array}\end{displaymath}

Figure 4: Decomposition of the area $ [l:h,l:h]$ in 4 sections. Left) when $ l>0$ . Right) when $ l<0$ .
\includegraphics[width=0.5\textwidth]{sections}

Every section forms the two dimensional bounds (on $ x$ and $ y$ ) for the integral $ \int\frac{z}{x}dx$ , and depending on the sign of $ l.h$ they wil be added or substracted to/from each other. Figure 4 presents this graphically. When $ l.h$ is positive we need to subtract $ S_{2}$ and $ S_{4}$ , otherwise we need to add them. $ S'_{x}$ is used to denoted the size of area $ S_{x}$ intersected with the area below the isoline. The cumulative distribution function is now defined as

CDF$\displaystyle _{x.y}=\begin{cases}S_{1}'+S'_{3}-S'_{2}-S'_{4} & \mbox{for }l.h\geq0\\ S'_{1}+S'_{2}+S'_{3}+S'_{4} & \mbox{for }l.h<0\end{cases}$ (12)
Given that area $ S_{2}$ and $ S_{4}$ will be the same, even when the isoline cuts it, ( $ \frac{z}{x}$ is symmetrical over the line $ x=y$), we also have

CDF$\displaystyle _{x.y}=\begin{cases}S_{1}'+S'_{3}-2S'_{2} & \mbox{for }l.h\geq0\\ S'_{1}+S'_{3}+2S'_{2} & \mbox{for }l.h<0\end{cases}$ (13)
To calculate the intersection between the surface area below (or above) $ \frac{z}{x}$ and one of the above sections, we will create a general solution, relying on a variable $ c$ , forming the maximum value on the x-axis and $ m$ , forming the maximum value on the y-axis. Both $ c$ and $ m$ are assumed to be positive. Later on we will replace $ c$ with either $ l$ or $ h$ depending on the situation called for. Notation-wise: $ S'_{c,m}$ is the area below the isoline limited by $ c$ (horizontally) and $ m$ (vertically).

$\displaystyle S'_{c,m}(z)=\int_{0}^{c}$min$\displaystyle \{\frac{z}{x},m\} dx$

Figure 5: Limiting the possible $ y$ value leads to a piecewise continue function.
\includegraphics[width=0.5\textwidth]{xyclip}

$ S'_{c,m}$ can be determined by first obtaining the x-point where the hyperbole crosses the top line of our box, which happens at position $ x=\frac{z}{m}$. When $ z$ and $ m$ are positive, this point will always be larger than 0. When $ z>c.m$ , the intersection will happen outside $ c$ , in which case the surface area will be $ c.m$ . When $ z<c.m$ we need to integrate $ \int_{0}^{\frac{z}{m}}mdx$ and $ \int_{\frac{z}{m}}^{c}\frac{z}{x}dx$ (See figure 5 for an illustration), which gives

$\displaystyle S'_{c,m}(z)=\begin{cases}z(1+\mbox{ln}\frac{c.m}{z}) & \mbox{for }z<c.m\\ c.m & \mbox{for }z\geq c.m\end{cases}$ (14)
(14) provides the surface area of positions with a multiplied value $ x.y$ below a specific value $ z$ , when $ x\in[0:c]$ and $ y\in[0:m]$ . We now use (14) to obtain cumulative probabilities for $ l.h$ positive and negative.

3.3.1 Cumulative probability when $ l.h$ is positive

The cumulative probability function (13) requires us to calculate the different sections based on (14) with $ S'_{1}=S'_{h,h}$ ; $ S'_{2}=S'_{l,h}$ and $ S'_{3}=S'_{l,l}$ . Since (14) appears to be discontinue at position $ c.m$ we split the cumulative probability function in 4 segments.

When $ z<l^{2}$ the cumulative probability is 0 because there can be no values $ x$ and $ y$ , both larger than $ l$ that can lead to a multiple that is smaller than $ l^{2}$ .

When $ z\in[l^{2},lh]$ we have

CDF$\displaystyle _{x.y}(z)$ $\displaystyle =$ $\displaystyle z+z.$ln$\displaystyle \frac{h^{2}}{z}+l^{2}-2z-2z.$ln$\displaystyle \frac{h.l}{z}$  
  $\displaystyle =$ $\displaystyle l^{2}+z($ln$\displaystyle z-2$ln$\displaystyle l-1)$ (15)
Equation 15, as expected, evaluates to 0 when $ z=l^{2}$ . If $ z=lh$ , it evaluates to $ l(l+h.$ln$ h-$ln$ l-h)$ english. When $ z\in[lh,h^{2}]$ we have

CDF$\displaystyle _{x.y}(z)=z(1+2$ln$\displaystyle h-$ln$\displaystyle z)+l^{2}-2hl$ (16)
When $ z=lh$ (16) evaluates to $ l(l+h.$ln$ h-$ln$ l-h)$ , which is consistent with eq. 15.

When $ z>h^{2}$ we have

CDF$\displaystyle _{x.y}(z)=h^{2}+l^{2}-2hl=t^{2}$ (17)
which is indeed the surface area of the square $ [l:h,l:h]$ .

Figure 6: $ PDF_{xy}(z)$Left) with $ l=1$ and $ h=3$ . Right) with $ l=-1$ and $ h=3$
\includegraphics[width=0.36\textwidth]{pdfxylhpos}\includegraphics[width=0.64\textwidth]{pdfxylhneg}

(15), (16) and (17) are the non-normalized cumulative distribution functions americanwhen $ l.h>0$. Given the maximum surface area (17), we can divide and differentiate them all to provide us with the proper probability distribution (illustrated in figure 6). We conclude that, when $ l.h>0$ :

PDF$\displaystyle _{x.y}(z)=\begin{cases}\frac{\mbox{ln}z-2\mbox{ln}l}{t^{2}} & \mb... ...mbox{ln}z}{t^{2}} & \mbox{for }z\in[lh,h^{2}]\\ 0 & \mbox{otherwise}\end{cases}$ (18)

3.3.2 Cumulative probability when $ lh$ is negative

When $ l<0\wedge h>0$ the result is somewhat more complex. Instead of subtracting $ 2S_{2}$ , we need to add them. The interesting thing is that neither $ S_{2}$ nor $ S_{4}$ will intersect with $ \frac{z}{x}$ , when $ z>0$ . However, as soon as $ z<0$ the situation is different. (depicted in fig. 3). Therefore we further branch the calculation.

3.3.2.1 z>0

When $ z\geq0$ we have $ -lh$ as surface area for $ S_{2}$ and $ S_{4}$ .

$\displaystyle S'_{2,4}(z)=-l.h$   for $\displaystyle z\geq0$ (19)
The surface area for $ S_{1}$ is

$\displaystyle S'_{1}(z)=\begin{cases}z(1+2\mbox{ln}h-\mbox{ln}z) & \mbox{for }z\in[0,h²]\\ h^{2} & \mbox{for }z>h^{2}\end{cases}$ (20)
The surface area for $ S_{3}$ is

$\displaystyle S'_{3}(z)=\begin{cases}z(1+2\mbox{ln}(-l)-\mbox{ln}z) & \mbox{for }z\in[0,l²]\\ l² & \mbox{for }z>l^{2}\end{cases}$ (21)
The logarithm in (21) uses $ -l$ because $ l$ is negative and the general form in (14) requires a positive sign. This does however not change the surface area.

3.3.2.2 z<0

When $ z<0$ we are interested in the outside of the function $ \frac{z}{x}$ , which is to be found in $ S_{2}$ and $ S_{4}$ . Since the area below the curve matches that as if $ l$ , $ h$ and $ z$ were positive, we get surface area $ -z(1+ln\,\frac{-lh}{-z})$ 1. As such, the remaining surface area must then be

$\displaystyle S'_{2,4}(z)=\begin{cases}-l.h+z(1+ln\frac{lh}{z}) & \mbox{for }z\in[lh,0]\\ -l.h & \mbox{for }z<l.h\end{cases}$ (22)
Because $ x.y$ can never be smaller than 0 in quadrants $ S_{1}$ and $ S_{3}$ , we get 0 for them.

$\displaystyle S'_{1,3}(z)=0$   for $\displaystyle z\in]-\infty,0]$ (23)
Combining (19) to (23) gives the non-normalized cumulative probability distribution:

CDF$\displaystyle _{x.y}(z)=\begin{cases}-2lh & z<l.h\\ 2(-lh+z(1+\mbox{ln}\frac{l.... ...+\mbox{ln}\frac{h^{2}}{z}) & z\in[l^{2},h^{2}]\\ l²-2lh+h² & z>h^{2}\end{cases}$ (24)
Differentiating (24) gives the probability distribution function when $ l<0$ and $ h>0$ . We again divided the CDF with the total expected area, being $ t^{2}$ , so when $ l.h<0$ we have the following probability distribution function:

PDF$\displaystyle _{x.y}(z)=\begin{cases}\frac{2\mbox{ln}h+2\mbox{ln}l-2\mbox{ln}z}... ...x{ln}h-\mbox{ln}z}{t^{2}} & z\in[l^{2},h^{2}]\\ 0 & \mbox{otherwise}\end{cases}$ (25)
Figure 6 shows an example of such distribution. When working out the various cases we made the silent assumption that $ \vert l\vert<h$ . The result however does not change at all. americanEq. 25 has some overlapping cases, so the right subset needs to be chosen depending on whether $ \vert l\vert>h$ or whether $ \vert l\vert<h$ .

3.3.3 The estimate of $ x.y$

The estimate of $ x.y$ is calculated as

$\displaystyle \mathbb{E}[x.y]=\int_{-\infty}^{+\infty}z.$PDF$\displaystyle _{xy}(z)dz$

3.3.3.1 when $ l.h>0$

$\displaystyle \mathbb{E}[x.y]$ $\displaystyle =$ $\displaystyle \int_{l^{2}}^{lh}z\frac{\mbox{ln}z-2\mbox{ln}l}{(h-l)^{2}}dz$ (26)
    $\displaystyle +\int_{lh}^{h^{2}}z\frac{2\mbox{ln}h-\mbox{ln}z}{(h-l)^{2}}dz$ (27)
  $\displaystyle =$ $\displaystyle \left(\frac{h+l}{2}\right)^{2}$ (28)

3.3.3.2 when $ l.h<0$

$\displaystyle \mathbb{E}[x.y]$ $\displaystyle =$ $\displaystyle \int_{lh}^{0}z\frac{2\mbox{ln}h+2\mbox{ln}l-2\mbox{ln}z}{(h-l)^{2}}dz$  
    $\displaystyle +\int_{0}^{l^{2}}z\frac{2\mbox{ln}h+2\mbox{ln}(-l)-2\mbox{ln}z}{(h-l)^{2}}dz$  
    $\displaystyle +\int_{l^{2}}^{h^{2}}z\frac{2\mbox{ln}h-\mbox{ln}z}{(h-l)^{2}}dz$  
  $\displaystyle =$ $\displaystyle -\frac{h^{2}l^{2}}{2(h-l)^{2}}+\frac{l^{4}(1+2\mbox{ln}h-2\mbox{ln}l)}{2(h-l)^{2}}$  
    $\displaystyle +\frac{h^{4}-l^{4}+4l^{4}(\mbox{ln}l-\mbox{ln}h)}{4(h-l)^{2}}$  
  $\displaystyle =$ $\displaystyle \left(\frac{h+l}{2}\right)^{2}$ (29)
Since (28)==(29) we have in the general case:

$\displaystyle \mathbb{E}[x.y]=\left(\frac{h+l}{2}\right)^{2}$ (30)

3.4 Estimate of $ \left (x.y\right )^{2}$

The probability density function of $ x.y$ is given in (18) and (25).

3.4.1 When $ lh>0$

$\displaystyle \mathbb{E}[\left(x.y\right)^{2}]$ $\displaystyle =$ $\displaystyle \int_{l^{2}}^{h^{2}}\frac{z^{2}}{t^{2}}\begin{cases} ln\frac{z}{l^{2}} & z\in[l^{2},lh]\\ ln\frac{h²}{z} & z\in[lh,h^{2}]\end{cases}d_{z}$  
  $\displaystyle =$ $\displaystyle \int_{l^{2}}^{lh}\frac{\mbox{ln}z-2\mbox{ln}l}{t^{2}}z^{2}d_{z}$  
    $\displaystyle +\int_{lh}^{h^{2}}\frac{2\mbox{ln}h-\mbox{ln}z}{t^{2}}z^{2}d_{z}$  
  $\displaystyle =$ $\displaystyle \frac{l^{6}-2l^{3}h^{3}+h^{6}}{9(h-l)^{2}}$  
  $\displaystyle =$ $\displaystyle \left(\frac{h^{3}-l^{3}}{3t}\right)^{2}$ (31)

3.4.2 When $ lh<0$

The situation when $ lh<0$ is discussed below. We first start with the case where $ \vert l\vert<h$ . This gives us

$\displaystyle \mathbb{E}[\left(x.y\right)^{2}]$ $\displaystyle =$ $\displaystyle \int_{l.h}^{h^{2}}2\frac{z^{2}}{t^{2}}\begin{cases} ln\frac{z}{l.... ...ac{l.h}{z} & z\in[0,l^{2}]\\ ln\frac{l}{z} & z\in[l^{2},h^{2}]\end{cases}d_{z}$  
  $\displaystyle =$ $\displaystyle \int_{lh}^{0}z^{2}\frac{-2\mbox{ln}lh+2\mbox{ln}z}{t^{2}}d_{z}$  
    $\displaystyle +\int_{0}^{l^{2}}z^{2}\frac{2\mbox{ln}l-2\mbox{ln}z+2\mbox{ln}h}{t^{2}}d_{z}$  
    $\displaystyle +\int_{l^{2}}^{h^{2}}z^{2}\frac{2\mbox{ln}h-\mbox{ln}z}{t^{2}}d_{z}$  
  $\displaystyle =$ $\displaystyle \frac{-2l^{3}h^{3}+l^{6}+h^{6}}{9t^{2}}$  
  $\displaystyle =$ $\displaystyle \left(\frac{h^{3}-l^{3}}{3t}\right)^{2}$ (32)
When $ \vert l\vert>h$ we have the same result.

Since (31)==(32), we conclude that

$\displaystyle \mathbb{E}\left[(x.y)^{2}\right]=\left(\frac{h^{3}-l^{3}}{3t}\right)^{2}$ (33)
Testing this empirically gives the following values: $ \left[0,1\right]\rightarrow0.110476$ , $ \left[0:256\right]\rightarrow4.774.10^{8}$, $ \left[0:65536\right]\rightarrow2.0536.10^{18}$, $ \left[-128,128\right]\rightarrow2.9834.10^{7}$ , $ \left[-1,1\right]\rightarrow0.11124$ , $ \left[64,320\right]\rightarrow1791433841.777777778$, $ \left[-0.25,0.6\right]\rightarrow0.00830775$and $ \left[-32768,32768\right]\rightarrow1.2893.10^{17}$.

3.5 Estimate of $ x.y\left \vert x-y\right \vert$

If we define $ a$ and $ b$ to be the translation and scaling of $ x$ and $ y$ as follows

$\displaystyle a=\frac{x-l}{t}\qquad b=\frac{y-l}{t}$

then $ a$ and $ b$ are uniform distributed over $ [0:1]$ . americanThe variable $ x$ (and $ y$ ) can also be defined in function of $ a$ as

$\displaystyle x=t.a+l\qquad y=t.b+l$ (34)

This substitution will make it possible to rewrite $ \mathbb{E}[x.y\vert x-y\vert]$

    $\displaystyle \mathbb{E}[x.y\vert x-y\vert]$  
  $\displaystyle =$ $\displaystyle \mathbb{E}[(t.a+l)(t.b+l)\vert t.a-t.b\vert]$  
  $\displaystyle =$ $\displaystyle t\mathbb{E}[(t²a.b+t.a.l+t.b.l+l²)\vert a-b\vert]$  
The estimates for $ t.a.l$ and $ t.b.l$ must be the same since they both are drawn from the same distribution.
$\displaystyle \mathbb{E}[x.y\vert x-y\vert]$ $\displaystyle =$ $\displaystyle t³\mathbb{E}[a.b\vert a-b\vert]$  
    $\displaystyle +2t^{2}l\mathbb{E}[a\vert a-b\vert]$  
    $\displaystyle +tl²\mathbb{E}[\vert a-b\vert]$ (35)
The estimate for $ \vert a-b\vert$ is $ \frac{1}{3}$ , as given in (9) (with $ h$ and $ l$ equal to 1 and 0 respectively). $ \mathbb{E}\left[a.b.\left\vert a-b\right\vert\right]$ and $ \mathbb{E}\left[a\left\vert a-b\right\vert\right]$ must be determined further.

3.5.1 Estimating $ \mathbb{E}[a\vert a-b\vert]$

$ \mathbb{E}[a\vert a-b\vert]$ becomes

$\displaystyle \mathbb{E}[a\vert a-b\vert]=\mathbb{E}[a^{2}]-\mathbb{E}[ab]$   with$\displaystyle \, a>b$

$ a$ and $ b$ are uniform distributions, as such $ \mathbb{E}[a^{2}]=\mathbb{E}[b^{2}]=\frac{1}{3}$ . The estimates for $ a-b$ (under condition that $ a>b$ ) and $ b-a$ (under condition that $ b>a)$ will be the same:

$\displaystyle \mathbb{E}[a.b\vert a>b]=\int_{0}^{1}-z$ln$\displaystyle z\, dz=\frac{1}{4}$ (36)

Without the condition that $ a>b$ we need to double the estimate of (36)