Question

Suppose \(\quad X_{1}, \quad X_{2}, \ldots\) are independent with \(\operatorname{Pr}\left\\{X_{k}=+1\right\\}=p\), \(\operatorname{Pr}\left\\{X_{k}=-1\right\\}=q=1-p\) where \(p \geq q .\) With \(S_{0}=0\), set \(S_{n}=X_{1}+\cdots+X_{n}\) \(M_{n}=\max \left\\{S_{k}: 0 \leq k \leq n\right\\}\) and \(Y_{n}=M_{n}-S_{n} .\) If \(T(a)=\min \left\\{n: S_{n}=a\right\\}\), show Hint: The bivariate process \(\left(M_{n}, Y_{n}\right)\) is a random walk on the positive lattice. What is the probability that this random walk leaves the rectangle

Short answer

In order to show that the bivariate process \((M_n, Y_n)\) is a random walk on the positive lattice and to obtain the probability that the random walk leaves the rectangle, we examined the behaviors of the sequences \(S_n, M_n, Y_n\). We identified how \(M_n\) and \(Y_n\) correspond to coordinates on a lattice in the first quadrant and found up and right movements to be the only possible directions. By analyzing the probability of leaving the rectangle, we determined that it is equal to 1. Finally, we used this information to connect the probabilities for \(T(a)\) with the random walk on the lattice, showing that the probability of reaching point \((a, 0)\) can be calculated through the study of paths on the positive lattice.

Step-by-step solution

Examine the behavior of \(S_n\)

The sequence \(S_n = X_1 + X_2 + \cdots + X_n\) represents the position of the random walk after n steps. Since \(X_k = +1\) with probability p and \(X_k = -1\) with probability q and the steps are independent, we can analyze it as a typical random walk. It starts at position 0 and can move left or right with probabilities q and p, respectively.

Analyze the behavior of \(M_n\)

The sequence \(M_n = \max\{S_k: 0 \leq k \leq n\}\) tracks the maximum value reached by the random walk \(S_n\) up to step n. Since the walk can move left and right, the maximum value can either stay the same or increase by 1 after each step.

Investigate the behavior of \(Y_n\)

The sequence \(Y_n = M_n - S_n\) represents the distance between the current position of the random walk and its maximum value achieved until step n. After each step, this could either stay the same (when a new maximum is achieved), or increase by 1 (when the walk steps to the left).

Relate \((M_n, Y_n)\) to a random walk on a positive lattice

Given the behaviors of \(M_n\) and \(Y_n\), we can view \((M_n, Y_n)\) as coordinates on a lattice in the first quadrant, where \(M_n\) and \(Y_n\) correspond to the x and y coordinates, respectively. Following each step in the original random walk: - \(Y_n\) can stay the same (when a new maximum is achieved), which would translate to a right movement on the lattice with probability p. - \(Y_n\) can increase by 1 (when the walk steps to the left), corresponding to an upward movement on the lattice with probability q. Therefore, \((M_n, Y_n)\) acts as a random walk on a positive lattice.

Determine the probability of leaving a rectangle

Next, we can find the probability of leaving a rectangle in the positive lattice using the properties of \((M_n, Y_n)\). Let the rectangle be defined by the equations \(M_n = x\) and \(Y_n = y\). Since we know that up and right movements are the only possible directions, we will leave the rectangle if: - \(M_n\) increases to \(x+1\), which happens with probability p. - \(Y_n\) increases to \(y+1\), which happens with probability q. Thus, the probability of leaving the rectangle is given by \(p + q = 1\).

Connect the information to \(T(a)\)

Now we need to show the connection between the random walk on the lattice and \(T(a)\). Recall that \(T(a) = \min\{n: S_n = a\}\). This means that the walk reaches that value a for the first time in n steps. We can view this as the point on the \((M_n, Y_n)\) lattice corresponding to the coordinates \((a,0)\), since \(Y_n=0\) when \(S_n=M_n\). To compute the probability of arriving at a point \((a, 0)\) on the \((M_n, Y_n)\) lattice, we can count all the possible paths from the origin \((0,0)\) to that point. We know that the probability of leaving a rectangle is 1, so the probability of reaching point \((a, 0)\) is equal to the sum of probabilities from all possible paths leading to this point.

Conclusion

Using the hint that \((M_n, Y_n)\) is a random walk on the positive lattice, we have analyzed how the sequences \(S_n\), \(M_n\), and \(Y_n\) together provide insights into using the probability of leaving the lattice to compute the probability of reaching point \((a, 0)\), which happens precisely when \(T(a) = n\). This means that the probability files associated with \(T(a)\) can be calculated through the study of paths on the positive lattice.