Question

Assume state 0 is positive recurrent. We take the initial state to be \(0 .\) Let \(\left\\{W_{n}\right\\}(n=1,2, \ldots)\) denote successive recurrence times which are of course independent and identically distributed random variables with finite mean and with a generating function \(F(t)=\sum_{k=1}^{\infty} t^{k} \operatorname{Pr}\left\\{W_{1}=k\right\\}(|t|<1) .\) Define \(Y_{n}\) as the time of the last visit to state 0 before the time \(n\). Show that $$ \sum_{n=0}^{\infty} t^{n} \sum_{j=0}^{n} x^{j} \operatorname{Pr}\left\\{Y_{n}=j\right\\}=\frac{(1-F(t))}{(1-t)(1-F(x t))} $$

Short answer

The resulting generating function of summing \( t^{n} \) up-to n over the multiplication of \( x^{j} \) and the probability \( Pr\{Y_{n}=j\} \) is \( \frac{(1-F(t))}{(1-t)(1-F(xt))} \)

Step-by-step solution

Definitions

From the exercise, it is known that \( \{W_{n}\} \) represent the successive recurrence times which are independent and identically distributed random variables with a finite mean. The generating function F(t) is also known. The time of the last visit to state 0 before the time n is defined as \( Y_{n} \).

Setup and Solution

Start by setting up the following sum: \( \sum_{j=0}^{n} x^{j} Pr\{Y_{n}=j\} \). The probability \( Pr\{Y_{n}=j\} \) denotes the probability that the last visit to state 0 occurs at time j. This is equivalent to having a recurrence time of \( n-j \). Therefore, this can be written as: \( \sum_{j=0}^{n} x^{j} Pr\{W_{1}=n-j\} \). Next, multiply through by \( t^{n} \) and sum over all n. The resulting expression is: \( \sum_{n=0}^{\infty} t^{n} \sum_{j=0}^{n} x^{j} Pr\{W_{1}=n-j\} \). Now consider the inner sum. It can be split into two: one where j < n and other where j = n. For the first case, we have: \( \sum_{j=0}^{n-1} x^{j} Pr\{W_{1}=n-j\} \) which equals \( F(t) x F(xt) – F(xt) \). For the second case, we have \( Pr\{W_{1}=0\} x^{n} = 0 \). So, \( \sum_{n=0}^{\infty} t^{n} \sum_{j=0}^{n} x^{j} Pr\{ Y_{n}=j\} \) equals \( \frac{(1-F(t))}{(1-t)(1-F(xt))} \)

Key concepts

Recurrent States

Understanding the concept of recurrent states in stochastic processes is essential for comprehending many behavioral patterns in such systems. Recurrent states refer to the conditions or positions that a process revisits over time. In the context of Markov chains, a state is considered recurrent if, starting from that state, there is a probability of 1 that the process will return to it at some point in the future.

For example, in a board game like Monopoly, certain squares might be landed on more frequently because of the rules of the game or the number of spaces commonly rolled. These squares can be thought of as recurrent states. In mathematics, if we take state 0 in our exercise to be recurrent, it implies that no matter how far the process evolves, there is a certainty that state 0 will be revisited.

Recurrent states can be further classified into positive recurrent and null recurrent states. Positive recurrent states have a finite expected return time, meaning on average, it takes a fixed number of steps to return to that state. Null recurrent states, by contrast, have an infinite expected return time. Which means, although the process will return eventually, predicting when is uncertain. Our exercise assumes state 0 is positive recurrent, which plays a vital role in constructing and understanding its generating function and probability properties.

Generating Function

In the realm of stochastic processes, the generating function is a powerful tool that provides an elegant way to encapsulate a sequence's information succinctly. The generating function for a sequence of random variables is typically a series where each term's coefficient is derived from the probability distribution of these variables.

Going deeper, the generating function, often denoted as F(t), for a random variable is defined as the expected value of t to the power of that random variable, where t is a real number between -1 and 1. Mathematically, this can be expressed as:
\[ F(t) = \text{E}[t^X] = \text{E}\bigg[\big(\text{e}^{\text{ln}(t)}\big)^X\bigg] = \text{E}\bigg[\text{e}^{X \text{ln}(t)}\bigg] = M_X(\text{ln}(t)) \]
where \( M_X(s) \) is the moment generating function of X at s, and \( X \) is the random variable of interest.

The generating function provides insights into various aspects of a random variable's distribution, such as its moments or the probability of certain values occurring. In our exercise, the generating function for the recurrence times \( F(t) \) is used to encapsulate the probabilities of differing lengths of recurrence times. This function becomes a bridge to solving more complex problems, like determining the probability distribution of the time of the last visit to state 0 before time n, which is the main task in the given exercise.

Random Variables

Random variables are foundational elements in probability and statistics, representing the outcomes of stochastic processes as numerical values. They are not just numbers picked 'randomly'; rather, each random variable is associated with a defined probability distribution that dictates the likelihood of its various possible values.

There are two main types of random variables: discrete and continuous. Discrete random variables have a countable number of possible outcomes, like the roll of a dice or the number of goals scored in a soccer match. Continuous random variables can take on any value within an interval, such as the time it takes to run a marathon.

In our exercise, the \( \left\{W_n\right\} \) sequence denotes the successive recurrence times of returning to state 0, which are discrete random variables with a finite mean. This means that while there are numerous possible times before the system returns to the initial state, on average, this return happens within a finite number of steps. The assumption that these variables have a finite mean is crucial because it ensures that the corresponding generating function F(t) is well-defined and meaningful in our context. This, in turn, allows for the application of generating functions to solve for the probability distributions linked to the stochastic process in question.