# Can a $\require{enclose}\enclose{horizontalstrike}{z-transform}$ Probability Generating Function be used to solve this recurrence relation?

Imagine a simple random walk where $x_n=\sum_{i=0}^ny_i$ and $y_i = \begin{cases} 1, & \text{with prob 1/2} \\ -1, & \text{with prob 1/2} \end{cases}$

Then say we want to find the probability that we reach a certain positive value before a negative one (i.e., the probability we reach 100 before reaching -50), given an arbitrary starting point $-50<k<100$. We'll denote $f_k$ as the probability of reaching k=100. We know $f_{100}=1$ and $f_{-50}=0$. Then a recursion can be formed with $f_k = 0.5f_{k+1} + 0.5f_{k-1}$.

Maybe I'm fooling myself by writing it in this form because now I want to use a $\require{enclose}\enclose{horizontalstrike}{z-transform}$ Probability Generating Function instead of drawing out a huge system of linear equations to solve it. However I'm not sure how to go about it. I should note i have more of a signal processing background where the z-transform is commonly used for transformations of signals to the frequency domain.

I'd like to extend to a similar problem such as the expected number of flips of a fair coin to get n heads in a row, where $u_k$ is the expected number of flips to reach n heads in a row after seeing $k$ heads, and $u_k=1+0.5u_{k+1} + 0.5u_0$

So perhaps it's a more general question on using a $\require{enclose}\enclose{horizontalstrike}{z-transform}$ Probability Generating Function to solve recurrence relations, but providing explanations for these examples would help me "get it" I think.

• You'll probably get more traction here if you use the term probability generating function (which is essentially the same thing as a z-transform, in the same way that characteristic functions are essentially Fourier transforms and MGFs are essentially Laplace transforms, in each case up to a flipped sign in the definition). Probability generating functions are indeed useful in all manner of recurrence problems. Commented Dec 25, 2017 at 0:38
• @Glen_b thanks! I'm in that space where I don't know what i don't know, and comments like this are extremely helpful.
– JPJ
Commented Dec 25, 2017 at 16:30
• If a result like this is known, you are most likely to succeed by starting to search for a formulation of the Binomial Options Pricing model that uses the PGF. You will see here that your problem is very similar: en.wikipedia.org/wiki/Binomial_options_pricing_model Commented Dec 25, 2017 at 17:45