Random walk on one-dimensional lattice - understanding the expression $pe^{i\theta} + qe^{-i\theta}$

Question

I've started reading the book - First Steps in Random Walks and in the very first example in Chapter 1 they talk about a random walk on a one-dimensional lattice.

If we consider a particle starting from $0$, it says that steps to the right are performed with probability $p$ and steps to the right are performed with probability $q = 1 - p$. The position of the particle after $n$ steps is determined by the number of steps to the right and to the left.

It then introduces the following expression that it describes as an instrument that allows for finding the positions of the particle -

$$pe^{i\theta} + qe^{-i\theta}$$ with the coefficients $p$ and $q$ being the probabilities that the first step was to the right and left respectively.

If we square the expression

$$(pe^{i\theta} + qe^{-i\theta})^2 = p^2 e^{2i\theta} + 2pq + q^2 e^{-2i\theta}$$

it says that the coefficient of the first term of the expansion gives the probability that the first two steps were to the right, the second term corresponds to the probability that the first two steps were made in opposite directions, and the coefficient of the third term gives the probability that the first two steps were to the left.

Question

I don't see the reasoning for the expression $$pe^{i\theta} + qe^{-i\theta}$$

1. Where are they getting this complex analysis type expression from?
2. Why are we dealing with $\theta$ when we are in a one dimensional space?
3. Why does squaring the expression 'magically' gives the probabilities of where we will be after two steps?

Answer 1

These are what are called characteristic functions: the characteristic function of a random variable $X$ is $$ \chi_X(t):=\mathbb{E}[e^{itX}]. $$ (You can view this as, essentially, the Fourier transform of the probability measure associated with $X$; if that doesn't make sense, don't worry about it.)

What's nice about characteristic functions is that they uniquely determine probability distributions much like CDFs or PDFs do. In addition, pointwise convergence of a sequence of characteristic functions actually gives you information about convergence in distribution of the corresponding sequence of random variables.

In this case, $\theta$ is not used to represent an angle; rather, we let $\theta_1,\theta_2,\ldots$ be defined as follows: let $\theta_j=1$ if we take a step to the right at time $j$, and let $\theta_j=-1$ if we take a step to the left. Then $S_n:=\theta_1+\cdots+\theta_n$ is precisely our position at time $n$, assuming that we start at $0$.

What is the characteristic function of $S_n$? We need to remember one fact: If $X$ and $Y$ are independent, then $\mathbb{E}[XY]=\mathbb{E}[X]\cdot\mathbb{E}[Y]$. We have $$ \chi_{S_n}(t)=\mathbb{E}[e^{itS_n}]=\mathbb{E}[e^{it\theta_1}e^{it\theta_2}\cdots e^{it\theta_n}]; $$ but, we assume that $\theta_1,\ldots,\theta_n$ are independent and identically distributed, so that $S_2=-2$ with probability $q^2$, $S_2=0$ with probability $2pq$, and $$\tag{1} \chi_{S_n}(t)=\prod_{j=1}^{n}\mathbb{E}[e^{it\theta_j}]=\left(\mathbb{E}[e^{it\theta_1}]\right)^n=(e^{it\cdot1}p+e^{it\cdot(-1)}q)^n. $$ On the other hand, we know that $$\tag{2} \mathbb{E}[e^{itS_n}]=\sum_{j=-n}^{n}e^{itj}P(S_n=j). $$ But (1) and (2) are equal for all $t$ if and only if the coefficient by $e^{itj}$ on each side of the equation is the same for each $j$. So, for instance, we see that $$ \chi_{S_2}(t)=(pe^{it}+qe^{-it})^2=p^2e^{i2t}+2pqe^{i0t}+q^2e^{i(-1)t}, $$ we see that $S_2=-2$ with probability $q^2$, $S_2=0$ with probability $2pq$, and $S_2=2$ with probability $p^2$; all other values have probability 0.

Answer 2

For every $\theta$, $p\mathrm e^{\mathrm i\theta} + q\mathrm e^{-\mathrm i\theta}$ is the expected value of the random variable $e^{\mathrm i\theta X_1}$, where $X_1$ is the position of the particle at time $1$. Likewise, for every $n\geqslant1$, the position $X_n$ of the particle at time $n$ is the sum of $n$ independent random variables distributed like $X_1$ hence the expected value of $\mathrm e^{\mathrm i\theta X_n}$ is $$\left(p\mathrm e^{\mathrm i\theta} + q\mathrm e^{-\mathrm i\theta}\right)^n. $$ By definition of the expectation of $\mathrm e^{\mathrm i\theta X_n}$, for every integer $k$, the probability that $X_n=k$ is the coefficient of $\mathrm e^{\mathrm i\theta k}$ in this expectation, that is, the coefficient of $\mathrm e^{\mathrm i\theta k}$ in $\left(p\mathrm e^{\mathrm i\theta} + q\mathrm e^{-\mathrm i\theta}\right)^n$. Expanding this by the binomial theorem yields the probability that $X_n=n-2k$ as $$ {n\choose k}p^{n-k}q^k, $$ for every $0\leqslant k\leqslant n$ (and obviously the probability that $X_n=i$ for some integer $i$ not in this set is zero).