7.3.2      Inequalities

For many complex systems, analyzing the exact performance can be challenging and even analytically intractable. In many such situations, inequalities are used to bound the system performance. Such bounding techniques are frequently used in communications to derive closed form approximations for the performance of various systems. The closed form approximations clearly demonstrate the effect that changes in a certain parameter has on performance. These inequalities are also used in learning theory to study the problem of optimal model selection for a given training data. A detailed discussion on using inequalities and large deviation theory is given in Chapter 9. In this section, we discuss in brief some of the frequently used inequalities.

For a non-negative random variable $\mathcal{X}$ with mean ${\mu }_{\mathcal{X}}=E\left\{\mathcal{X}\right\}$ , the Markov inequality provides a bound on the tail probability and is given by

$\mathrm{Pr}\left(\chi \ge a\right)\le \frac{E\left\{\chi \right\}}{a}.$

(7.59)

Clearly, this inequality only provides meaningful results only when $a>{\mu }_{\mathcal{X}}$ . Even in that case, the bound is quite weak since it only uses the mean of the function to evaluate a bound on the tail probability. A tighter bound on the tail probability is given by the Chebychev inequality which uses both the mean ${\mu }_{\mathcal{X}}$ and the variance as ${\sigma }_{\mathcal{X}}^2$ as

$\mathrm{Pr}\left(\left|\chi -{\mu }_{\chi }\right|\ge a\right)\le \frac{{\sigma }_{\chi }^2}{a^2}$

(7.60)

The Chebychev inequality is obtained by applying the Markov inequality to ${\left(\mathcal{X}-{\mu }_{\mathcal{X}}\right)}^2$ .

Jensen’s inequality states that for a convex function g(·), the expected value of the function of a random variable is no smaller than the function of the expected value of that random variable, i.e.,

$g\left(E\left\{\chi \right\}\right)\le E\left\{g\left(\chi \right)\right\}$

(7.61)

The Union bound simply states that the probability of the union of certain events is lesser than the sum of the probabilities of the individual events,

$\mathrm{Pr}\left({\cup }_i{A}_i\right)\le {\displaystyle \sum _i\mathrm{Pr}\left(A_i\right)}$

(7.62)

The Schwarz inequality is given by

$\left|E\left\{\chi \mathcal{Y}\right\}\right|\le \sqrt{E\left\{{\chi }^2\right\}E\left\{{\mathcal{Y}}^2\right\}}$

(7.63)

The Chernoff bound is given by

$\begin{array}{lll}\mathrm{Pr}\left(\chi >a\right)\hfill & =\hfill & \mathrm{Pr}\left(e^{t\chi }>e^{ta}\right)\forall t>0\hfill \\ \hfill & \le \hfill & \frac{E\left\{e^{t\chi }\right\}}{e^{ta}}\left(\text{using}\text{Markov}\text{inequality}\right)\hfill \\ \Rightarrow \mathrm{Pr}\left(\chi >a\right)\hfill & \le \hfill & \underset{t>0}{\min }\frac{E\left\{e^{t\chi }\right\}}{e^{ta}}\hfill \end{array}$

(7.64)

Recognize that the tail probability fall of exponentially with the Chernoff bound but only in polynomial terms with the Chebychev inequality. On the other hand, while the Chebychev inequality is general enough to apply to the sum of dependent random variables, the Chernoff bound is only valid for the sum of independent random variables. Hoeffdings inequality generalizes the Chernoff bound to the case of arbitrary bounded random variables [7].

7.3.3      Functions of Multiple Random Variables

Let random variable Z = g(${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_n$ ). Then, the distribution of $\mathcal{Z}$ can be computed from the joint distribution of the random variables ${\mathcal{X}}_{i,i}=1,2,\dots n$ Depending on whether the random variables are continuous or discrete, several cases arise.

•  Random variables ${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_n$ and $\mathcal{Z}$ are continuous. In this case, the CDF of $\mathcal{Z}$ can be computed as

$F_Z\left(z\right){\displaystyle \underset{\left(x_1,\dots ,x_n\right):g}{\int }\cdots {\displaystyle \underset{\left(x_1,\dots x_n\right)\le z}{\int }f{\chi }_1,{\chi }_2,\dots {\chi }_n}}\left(x_1,x_2,\dots ,x_n\right)d{x}_{1}d{x}_2\dots d{x}_n,$

(7.65)

where the integral is over the n−tuples of (${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_n$ ) that are mapped by the function g to a value lesser than z. The PDF of $\mathcal{Z}$ can be computed by differentiating the CDF obtained in (7.65). While this same principle can be used in case the random variables are not continuous, it is also possible to directly compute the PMF of random variable $\mathcal{Z}$ if it’s discrete as discussed in the next 2 cases.

•  Random variables ${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_n$ and $\mathcal{Z}$ are discrete. In this case the PMF of $\mathcal{Z}$ can be computed as

$P_z\left(z\right)={\displaystyle \sum _{\left(x_1,\dots x_n\right):g\left(x_1,\dots x_n\right)=z}P{\chi }_{1,}{\chi }_{2,\dots ,}{\chi }_{n,}}$

(7.66)

where the summation is over the n−tuples of (${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_n$ ) that are mapped by the function g to the value z.

•  Random variables ${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_N$ are continuous and random variable $\mathcal{Z}$ is discrete. In this case the PMF of $\mathcal{Z}$ can be computed as

$P_Z\left(z\right){\displaystyle \underset{\left(x_1,\dots x_n\right):g}{\int }\cdots {\displaystyle \underset{g\left(x_1,\dots ,x_n\right)=z}{\int }P{\chi }_1,{\chi }_2,\dots ,{\chi }_n,}}$

(7.67)

where the integral is over the n—tuples of (${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_n$ ) that are mapped by the function g to the value z.

Example 7.3.9. Let the joint PDF of random variables ${\mathcal{X}}_1$ and ${\mathcal{X}}_2$ be given by

$\begin{array}{cc}f{\chi }_{1,}{\chi }_2\left(x_1,x_2\right)=1,& 1\le x_1\le 2,1\end{array}\le x_2\le 2$

(7.68)

Now let $\mathcal{Z}={\mathcal{X}}_1{\mathcal{X}}_2$ . The CDF of $\mathcal{Z}$ can be calculated as follows:

•  For the values 1 ≤ $\mathcal{Z}$ ≤ 2

$F_Z\left(z\right)={\displaystyle {\int }_1^z{\displaystyle {\int }_1^{z/x_1}1d{x}_{2}d{x}_1}}$

(7.69)

$={\displaystyle {\int }_1^z\left(\frac{z}{x_1}-1\right)}d{x}_1$

(7.70)

$=z\log \left(z\right)-z+1$

(7.71)

•  For the values 2 < $\mathcal{Z}$ ≤ 4

$F_Z\left(z\right)={\displaystyle {\int }_1^{z/2}{\displaystyle {\int }_1^{2}1d{x}_{2}d{x}_1+{\displaystyle {\int }_{z/2}^2{\displaystyle {\int }_1^{z/x_1}1d{x}_{2}d{x}_1}}}}$

(7.72)

$=\text{}z/2-1+{\displaystyle {\int }_{z/2}^2\left(\frac{z}{x_1}-1\right)d{x}_1}$

(7.73)

$=z/2-1+z\left(\log \left(2\right)-\log \left(z/2\right)\right)-2+z/2$

(7.74)

$=z\left(1+\log \left(2\right)-\log \left(z/2\right)\right)-3$

(7.75)

The corresponding PDF of $\mathcal{Z}$ is given by

$f_Z\left(z\right)=\{\begin{array}{ll}\log \left(z\right)\hfill & 1\le z\le 2\hfill \\ 2\log \left(2\right)-\log \left(z\right)\hfill & 2<z\le 4\hfill \end{array}$

(7.76)

Now suppose $\mathcal{Y}=\lfloor 2{\mathcal{X}}_1+2{\mathcal{X}}_2\rfloor$ . Then the PMF of $\mathcal{Y}$ can be calculated as

$P_{\mathcal{Y}}\left(y\right)=\{\begin{array}{ll}{\displaystyle {\int }_1^{1.5}{\displaystyle {\int }_1^{2.5-x_1}d{x}_{2}d{x}_1=1/8}}\hfill & y=4\hfill \\ {\displaystyle {\int }_1^{1.5}{\displaystyle {\int }_{2.5-x_1}^{3-x_1}d{x}_{2}d{x}_1+{\displaystyle {\int }_{1.5}^2{\displaystyle {\int }_1^{3-x_1}d{x}_{2}d{x}_1=3/8}}}}\hfill & y=5\hfill \\ {\displaystyle {\int }_1^{1.5}{\displaystyle {\int }_{3-x_1}^{2}d{x}_{2}d{x}_1}+{\displaystyle {\int }_{1.5}^2{\displaystyle {\int }_{3-x_1}^{3.5-x_1}d{x}_{2}d{x}_1=3/8}}}\hfill & y=6\hfill \\ {\displaystyle {\int }_{1.5}^2{\displaystyle {\int }_{3.5-x_1}^{2}d{x}_{2}d{x}_1}=1/8}\hfill & y=7\hfill \end{array}$

(7.77)

□

In many applications it turns out that we are interested in computing the distribution of the sum of multiple independent random variables. In this case, the PDF of $\mathcal{Z}$ can be computed simply as the convolution of the marginal PDF’s of random variables ${\mathcal{X}}_1,{\mathcal{X}}_2,\dots {\mathcal{X}}_n$ . For simplicity, we prove this result for the case that $\mathcal{Z}={\mathcal{X}}_1+{\mathcal{X}}_2$ . The CDF of $\mathcal{Z}$ can be calculated as,

$F_Z\left(z\right)={\displaystyle {\int }_{x_1+x_2\le z}f{\chi }_{1,}{\chi }_2\left(x_1,x_2\right)}d{x}_{1}d{x}_2,$

(7.78)

$\begin{array}{c}={\displaystyle {\int }_{-\infty }^{\infty }{\displaystyle {\int }_{-\infty }^{z-x_2}f{\chi }_1\left(x_1\right)f{\chi }_2\left(x_2\right)d{x}_{1}d{x}_2}}\\ \left(\text{due}\text{to}\text{independence}\text{of}{\chi }_1\text{and}{\chi }_2\right)\end{array}$

(7.79)

The PDF of $\mathcal{Z}$ can now be computed by taking the derivative of the CDF as

$f_Z\left(z\right)={\displaystyle {\int }_{-\infty }^{\infty }f{\chi }_1\left(x_1\right)f{\chi }_2\left(z-x_1\right)d{x}_1,}$

(7.80)

which can be recognized as the convolution of the marginal PDFs of ${\mathcal{X}}_1$ and ${\mathcal{X}}_2$ . In the case of discrete random variables, the convolution integral is given by

$P_Z\left(k\right)={\displaystyle \sum _{k}P{\chi }_1\left(k\right)f{\chi }_2\left(z-k\right).}$

(7.81)

The PDF of $\mathcal{Z}$ can also be computed using the properties of the characteristic functions as,

${\varphi }_{\mathcal{Z}}\left(\omega \right)=E\left\{e^{j\omega }{}^{\left({\chi }_1+{\chi }_2\right)}\right\}$

(7.82)

$=E\left\{e^{j\omega {\chi }_1}\right\}E\left\{d^{j\omega {\chi }_2}\right\}$

(7.83)

$=\varphi {\chi }_1\left(\omega \right)\varphi {\chi }_2\left(\omega \right)$

(7.84)

This product relationship is similar to the analysis of linear time invariant systems in which the output of the system equals the convolution of the input and impulse response. Or equivalently, the Fourier transform of the output equals the product of the Fourier transform of the input and the frequency response of the system.

Example 7.3.10. Let ${\mathcal{X}}_1$ ≈ Uniform (a, b) and ${\mathcal{X}}_2$ ≈ Uniform (c, d) be independent uniformly distributed continuous random variables. For simplicity, assume that d−c = b − a. Let $\mathcal{Y}={\mathcal{X}}_1+{\mathcal{X}}_2$ . The characteristic function of ${\mathcal{X}}_1$ equals

$\varphi {\chi }_1\left(\omega \right)=\frac{e^{j\omega b}-e^{j\omega a}}{j\omega \left(b-a\right)}$

(7.85)

Using (7.84), the characteristic function of $\mathcal{Y}$ can be evaluated as,

${\varphi }_{\mathcal{Y}}\left(\omega \right)=\frac{e^{j\omega b}-e^{j\omega a}}{j\omega \left(b-a\right)}\frac{e^{j\omega d}-e^{j\omega c}}{j\omega \left(d-c\right)}$

(7.86)

By taking the inverse Fourier transform of (7.86) it can be shown that the PDF of $\mathcal{Y}$ equals

$f_{\mathcal{Y}}\left(y\right)=\{\begin{array}{ll}\frac{4\left(y-a-c\right)}{\left(b+d-a-c\right)\left(b+d-a-c\right)}=\frac{y-a-c}{\left(d-c\right)\left(b-a\right)}\hfill & \left(a+c\right)\le y\le \left(a-b+c+d\right)/2\hfill \\ \frac{4\left(b+d-y\right)}{\left(b+d-a-c\right)\left(b+d-a-c\right)}=\frac{b+d-y}{\left(d-c\right)\left(b-a\right)}\hfill & \left(b+d\right)\ge y>\left(a+b+c+d\right)/2\hfill \end{array}$

(7.87)

The PDF of $\mathcal{Y}$ can also be derived by convolving the PDFs of ${\mathcal{X}}_1$ and ${\mathcal{X}}_2$ as shown below. For (a + c) ≤ y (a + b + c + d)/2

$f_{\mathcal{Y}}\left(y\right)=\underset{a+c}{\overset{y}{{\displaystyle \int }}}\frac{1}{b-a}\frac{1}{d-c}dx$

(7.88)

$=\frac{y-a-c}{\left(b-a\right)\left(d-c\right)}$

(7.89)

For (a + b + c + d)/2 < y ≤ (b + d), the PDF is given by

$f_{\mathcal{Y}}\left(y\right)=\underset{y}{\overset{b+d}{{\displaystyle \int }}}\frac{1}{b-a}\frac{1}{d-c}dx$

(7.90)

$=\frac{b+d-y}{\left(b-a\right)\left(d-c\right)}$

(7.91)

It can be recognized that this PDF corresponds to a triangular PDF.

□

Example 7.3.11. Let ${\mathcal{X}}_1$ and ${\mathcal{X}}_2$ be independent Gaussian random variables with means ${\mu }_{{\mathcal{X}}_1}$ and ${\mu }_{{\mathcal{X}}_2}$ , respectively. Let their variances be ${\sigma }_{{\mathcal{X}}_1}^2$ and ${\sigma }_{{\mathcal{X}}_2}^2$, respectively. The distribution of $\mathcal{Y}=a{\mathcal{X}}_1+b{\mathcal{X}}_2$ can be computed using the characteristic functions as follows. The characteristic function of ${\mathcal{X}}_1$ equals

$\varphi {\chi }_1\left(\omega \right)=e^{j\mu \chi \omega -{\sigma }_{\chi }^2{\omega }^2/2}$

(7.92)

Now, the mean and variance of $a{\mathcal{X}}_1$ are $a{\mu }_{{\mathcal{X}}_1}$ and $a^2{\sigma }_{{\mathcal{X}}_1}^2$, respectively. Using (7.84), the characteristic function of $\mathcal{Y}$ can be evaluated as,

${\varphi }_{\mathcal{Y}}\left(\omega \right)=e^{j\omega a\mu {\chi }_1}{}^{-a2{\sigma }_{{\chi }_1}^2{\omega }^2/2}{e}^{j\omega b\mu {\chi }_2-b2{\sigma }_{{\chi }_2}^2{\omega }^2/2}$

(7.93)

$=e^{j\omega \left(a\mu {\chi }_1+b\mu {\chi }_2\right)-{\omega }^2\left(a^2{\sigma }_{{\chi }_1}^2+b^2{\sigma }_{{\chi }_2}^2\right)/2}$

(7.94)

From (7.94), it can be clearly seen that $\mathcal{Y}$ is also a Gaussian random variable with mean $a{\mu }_{{\mathcal{X}}_1}+b{\mu }_{{\mathcal{X}}_2}$ and variance $a^2{\sigma }_{{\mathcal{X}}_1}^2+b^2{\sigma }_{{\mathcal{X}}_2}^1$. Thus, any linear processing of a Gaussian variable results in another Gaussian variable.

□

Example 7.3.12. Let ${\mathcal{X}}_i$ be a sequence of i.i.d. exponential random variables n with PDF fx (x) = αe^−αx. Let ${\mathcal{Y}}_n={\displaystyle \sum _{i=1}^n{\mathcal{X}}_n}$ represent the sum of the random variables ${\mathcal{X}}_i$ . It can be shown using the principles of mathematical induction that the PDF and CDF of Y_n are given by

$f_{\mathcal{Y}}{}_{{}_n}\left(x\right)=\alpha e^{-\alpha x}\frac{{\left(\alpha x\right)}^{n-1}}{\left(n-1\right)!}$

(7.95)

$F_{\mathcal{Y}}{}_{{}_n}\left(x\right)=1-e^{-\alpha x}\left(1+\frac{\alpha x}{1!}+\dots +\frac{{\left(\alpha x\right)}^{n-1}}{\left(n-1\right)!}\right)$

(7.96)

Now, define a new family of discrete random variables $\mathcal{N}\left(t\right)$ as follows

$\mathcal{N}\left(t\right)=\underset{k}{\arg \max }{\mathcal{Y}}_k\le t$

(7.97)

In other words, $\mathcal{N}\left(t\right)$ takes on the value n iff ${\mathcal{Y}}_n\le t$ and ${\mathcal{Y}}_{n+1}>t$ The probability of this event can be calculated as

$\mathrm{Pr}\left(\mathcal{N}\left(t\right)=n\right)=F_{{\mathcal{Y}}_n}\left(t\right)-F_{{\mathcal{Y}}_{n+1}}\left(t\right)=e^{-\alpha t}\frac{{\left(\alpha t\right)}^n}{n!}$

(7.98)

This demonstrates the relationship between the discrete Poisson random variable and the continuous exponential random variables.

□

7.3.4      Convergence of Random Variables

Before formally introducing the law of large numbers, in this section, we introduce the various types of convergences of random variables.

First, consider a sequence a₁, a₂,… a_n of real numbers. This sequence is said to converge to a real number a if for any given value of ϵ > 0, there exists an integer N such that ∣a_n − a∣ < ϵ, ∀n ≥ N.

As noted before a random variable is a mapping from the set of outcomes to real numbers. Consider a sequence of random variables ${\mathcal{X}}_1$ , ${\mathcal{X}}_2$ ,….

Convergence everywhere: If for every value of ω ∈ S, the sequence ${\mathcal{X}}_1\left(\omega \right),{\mathcal{X}}_2\left(\omega \right),\dots$ converges to a value that could depend on ω then the sequence is said to converge everywhere.

Convergence almost everywhere: If the set of outcomes ω for which the sequence ${\mathcal{X}}_1\left(\omega \right),{\mathcal{X}}_2\left(\omega \right),\dots$ converges has a probability equal to 1, then the sequence is said to converge almost everywhere. In other words,

$\mathrm{Pr}\left({\chi }_n\to \chi \right)=1,\text{as}n\to \infty .$

(7.99)

Convergence in probability or stochastic convergence: For a given value of ϵ > 0, consider the sequence of real numbers given by $\mathrm{Pr}\left(|{\mathcal{X}}_n-\mathcal{X}|>\epsilon \right)$ . If this sequence of real numbers converges to 0 for all values of ϵ > 0, then the sequence ${\mathcal{X}}_1$ , ${\mathcal{X}}_2$ ,… is said to converge in probability to the random variable $\mathcal{X}$ .

It should be noted that the expression “converges almost everywhere” also implies convergence in probability while the reverse is not always true. Further, several other forms of convergences are defined in the literature [8].

7.3.5      Law of Large Numbers (LLN) and Central Limit Theorem (CLT)

The LLN allows the approximation of the average of a finite set of independent random variables by a single number. The LLN essentially states that certain aspects of the behavior of populations becomes more predictable when the population size increases. In its simple form, the weak law of large numbers (WLLN) is stated as follows:

Theorem 7.3.1 (Weak Law of Large Numbers). Let ${ℳ}_n=\frac{1}{n}\left({\mathcal{X}}_1+{\mathcal{X}}_2+\cdots +{\mathcal{X}}_n\right)$, where the random variables ${\mathcal{X}}_{\mathrm{i}}$ are all independent and have identical means ${\mu }_{\mathcal{X}}$ and a finite variance no greater than ${\sigma }_{\mathcal{X}}^2$ . Then,

$\mathrm{Pr}\left(\left|{ℳ}_n-{\mu }_{\chi }\right|\ge \delta \right)\le \frac{{\sigma }_{\chi }^2}{n{\delta }^2}$

(7.100)

In the limit of large n, the RHS of (7.100) equals 0. In other words, ${\mathcal{M}}_n$ converges to ${\mu }_{\mathcal{X}}$ in probability.

In simple terms, the WLLN states that ${\mathcal{M}}_n$ can be approximated by ${\mu }_{\mathcal{X}}$ . It should be noted that the finite variance requirement in the theorem is not strictly needed; it only makes the proof easier.

Theorem 7.3.2 (Strong Law of Large Numbers). Let ${ℳ}_n=\frac{1}{n}\left({\mathcal{X}}_1+{\mathcal{X}}_2+\cdots +{\mathcal{X}}_n\right)$, where the random variables ${\mathcal{X}}_{\mathrm{i}}$ are all independent and have identical means ${\mu }_{\mathcal{X}}$ . Then, ${\mathcal{M}}_n$ converges to ${\mu }_{\mathcal{X}}$ almost everywhere, i.e.,

$\mathrm{Pr}\left({ℳ}_n\to {\mu }_{\chi }\right)=1asn\to \infty$

(7.101)

Theorem 7.3.3 (Central Limit Theorem). Let ${ℳ}_n=\frac{1}{n}\left({\mathcal{X}}_1+{\mathcal{X}}_2+\cdots +{\mathcal{X}}_n\right)$, where the random variables ${\mathcal{X}}_{\mathrm{i}}$ are all independent and have identical means ${\mu }_{\mathcal{X}}$ and a finite variance ${\sigma }^2\mathcal{X}$ Then,

$\underset{x\to \infty }{\lim }\mathrm{Pr}\left(\frac{{ℳ}_n-\mu \chi }{\sqrt{n-1{\sigma }_{\chi }^2}}\le c\right)=\text{Φ}\left(c\right)$

(7.102)

The CLT allows the sum or mean of a finite set of independent random variables to be approximated by a Gaussian distribution and the approximation becomes better for large population sizes.

The LLN can be used to determine the probability of an event that is repeatable and has independent probabilities in each trial. For instance, let random variable ${\mathcal{X}}_i$ = 1 if event A occurs in the i^th trial and ${\mathcal{X}}_i$ = 0 otherwise. Then Pr (A) = E {${\mathcal{X}}_i$ } The sample mean ${\widehat{\mu }}_{\mathcal{X}}=\frac{1}{n}{\displaystyle \sum _{k=1}^n{\mathcal{X}}_k}$ is an estimate of the probability Pr (A). By the LLN, as the sample size gets large, the estimate will converge to the true probability. Other applications of the laws of large numbers in estimation theory are given in Chapter 8.

The Monte Carlo simulation method is based on this principle and is commonly used to evaluate the performance of a variety of systems. For instance, to detect the probability of bit error of a communication system, a large number of bits are transmitted and the average number of errors are calculated. In information theory, the asymptotic equipartition property (AEP) [9] is a consequence of the LLN.

7.4      Random Processes

A random process $\mathcal{X}$ (t, ω) is a mapping from each outcome ω to functions of time. A random process can also be considered as an indexed collection of random variables. The index set can be continuous or discrete. The values taken by the process can also belong to a discrete set or continuous set. Thus, there are 4 possible types of random processes:

•  Continuous time, continuous valued processes such as seismic measurements and Brownian motion.

•  Continuous time, discrete valued processes such as population size and stock prices.

•  Discrete time, continuous valued processes such as sampled speech and temperature signals.

•  Discrete time, discrete valued processes such as digitized speech and video signals.

The collection of temporal functions over all values of ω is sometimes referred to as the ensemble of function. For simplicity of notation, we do not explicitly show the dependence of the random process $\mathcal{X}\left(t\right)$ on the outcome ω. To completely define the random process, the joint distribution of the set of random variables $\mathcal{X}\left(t_1\right),\mathcal{X}\left(t_2\right),\dots \mathcal{X}\left(t_K\right)$ needs to be specified for all values of K and t₁, t₂,…, t_K. Clearly, this is a daunting task and practically impossible except in some very narrow and specialized cases such as a process defined by an i.i.d. sequence of random variables. Consequently, most analysis of random processes is restricted to understanding some statistical properties.

The mean function ${\mu }_{\mathcal{X}\left(t\right)}$ of a random process is defined as

${\mu }_{\chi }{}_{\left(t\right)}={\displaystyle \int x{f}_{\chi \left(t\right)}\left(x\right)dx}$

(7.103)

The autocorrelation $R_{\mathcal{X}}\left(t,\tau \right)$ of the random process is defined as

$R_{\chi }\left(t,\tau \right)=E\left\{\chi \left(t\right)\chi *\left(t+\tau \right)\right\}$

(7.104)

The autocovariance of the process is defined as

$C_{\chi }\left(t,\tau \right)=E\left\{\left(\chi \left(t\right)-{\mu }_{\chi \left(t\right)}\right){\left(\chi \left(t+\tau \right)-{\mu }_{\chi \left(t+\tau \right)}\right)}^{*}\right\}=R_{\chi }\left(t,\tau \right)-{\mu }_{\chi \left(t\right)}{\mu }_{\chi \left(t+\tau \right)}$

(7.105)

The crosscorrelation $R_{\mathcal{X},\mathcal{Y}}\left(t,\tau \right)$ of two random process $\mathcal{X}\left(t\right)$ and $\mathcal{Y}\left(t\right)$ is defined as

$R_{\chi ,\mathcal{Y}}\left(t,\tau \right)=E\left\{\chi \left(t\right)\mathcal{Y}*\left(t+\tau \right)\right\}$

(7.106)

Properties of autocorrelation: The autocorrelation $R_{\mathcal{X}}\left(t,\tau \right)$ is a positive definite function. Further, it can be shown that given any positive definite function f (t, τ) we can compute a random process $\mathcal{X}\left(t\right)$ for which the function is the autocorrelation. It can also be easily shown that $R_{\mathcal{X}}\left(t+\tau ,-\tau \right)=R_{\mathcal{X}}^{*}\left(t,\tau \right)$ .

7.4.1      Stationary Process

Random process $\mathcal{X}\left(t\right)$ is said to be strictly stationary if the joint PDF of $\left(\mathcal{X}\left(t_1\right),\mathcal{X}\left(t_2\right),\dots ,\mathcal{X}\left(t_K\right)\right)$ is the same as the joint PDF of $\left(\mathcal{X}\left(t_1+T\right),\mathcal{X}\left(t_2+T\right),\dots \mathcal{X}\left(t_k+T\right)\right)$ for all values of k, t₁, t₂,…, t_k and T. Two random process ${\mathcal{X}}_t$ and ${\mathcal{Y}}_t$ are jointly stationary if the joint PDF of $\left(\mathcal{X}\left(t_1\right),\mathcal{X}\left(t_2\right),\dots ,\mathcal{X}\left(t_K\right),\mathcal{Y}\left(t_k+1\right),\mathcal{Y}\left(t_k+2\right),\dots \mathcal{Y}\left(t_K\right)\right)$ is the same as the joint PDF of $\left(\mathcal{X}\left(t_1+T\right),\mathcal{X}\left(t_2+T\right),\dots \mathcal{X}\left(t_k+T\right),\mathcal{Y}\left(t_{k+1}+T\right),\mathcal{Y}\left(t_{k+2}+T\right),\dots \mathcal{Y}\left(t_K+T\right)\right)$ for all values of k, K,t₁,t₂,…, t_K and T.

Random process $\mathcal{X}\left(t\right)$ is said to be wide-sense stationary (WSS) if and only if its mean is independent of time $\left({\mu }_{\mathcal{X}\left(t\right)}={\mu }_{\mathcal{X}}\right)$ and its autocorrelation depends only on time difference, i.e., $R_{\mathcal{X}}\left(t,\tau \right)=R_{\mathcal{X}}\left(\tau \right)$ . Two random processes ${\mathcal{X}}_t$ and ${\mathcal{Y}}_t$ are jointly WSS if both $\mathcal{X}\left(t\right)$ and $\mathcal{Y}\left(t\right)$ are WSS and their crosscorrelation $R_{\mathcal{X},\mathcal{Y}}\left(t,\tau \right)$ depends only on time difference.

Random process $\mathcal{X}\left(t\right)$ is said to be cyclostationary if the joint PDF of $\left(\mathcal{X}\left(t_1\right),\mathcal{X}\left(t_2\right),\dots ,\mathcal{X}\left(t_K\right)\right)$ is the same as the joint PDF of $\left(\mathcal{X}\left(t_1+T\right),\mathcal{X}\left(t_2+T\right),\dots ,\mathcal{X}\left(t_k+T\right)\right)$ for all values of k,t₁,t₂,…, t_k and for a fixed value of T called the time period of the random process.

The change in the process $\mathcal{X}\left(t_2\right)-{\mathcal{X}}_{t_1},\mathcal{X}\left(t_3\right)-{\mathcal{X}}_{(}{t}_2),\mathcal{X}\left(t_4\right)-\mathcal{X}\left(t_3\right),\cdots$ between successive sampling instants, is called the increments of the process. A process in which the increments are all independent is said to be an independent increments process. Similarly, a process with stationary increments is said to be a stationary increments process. The stationary properties of discrete time random processes are similarly defined.

A random process is said to be ergodicity if the properties calculated from a temporal sequence of the process are the same as the properties of the ensemble of functions.

Random Walk: The random walk process ${\mathcal{D}}_n$ is defined as the sum of a sequence of independent random variables ${\mathcal{L}}_i$ that takes values 1 and -1 with probabilities α and 1 − α, respectively. Thus, ${\mathcal{D}}_n={\displaystyle \sum _{i=1}^n{\mathcal{L}}_i}$ . In other words, at each time-instant the process either increases by 1 or decreases by 1. The random walk process is clearly memoryless in the sense that given the current state of the process, the future state is independent of the past. It can also be easily seen that the increments of the process are independent and stationary.

ARMA Process: Consider a random process ${\mathcal{Y}}_n$ which is obtained by passing the White noise process ${\mathcal{X}}_n$ through a linear filter H(f). If the transfer function of the filter is of the form

$H\left(f\right)=\frac{{\displaystyle {\sum }_{k=0}^B{b}_k{e}^{-j2\pi fk}}}{1-{\displaystyle {\sum }_{k=0}^A{a}_k{e}^{-j2\pi fk}}}$

(7.107)

then the evolution of the process can be represented as

${\mathcal{Y}}_n={\displaystyle \sum _{k=0}^A{a}_k{\mathcal{Y}}_{n-k}+{\displaystyle \sum _{k=0}^B{b}_k{\chi }_{n-k}}}$

(7.108)

Such a process is referred to as an ARMA process and is frequently used in several signal processing applications and for time-series analysis.

Wiener random process and Brownian motion: A Wiener random process is constructed as the limit of a random walk process. Specifically, consider the symmetric random walk process which has equal probability to increase or decrease by 1. Now let the time increments be denoted by δ and the increase in process at each time instant be set to $\sqrt{\alpha \delta }$. In the limit of δ → 0, the continuous time random process $\mathcal{X}\left(t\right)$ becomes a process with zero mean and a variance that increases linearly with time. Further, since each $\mathcal{X}\left(t\right)$ is now the sum of an infinite number of independent random variables, it has a Gaussian distribution. Such a process is referred to as the Wiener random process and is commonly used to model Brownian motion. Clearly, by construction, it can be seen that the Wiener process has independent and stationary increments. The autocorrelation of this process can be shown to equal $R_{\mathcal{X}}\left(t,\tau \right)=\alpha \min \left\{t,t+\tau \right\}$ .

7.4.2      Random Process as the Input to a Linear System

When a random process $\mathcal{X}\left(t\right)$ is the input to a LTI system then the output $\mathcal{Y}\left(t\right)$ is also a random process. Further, if the input is WSS then the output is also WSS as will be clear from (7.111) and (7.116). The mean and autocorrelation of the output can be derived in terms of the mean and autocorrelation of the input to the system and the impulse response of the LTI system. Let h(t) and H(f) denote, respectively, the impulse response and frequency response of the LTI system.

Now, the mean of the output process $\mathcal{Y}\left(t\right)$ can be derived as

$E\left\{\mathcal{Y}\left(t\right)\right\}=E\left\{{\displaystyle \int h\left(t-u\right)\chi \left(u\right)du}\right\}$

(7.109)

${\displaystyle \int h\left(t-u\right)E\left\{\chi \left(u\right)\right\}du}$

(7.110)

$={\mu }_{\chi }H\left(0\right)$

(7.111)

Thus, the mean of the output process $\mathcal{Y}\left(t\right)$ is independent of time. The autocorrelation of the output is given by,

$R_{\mathcal{Y}}\left(t,\tau \right)=E\left\{{\mathcal{Y}}_t{\mathcal{Y}}_{t+\tau }^{*}\right\}$

(7.112)

$=E\left\{\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}h\left(u\right)\chi \left(t-u\right)du\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}{h}^{*}\left(v\right){\chi }^{*}\left(t+\tau -v\right)dv\right\}$

(7.113)

$=\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}h\left(u\right)h^{*}\left(v\right)E\left\{\chi \left(t-u\right)\chi \left(t+\tau -v\right)\right\}dvdu$

(7.114)

Since, $\mathcal{X}\left(t\right)$ is WSS, (7.114) can be rewritten as

$R_{\mathcal{Y}}\left(t,\tau \right)=\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}h\left(u\right)\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}{h}^{*}\left(v\right)R_{\chi }\left(\tau -v+u\right)dvdu$

(7.115)

$=R_{\chi }\left(\tau \right)*h^{*}\left(\tau \right)*h\left(-\tau \right)$

(7.116)

Thus, the autocorrelation of the output process $\mathcal{Y}\left(t\right)$ depends only on time-difference τ.

The cross-correlation is given by

$R_{\chi ,\mathcal{Y}}\left(t,\tau \right)=E\left\{{\displaystyle {\int }_{-\infty }^{\infty }\chi \left(t\right)h^{*}\left(u\right){\chi }^{*}\left(t+\tau -u\right)du}\right\}$

(7.117)

$=\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}{h}^{*}\left(u\right)E\left\{\chi \left(t\right){\chi }^{*}\left(t+\tau -u\right)du\right\}$

(7.118)

$=\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}{h}^{*}\left(u\right)R_{\chi }\left(\tau -u\right)du$

(7.119)

$=\underset{-\infty }{\overset{\infty }{{\displaystyle \int }}}{h}^{*}\left(u\right)R_{\chi }\left(\tau -u\right)du$

(7.120)

If random processes $\mathcal{X}\left(t\right)$ and $\mathcal{Y}\left(t\right)$ are jointly wide sense stationary, then

$R_{\chi ,\mathcal{Y}}\left(\tau \right)=R_{\mathcal{Y},\chi }\left(-\tau \right).$

(7.121)

The power spectral density (PSD), denoted $W_{\mathcal{X}}\left(f\right)$ , of random process ${\mathcal{X}}_t$ is defined as the Fourier transform of the autocorrelation $R_{\mathcal{X}}\left(\tau \right)$ and is given by

$W_{\chi }\left(f\right)={\displaystyle {\int }_{-\infty }^{\infty }{R}_{\chi }\left(t\right)e^{-j2\pi ft}dt}$

(7.122)

Similarly, the cross-power spectral density, denoted $W_{\mathcal{X},\mathcal{Y}}\left(f\right)$ of jointly WSS random processes $\mathcal{X}\left(t\right)$ and $\mathcal{Y}\left(t\right)$ is defined as,

$W_{\chi ,\mathcal{Y}}\left(f\right)={\displaystyle {\int }_{-\infty }^{\infty }{R}_{\chi ,\mathcal{Y}}\left(t\right)e^{-j2\pi ft}dt}$

(7.123)

For this linear time invariant system with input $\mathcal{X}\left(t\right)$ the PSD of the output can be computed using the frequency transfer function of the system and the PSD of the input as,

$W_{\mathcal{Y}}\left(f\right)=W_{\chi }\left(f\right){\left|H\left(f\right)\right|}^2$

(7.124)

The cross-power spectral density is related to the PSD of $\mathcal{X}\left(t\right)$ and $\mathcal{Y}\left(t\right)$ as

$W_{\chi ,\mathcal{Y}}\left(f\right)=H\left(f\right)W_{\chi }\left(f\right)$

(7.125)

$W_{\mathcal{Y}}\left(f\right)=H^{*}\left(f\right)W_{\chi ,\mathcal{Y}}\left(f\right)$

(7.126)

Example 7.4.1. Consider a WSS random process $\mathcal{X}\left(t\right)=A\cos \left(2\pi f_{0}t+\theta \right)$ , where A is a constant and θ is uniformly distributed between (0, 2π). It can be easily shown that the autocorrelation $R\mathcal{X}\left(\tau \right)=\frac{A^2}{2}\cos \left(2\pi f+0\tau \right)$. Let this process be input to differentiator system with frequency response H(f) = j2πf. The output $\mathcal{Y}\left(t\right)$ has spectral density given by

$S_{\mathcal{Y}}\left(f\right)=4{\pi }^2{f}^2{S}_{\chi }\left(f\right)=A2{\pi }^2{f}_0^2\left(\delta \left(f-f_0\right)+\delta \left(f+f_0\right)\right).$

(7.127)

□

Discrete Time Processes and Systems

For a discrete time random process, $R_{\mathcal{X}}\left(m,n\right)=E\left\{{\mathcal{X}}_n{\mathcal{X}}_{n+m}\right\}$ . If the process is wide sense stationary, then $R_{\mathcal{X}}\left(m,n\right)=R_{\mathcal{X}}\left(n\right)$ . Since $R_{\mathcal{X}}\left(n\right)$ is a discrete function, the PSD is a periodic function. Thus, it is sufficient to consider one period of the PSD. The relationship between the autocorrelation and PSD is now given by,

$W_{\chi }\left(f\right)={\displaystyle \sum _k{R}_{\chi }\left(k\right)e^{-je\pi kf}}$

(7.128)

$R_{\chi }\left(k\right)={\displaystyle {\int }_{-1/2}^{1/2}{W}_{\chi }\left(f\right)e^{j2\pi fk}df}$

(7.129)

Example 7.4.2. Let the input to a simple averaging filter h(n) be a WSS process $\mathcal{X}\left(n\right)$ with autocorrelation

$R_{\chi }\left(n\right)=\delta \left(n\right)$

(7.130)

Let h(n) = 1/(2M + 1), n = −M,… − 1,0,1,… M and h(n) = 0 for all other values of n. The autocorrelation of the output process $\mathcal{X}\left(n\right)$ can be calculated as

$R_{\mathcal{Y}}\left(n\right)={\displaystyle \sum _{i=-M}^M{\displaystyle \sum _{j=-M}^M{h}_i{h}_j{R}_{\chi }\left(n+i-j\right)}}$

(7.131)

$=\{\begin{array}{ll}\frac{1}{{\left(2M+1\right)}^2}\left(2M+1\left|n\right|\right)\hfill & n=-\left(2M+1\right),\dots ,-1,0,1,\dots \left(2M+1\right)\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

(7.132)

□

7.5      Markov Process

A random process with discrete states is said to be a Markov process if it is memoryless, i.e., it satisfies the following property

$f{\chi }_t|{\chi }_{\tau <0}=f{\chi }_t|{\chi }_{\tau }$

(7.133)

Without loss of generality, the states of the random process are denoted by {0,1,…}.

7.5.1      Markov Chains

A discrete time Markov process is also referred to as a Markov Chain. In this case,

$\mathrm{Pr}\left({\chi }_{n+1}|{\chi }_n,{\chi }_{n-1},\dots \right)=\mathrm{Pr}\left({\chi }_{n+1}|{\chi }_n\right)$

(7.134)

A Markov chain is completely defined by its one step state transition probabilities denoted by p_ij and the initial starting condition. For convenience, these transition probabilities are arranged in a matrix form represented by P with p_ij being the i^th row and j^th column element such that $p_{ij}=\mathrm{Pr}\left({\mathcal{X}}_{n+1}=j|{\mathcal{X}}_n=i\right)$ . The n—step transition probabilities can be derived from p_ij using the Chapman-Kolmogorov equations as follows:

$p_{ij}^{\left(n\right)}={\displaystyle \sum _k{p}_{ik}^{\left(m\right)}{p}_{kj}^{\left(n-m\right)},0\le m\le n}$

(7.135)

To intuitively understand (7.135), we consider the transition from state i to state j in exactly n steps. After m < n steps, let the Markov chain be in state k. Consider all the paths that start at state i and is in state k after m steps. The probability of all such paths is given by $p_{ik}^{\left(m\right)}$. Similarly, the probability of going from state k to state j in n − m steps equals $p_{kj}^{\left(n-m\right)}$. Thus the probability of all paths that start at state i and end at state j and passing through state k in step m is given by $p_{ik}^{\left(m\right)}{p}_{kj}^{\left(n-m\right)}$ Thus, the total probability equals the summation over all possible intermediate states k.

A Markov chain is sometimes represented pictorially (as shown in Figure 7.3) as a group of states with arcs representing the transitions between the various states. In a discrete time MC, there is a transition at every time instant. In a continuous time MC, the transition between states occur at random time instants.

The states of a Markov chain are classified as follows. State i can reach state j if there is a non-zero probability of reaching state j in n-steps after starting from state i. States i and j are said to communicate if one can reach state i starting from state j and vice versa. A communicating class consists of a set of states that can communicate with each other. Clearly, all the states of a Markov chain can be partitioned into disjoint communicating classes. An MC is said to be irreducible if it contains only one class, i.e., all states communicate with each other.

Figure 7.3:  Illustration of the transitions between various states of a discrete Markov chain.

The first passage time or hitting time ${\mathcal{T}}_{ij}$ is the random time it takes to first reach state j starting from state i. Let $f_{jj}^{\left(n\right)}=\mathrm{Pr}\left({\mathcal{T}}_{jj}=n\right)$ denote the probability that the MC comes back to state j in exactly n-steps. Let $f_{jj}={\displaystyle \sum _{n=1}^{\infty }{f}_{jj}^{\left(n\right)}}$.

State j is transient if f_jj < 1. State j is recurrent if f_jj=1. The recurrent states are positive recurrent if $E\left\{{\mathcal{T}}_{i}j\right\}<\infty$ and null recurrent if $E\left\{{\mathcal{T}}_{jj}\right\}=\infty$ . The positive recurrent states are said to be periodic if revisits must occur in multiples of a certain period d. The positive recurrent states are said to be a periodic if revisits have period 1.

If the Markov chain is irreducible, and all its states are aperiodic and positive recurrent, then the Markov chain is said to be ergodic. In this case, as time continues the chain approaches a steady state or equilibrium condition. The probability distribution of the states in equilibrium are unique and can be computed from the transition probability matrix of the MC. Let π_i denote the probability of being in state i and let Π = [π₁ π₂ …]. These probabilities π_i also represent a time average, i.e., the fraction of time spent in state i. The steady-state probabilities are not dependent on the initial state probabilities and can be calculated as the solution to the balance equations which is given in matrix form as,

$\mathbf{\text{Π}}=\mathbf{\text{Π}}\text{P}$

(7.136)

with the additional constraint that the sum of the probabilities of the states should equal 1, i.e.,

${\displaystyle \sum _i{\pi }_i}=1$

(7.137)

Example 7.5.1. Consider a node in an ad-hoc network that is in one of three possible states during each time slot: transmitting its own data (T), receiving data (R), or in sleep mode (S). The transition probabilities from the various states are given in Figure 7.3. Compute the steady-state probabilities of the various states. If the energy consumed in the T, R, and S states are respectively 100 mJ, 30 mJ, and 1 mJ, compute the average energy consumed by the node.

The transition probability matrix is given by

$\mathbf{\text{P}}=\left[\begin{array}{ccc}0.1& 0.7& 0.2\\ 0.2& 0.4& 0.4\\ 0.3& 0.1& 0.6\end{array}\right]$

(7.138)

The steady-state probability distribution for the transmit, receive, and sleep states can be computed respectively as 2/9,1/3, and 4/9. The average energy consumption equals 32.67 mJ.

□

Time reversibility. Let ${\mathcal{Y}}_n={\mathcal{X}}_{-n}$ represent the MC with time reversed process of the Markov chain ${\mathcal{X}}_n$ . Clearly, the time reversed MC has the same states as the original MC. Also, the time spent in each state is the same whether it is the original MC or the time-reversed MC, so the steady-state probabilities are also identical. Further, the transition probabilities of the time-reversed MC are related to those of the original MC as

$\mathrm{Pr}\left({\mathcal{Y}}_{n-1}=i|{\mathcal{Y}}_n=j\right)=\frac{{\pi }_j}{{\pi }_i}{p}_{ij}$

(7.139)

7.5.2      Continuous Time Markov Chains

As noted before, a continuous time Markov chain also has discrete states and is characterized by arcs representing state transitions. However, transitions between states can happen at any time. The state transition probability matrix for the continuous time Markov chains can also be defined in a manner similar to the discrete time Markov chain. However, the transition probabilities now also depend on time as follows

$p_i{}_j\left(s,t\right)=\mathrm{Pr}\left(\chi \left(s+t\right)=j|\chi \left(s\right)=i\right)$

(7.140)

For simplicity, it is sometimes assumed that p_ij(s,t) is independent of starting time s and only depends on time difference t. Even in this case, the analysis is complicated since the transition probabilities must be specified for all values of t.

An alternate approach to the analysis of such systems is to consider the continuous time MC at the time instants when a state transition occurs. Specifically, ${\mathcal{Y}}_n=\mathcal{X}\left(t_n\right)$ is an embedded discrete time Markov chain where the transition times are t₁,t₂,…. Further, for a given value of ${\mathcal{Y}}_n$ , the time intervals τ_n = t_n+1 − t_n are independent exponential random variables with mean a_i that depends only on the current state.

The infinitesimal rate a_ij is defined as

$a_{ij}=\underset{x\to \infty }{\lim }\frac{p_{ij}\left(t\right)}{t}=a_i\mathrm{Pr}\left({\mathcal{Y}}_{n+1}=j|{\mathcal{Y}}_n=i\right)$

(7.141)

The time spent by the MC in state i before a transition to state j is exponentially distributed with parameter a_ij. Clearly, $a_i={\displaystyle \sum _j{a}_{ij}\forall i}$. These rates are arranged in matrix form for convenience and denoted by matrix A with the i^th row and j^th column entry being a_ij.

The steady-state distribution for the continuous time MC can be computed using the same principle as for its discrete time counterpart. Recall that π_i denotes the probability of being in state i. Now the probability of transition from state i to state j is given by a_ij/a_i. Thus,

${\pi }_j={\displaystyle \sum _{i\ne j}{\pi }_i\frac{a_{ij}}{a_j}}$

(7.142)

$\Rightarrow {\pi }_j{a}_j={\displaystyle \sum _{i\ne j}{\pi }_i{a}_{ij}}$

(7.143)

$\Rightarrow {\displaystyle \sum _{i\ne j}{\pi }_i{a}_{ij}-{\pi }_j{a}_j=0}$

(7.144)

with the additional constraint that ${\displaystyle \sum _i{\pi }_i=1}$. Grouping (7.144) for all i together i into matrix form results in the following balance equation

$\text{Π}\text{Q}=0$

(7.145)

where

$\text{Q}=\left[\begin{array}{cccc}-a_0& a_{01}& a_{02}& \dots \\ a_{10}& -a_1& a_{12}& \dots \\ a_{20}& a_{21}& -a_2& \dots \end{array}\right]$

(7.146)

Example 7.5.2. Each node in an ad-hoc network is either in transmit or receive mode. The time spent in the transmit mode is exponentially distributed with parameter α and the time spent in the receive mode is exponentially distributed with parameter β. Assume that all transmit and receive durations are independent. In this case, the Q matrix is given by

$\text{Q}=\left[\begin{array}{cc}-\alpha & \alpha \\ \beta & -\beta \end{array}\right]$

(7.147)

The steady-state probabilities can easily be computed as $\frac{\beta }{\alpha +\alpha }$ and $\frac{\alpha }{\alpha +\beta }$.

□

7.5.3      Hidden Markov Model

In many applications the output variables being observed do not directly have the Markov property. However, there is an underlying dynamically changing state variable which exhibits the Markov property. Further, corresponding to each state, there is a probability distribution that governs the output variable that is observed. Such a model is referred to as a HMM and such models are often used in signal modeling and coding applications as illustrated by the examples in this section. An excellent introduction to HMMs is given in [10].

Let random variables ${\mathcal{X}}_n$ , for n=1, 2,… represent the underlying state of the system. Let the observed random variables be represented by ${\mathcal{Y}}_n$ , for n =1, 2,… The hidden Markov model is characterized by two condition distribution matrices, A and B. Matrix A with elements $a_{ij}=\mathrm{Pr}\left({\mathcal{X}}_{n+1}=j|{\mathcal{X}}_n=i\right)$ determines the state transition probabilities for the underlying state variable ${\mathcal{X}}_n$ . Matrix B with elements $b_{ik}=\mathrm{Pr}\left({\mathcal{Y}}_n=k|{\mathcal{X}}_n=i\right)$ determines the conditional probabilities of the output variable for each input variable. In some applications the initial distribution,${\pi }_i=\mathrm{Pr}\left({\mathcal{X}}_1=i\right)$ , of the states of the system is also specified. The structure of the hidden Markov model is depicted in Figure 7.4.

Figure 7.4:  Structure of a general Hidden Markov Model.

There are essentially three main problems in HMMs.

1.  Enumeration/Evaluation Problem: Given a certain model (A, B, Π) for the HMM and a sequence of observations, y₁, y₂,… y_N, calculate the probability Pr (y₁, y₂,… y_N ∣ A, B, Π) that the model caused these observations.

2.  State Estimation: Given a certain model (A, B, Π) and observation sequence y₁, y₂,… y_N, find the best sequences x̂₁, x̂₂,… x̂_N of state variables that could result in the observation.

3.  Model Parameter Optimization: Given a certain sequence of observations y₁, y₂,… y_N, find the model probabilities (A, B, Π) that best fit the given data. This problem is typically solved during the model training phase and is critical in the practical use of HMMs.

Solution to the Enumeration problem

The problem of enumeration can be evaluated using elementary tools of conditional probability. Formally, given a sequence of observations y₁, y₂,…, y_N, this sequence can be obtained from a given state sequence as

$\mathrm{Pr}\left(y_1,y_2,\dots ,y_N|s_1,s_2,\dots ,s_N\right)={\text{Π}}_{k=1}^N\mathrm{Pr}\left(y_k|s_k\right),$

(7.148)

assuming the observations are independent. The probability of this state sequence is given by

$\mathrm{Pr}\left(s_1,s_2,\dots s_N\right)=\mathrm{Pr}\left({\chi }_1=s_1\right){\text{Π}}_{k=2}^N\mathrm{Pr}\left({\chi }_k=s_k|{\chi }_{k-1}=s_{k-1}\right).$

(7.149)

The desired probability of the observations given the model can then be calculated as

$\begin{array}{l}\mathrm{Pr}\left(y_1,y_2,\cdots ,y_N|A,B,\pi \right)={\displaystyle \sum _{s_1,s_2,\cdots s_N}\mathrm{Pr}\left({\chi }_1=s_1\right)\mathrm{Pr}\left(y_1|s_1\right)}\\ {\text{Π}}_{k=2}^N\mathrm{Pr}\left({\chi }_k=s_k|{\chi }_{k-1}=s_{k-1}\right)\mathrm{Pr}\left(y_k|s_k\right)\end{array}$

(7.150)

The difficulty with this direct evaluation (7.150) of Pr (y_l, y₂,…, y_N∣A,B,π) is that the number of computations required is of the order of NM^N, where M is the number of possible states of the underlying Markov chain. Clearly, this poses a significant computational challenge even for reasonable lengths N of the observed sequence. In practice, a computationally efficient algorithms known as the Forward-Backward procedure is used to reduce the computational complexity. It should be mentioned that this Forward-Backward procedure can be derived as a special case of a message passing algorithm in graphs as described in Chapter 13.

The main steps in the Forward algorithm are as follows. Define α_i(m) as the probability of the partial observation sequence y₁,y₂,…,y_i up to time i and having state x_i = m. Now these probabilities α_i(m) can be calculated using the following recursive approach:

1.  The Initialization Step: First set

${\alpha }_1\left(m\right)={\pi }_m\mathrm{Pr}\left(y_1|x_1=m\right),\forall 1\le m\le M$

(7.151)

2.  The Induction Step:

$\begin{array}{l}{\alpha }_{i+1}\left(k\right)=\left[{\displaystyle \sum _{m=1}^M{\alpha }_i\left(m\right)\mathrm{Pr}\left(x_{i+1}=k|x_i=m\right)}\right]\mathrm{Pr}\left(y_{i+1}|x_{i+1}=k\right),\\ \forall k=1,\dots M,\text{and}i=1,\dots N-1.\end{array}$

(7.152)

3.  The Termination Step:

$\mathrm{Pr}\left(y_1,y_2,\dots ,y_N|A,B,\pi \right)={\displaystyle \sum _{m=1}^M{\alpha }_N\left(m\right)}$

(7.153)

The Backward algorithm proceeds in a similar manner to the Forward algorithm. Define β_i(m) as the joint probability of the partial sequence y_i+1, y_i+2,…, y_N given that the state of the Markov chain at time i is x_i = m. Now β_i is calculated using the following recursive approach.

1.  The Initialization Step: First set β_N(m) = 1, ∀1 ≤ m ≤ M

2.  The Induction Step:

$\begin{array}{l}{\beta }_i\left(k\right)={\displaystyle \sum _{m=1}^M\mathrm{Pr}\left(x_{i+1}=m|x_i=k\right)}\mathrm{Pr}\left(y_{i+1}|x_{i+1}=m\right){\beta }_{i+1}\left(m\right)\\ \text{}\text{}\forall k=1,\dots M,\text{and}i=N-1,N-2,\dots 1.\end{array}$

(7.154)

3.  The Termination Step:

$\mathrm{Pr}\left(y_1,y_2,\dots ,y_N|A,B,\pi \right)={\displaystyle \sum _{m=1}^M{\beta }_1\left(m\right){\pi }_m\mathrm{Pr}\left(y_1|x_1=m\right)}$

(7.155)

Solution to the State Estimation Problem

Unlike the enumeration problem, the optimal solution to the state estimation problem depends on the definition of optimality. One possible optimality measure is to compute the state at each step that maximizes the probability of the outcome at that step. Clearly this approach could result in state sequences that may be infeasible depending on the state transition probabilities. An alternate definition of optimality that is commonly used is to find the state sequence that has highest probability. The well-known Viterbi algorithm provides a computationally efficient method to compute this optimal state sequence. In Chapter 13, the Viterbi algorithm is also shown to be a special case of a generalized message passing algorithm on graphs.

Similar to the forward algorithm, in this case, we define the probabilities δ_i(m) of the partial state sequence and observations up to time i and having state x_i = m, as

${\delta }_i\left(m\right)=\underset{x_1,x_2,\dots ,x_{i-1}}{\max }\mathrm{Pr}\left(x_1,x_2,\dots ,x_{i-1},x_i=m,y_1,y_2,\dots y_i\right)$

(7.156)

Using the principle of induction, it can be easily shown that these probabilities δ_i(m) can be computed as

${\delta }_{i+1}\left(m\right)=\left[\underset{k}{\max }{\delta }_i\left(k\right)\mathrm{Pr}\left(x_{i+1}=m|x_i=k\right)\right]\mathrm{Pr}\left(y_{i+1}|x_{i+1}=m\right)$

(7.157)

It turns out that to find the optimal state sequence, we also need to keep track of the maximizing argument at each step in (7.157). This maximizing argument is thus stored in the ψ_i(m) variables as outlined in the formal Viterbi procedure:

1.  The initialization step

${\delta }_1\left(m\right)={\pi }_m\mathrm{Pr}\left(y_1|x_1=m\right),{\psi }_1\left(m\right)=0,\forall 1\le m\le M$

(7.158)

2.  The recursive step

${\delta }_{i+1}\left(m\right)=\underset{1\le k\le M}{\max }\left[{\delta }_i\left(k\right)\mathrm{Pr}\left(x_{i+1}=m|x_i=k\right)\right]\mathrm{Pr}\left(y_{i+1}|x_{i+1}=m\right)$

(7.159)

${\psi }_{i+1}\left(m\right)=\arg \underset{1\le k\le M}{\max }\left[{\delta }_i\left(k\right)\mathrm{Pr}\left(x_{i+1}=m|x_i=k\right)\right]$

(7.160)

3.  The termination step

$P^{*}=\underset{1\le m\le M}{\max }{\delta }_N\left(m\right)$

(7.161)

${\widehat{x}}_N=\arg \underset{1\le m\le M}{\max }{\delta }_N\left(m\right)$

(7.162)

4.  Backtracking step

${\widehat{x}}_n={\psi }_{n+1}\left({\widehat{x}}_{n+1}\right),n=N-1,N-2,\dots ,1.$

(7.163)

Solution to the Model Parameter Estimation Problem

This problem is the most challenging of all problems in HMMs and there exists no analytical solutions to find the optimal model parameters given a finite observation sequence. However, the model parameters can be selected as a local optimum that maximizes the probability of the observation sequence for that model, using the iterative Baum-Welch algorithm.

Define ϵ_i(m, n) as the conditional probability of being in state x_i = m and x_i+1 = n given the observation. This conditional probability can be expressed in terms of the α_i(m) and β_i(n) variables as,

${ϵ}_i\left(m,n\right)=\frac{{\alpha }_i\left(m\right){\beta }_{i+1}\left(n\right)\mathrm{Pr}\left(x_{i+1}=n|x_i=m\right)\mathrm{Pr}\left(y_{i+1}|x_{i+1}=n\right)}{{\displaystyle {\sum }_{l=1}^M{\displaystyle {\sum }_{l=1}^M{\alpha }_i\left(k\right){\beta }_{i+1}}\left(l\right)}\mathrm{Pr}\left(x_{i+1}=l|x_i=k\right)\mathrm{Pr}\left(y_{i+1}|x_{i+1}=l\right)}$

(7.164)

The iterative procedure is as follows:

1.  Begin with an initial estimate for the parameters of the HMM.

2.  Calculate a new estimate for the parameters as

${\pi }_i={\displaystyle \sum _{j=1}^M{ϵ}_1\left(i,j\right)}$

(7.165)

$a_{ji}=\mathrm{Pr}\left(x_{n+1}=j|x_n=i\right)=\frac{{\displaystyle {\sum }_{n=1}^{N-1}{ϵ}_n\left(i,j\right)}}{{\displaystyle {\sum }_{k=1}^M{\displaystyle {\sum }_{n=1}^{N-1}{ϵ}_n\left(i,k\right)}}}$

(7.166)

$b_{ik}=\frac{\begin{array}{l}{\displaystyle {\sum }_{n=1}^N{\displaystyle {\sum }_{j=1}^M{ϵ}_n\left(i,j\right)}}\\ \text{such}\text{that}{y}_n=k\end{array}}{{\displaystyle {\sum }_{n=1}^N{\displaystyle {\sum }_{j=1}^M{ϵ}_n\left(i,j\right)}}}$

(7.167)

3.  Using the new calculated parameters recalculate ϵ_i using (7.164) and then repeat step 2 above, i.e., evaluate (7.165)–(7.167).

This iterative process is repeated until convergence; as noted before this limit is not the global optimum but a local optimum. It should also be noted that this algorithm can be interpreted as being similar to the Expectation-Maximization (EM) algorithm [11, 12].

7.6      Summary and Further Reading

In this chapter, we provided a brief introduction to probability theory and provided several simple examples to understand the main results. These results form the basis of several chapters in this text. For instance, Markov models and Poisson processes are frequently used in Chapter 17 on queueing theory. Hidden Markov models are considered as a special case of a generalized factor graph-based formulation in Chapter 13. The ideas on conditional probabilities and Bayes result are extensively used in Detection (Chapter 11) and Estimation Theory (Chapter 10). As noted before, several excellent textbooks and papers discuss various aspects of this chapter in great detail [1, 2, 3, 4, 5].

Acknowledgment: This work is supported in part by NSF through grant CCF-0546519.

7.7      Exercises

Exercise 7.7.1. A box contains 100 identical balls numbered from 1 through 100. Let there be 10 balls picked from the box without replacement. What is the probability that the largest numbered ball selected equals 20? What is the probability that the smallest numbered ball selected equals 20?

Exercise 7.7.2. A biased coin has a probability of head equal to p. This biased coin is flipped 5 times. The outcome of each flip is independent of the outcome of the other flips. Let discrete random variable $\mathcal{X}$ denote the number of heads in the first 3 flips and discrete random variable $\mathcal{Y}$ denote the number of tails in the last 3 flips. Find the joint PMF $P_{\mathcal{X},\mathcal{Y}}\left(x,y\right)$ . Are $\mathcal{X}$ and $\mathcal{Y}$ independent?

Exercise 7.7.3. There are two different types of radioactive elements available to a scientist. Type 1 emits radioactive particles with a Poisson distribution and mean of α. Type 2 emits radioactive particles with a Poisson distribution and a mean of β. Let α > β. The scientist does not know apriori which of the two materials he is given, i.e., both materials have a probability of 0.5 of being selected. The scientist can only observe the number of emissions from the source in a given period of time. How should the scientist decide whether the material is type 1 or type 2? In other words, what is the decision rule? What is the probability of making an error using this decision rule?

Exercise 7.7.4. We have a set of M coins, numbered 1, 2,…, M. The probability of getting a head when coin k is tossed equals 1/k. We select one of the coins at random and toss it N times. The sequence of N observations is then given to you. What is your decision rule to determine which of the coins was selected based on your observations?

Exercise 7.7.5. Let $\mathcal{X}\left(t\right)$ be a random process defined by $\mathcal{X}\left(t\right)={\displaystyle \sum }_{i=1}^2{N}_{i}sin\left(2\pi f_{0}t+{\theta }_i\right)$ , where f₀ is a known frequency and all ${\mathcal{N}}_i$ and θ_j are independent random variables. The characteristic function for ${\mathcal{N}}_i$ is ${\text{Φ}}_{N_i}\left(\omega \right)=e^{\left({\text{λ}}_i\left[e^{j\omega }-1\right]\right)}$, where λ_i is a positive constant. Random variable θ_i is uniformly distributed on [−n, +n]. Find the mean and covariance of the process $\mathcal{X}\left(t\right)$ . Is the process $\mathcal{X}\left(t\right)$ wide sense stationary?

Exercise 7.7.6. Consider the motion of a Queen piece on a 3 × 3 chessboard in which the piece moves its position at every integer times starting from t > 0. For simplicity assume that the squares are numbered sequentially from 1 through 9, with the top left square being 1 and the bottom right square being 9. Let ${\mathcal{X}}_t$ denote which vertex the queen is at time t. Assume ${\mathcal{X}}_t,t>0$ is a discrete time Markov process, such that given ${\mathcal{X}}_t$ , the next state ${\mathcal{X}}_{t+1}$ is equally likely to be any one of the legal squares to which the queen may move. (a) Sketch the one step transition probability diagram for ${\mathcal{X}}_t$ . (b) Compute the steady-state probabilities.

Exercise 7.7.7. Let $\mathcal{X}$ and $\mathcal{Y}$ be continuous random variables with a joint PDF given by

$f_{\chi ,\mathcal{Y}}\left(x,y\right)=\{\begin{array}{ll}cxy\hfill & 0<x<1,0<y<1\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

(7.168)

Let $\mathcal{A}=\min \left\{\mathcal{X},\mathcal{Y}\right\}$ and $\mathcal{B}=\max \left\{\mathcal{X},\mathcal{Y}\right\}$ . Compute the joint PDF, $F_{\mathcal{A},\mathcal{B}}\left(a,b\right)$ , b) and marginal PDFs $f_{\mathcal{A}}\left(a\right)$ and $f_{\mathcal{B}}\left(a\right)$ .

Exercise 7.7.8. The value of a particular stock equals $100 on the first of January of a particular year. Every day the price of the stock increases by 2% with probability 0.1 and decreases by 1% with probability 0.2. With a probability of 0.7 the value of the stock remains the same for that day. Let random variable $\mathcal{X}$ represent the value of the stock after 1 year of trading. Compute the probability that the price of the stock exceeds $105 after 1 year.

Exercise 7.7.9. Let continuous random variables ${\mathcal{X}}_i$ , i ≥ 1 be a sequence of i.i.d. random variables with uniform distribution over the interval (0,2). Let discrete random variable $\mathcal{N}$ be independent of ${\mathcal{X}}_i$ and have PMF

$P_{\mathcal{N}}\left(n\right)=\{\begin{array}{ll}1/2\hfill & n=1,2\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

(7.169)

Let random variable $M={\displaystyle \sum _{i=1}^n{\mathcal{X}}_{〉}}$. Find the PDF of $\mathcal{M}$ .

Exercise 7.7.10. Let $\mathcal{Y}\left(t\right)=\mathcal{X}\left(t\right)-a_1\mathcal{X}\left(t-d_1\right)-a_2\mathcal{X}\left(t-d_2\right)$ where a_i and d_i are real constants. Find the autocorrelation and spectral density of $\mathcal{Y}\left(t\right)$ .

Exercise 7.7.11. Consider a random walk over the set {0,1, 2,… M} where the probability of transitioning from state i to state i + 1 equals q and the probability of transitioning from state i to state i − 1 equals 1 − q. From state 0 the probability of transitioning to state 1 equals 1. The probability of transitioning from state M to state M equals q. Find the long-term probability of being in each state i.

Exercise 7.7.12. Compute the autocorrelation of a first order MA process of the form

$Y_n=X_n+\beta X_{n-1}$

(7.170)

where {${\mathcal{X}}_n$ } are i.i.d. with mean μ and variance σ².

Exercise 7.7.13. Consider a packet retransmission system in which the same packet is repeatedly sent by the transmitter until the receiver gets N consecutive correct versions of the packet. Assume that each transmission of the packet has a probability of error of 1 − q and is independent of the other transmissions. What is the expected number of packet transmissions?

Exercise 7.7.14. In source coding, a prefix code or an instantaneous code is one in which no codeword is a prefix of any other codeword. Consider the following prefix code: Symbols {a, b, c, d} are mapped to codewords: 0, 10,110,111, respectively. Consider an i.i.d. sequence of symbols with probabilities of the symbols as Pr (a) = 0.5, Pr (b) = 0.3, Pr(c) = Pr (d) = 0.1. Find the average length of the binary representation of the code. Let ${\mathcal{B}}_n$ represent the sequence of binary symbols that result from the encoding. Find the PMF of ${\mathcal{B}}_n$ .

Exercise 7.7.15. In error control coding, one metric used to measure the performance of a block code is the number of bit errors that it can correct. For instance, in a 2-error correcting code, any bit error combination up to 2 errors can be corrected by the decoder at the receiver. Consider a 5-error correcting code with a resulting codeword of length 100. This length 100 code is transmitted over a binary symmetric channel with crossover probability p = 0.05. Compute the exact probability that all the errors made by the channel can be corrected by the code. Now, estimate this probability using the Central Limit Theorem.

References

[1]  W. Feller, An Introduction to Probability Theory and Its Applications. New York, Wiley, 1968.

[2]  S. Kay, Intuitive Probability and Random Processes Using MATLAB, 8th ed. Springer, New York, 2005.

[3]  A. Leon-Garcia, Probability, Statistics and Random Processes for Electrical Engineering, 3rd ed. Prentice Hall, Upper Saddle River, NJ, 2008.

[4]  S. Ross, A First Course in Probability. Prentice Hall, Upper Saddle River, NJ, 2009.

[5]  R. Yates and D. J. Goodman, Probability and Stochastic Processes: A Friendly Introduction for Electrical and Computer Engineers, 2nd ed. Hoboken, NJ: John Wiley and Sons Inc., 2004.

[6]  S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Application, 2nd ed., Prentice Hall, Upper Saddle River, NJ, 2004.

[7]  W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, vol. 58, no. 301, pp. 13–30, March 1963.

[8]  A. Papoulis and U. S. Pillai, Probability, Random Variables and Stochastic Processes. McGraw-Hill, New York, NY, 2002.

[9]  T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. Wiley, New York, 2006.

[10]  L. Rabiner, “A tutorial on hidden Markov models and selected applications in speech recognition,” Proceedings of the IEEE, vol. 77, no. 2, pp. 257–286, February 1989.

[11]  A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” Journal of the Royal Statistical Society, vol. 39, pp. 1–38, 1977.

[12]  M. Gupta and Y. Chen, “Theory and use of EM algorithm,” Foundations and Trends in Signal Processing, vol. 4, pp. 223–296, 2010.