Random variables and sum

Question

Consider a sequence of random variable $(S_k)$ as sum of random variables $F_k$ I want to compute: $P(\pi_m =k+s)= \sum_j P(\S_k=s)P(F_k=k+j)$, where $\pi_m=m+F_m$

Answer 1

I write here as best an explanation as I can, even if it is difficult to discuss this without figures. I hope in any case my explanation can give some ideas to think.

Let $X_i,i=1,..$ be i.i.d. random integer $\ge 0$ variables.

Let $Y_k=\sum_{i=1}^k X_i$

Let $T_m=min_{t\ge1}\{t \ | \ Y_t+m =t\}$

Than it holds:

$P(T_m=m+n)=\sum_{j=1}^{n} P(Y_m=j)P(T_j=n) , \ m,n \ge 1$

Let's call $S_{k,m}=Y_k+m, m\ge 1$ the shifted process. Note that: $T_m=min_{t\ge1}\{t \ | \ S_{k,m}=t\}$.

We can say more:

• $S_{k,m}=Y_k+m \ge m$ [1];
• $T_m \ge m$ [2];

(why?)

Now let's consider the event $A=\{ T_m=m+n \}$. We have $S_{m,m} \ge m$ in general because of [1]. Further, since on $A$ the hitting time is $m+n$ we must have $S_{m,m} \le m+n$, because otherwise the hitting time could not happen at $m+n$. This implies that on $A$ we have $1 \le Y_m \le n$. We condition than on the possible values of $S_{m,m}=m+j$:

$P(T_m=m+n)=\sum_{j=1}^n P(S_{m,m}=m+j)P(T_m=m+n|S_{m,m}=m+j)$ [3]

Since the process is shift invariant, we have that the probability starting at $m+j$ at time equal to $m$ and hit for the first time the diagonal at $m+n$ is exactly to the probability of starting at $j$ at $t=1$ and hit the diagonal at time $n$:

$P(T_m=m+n|S_{m,m}=m+j)=P(T_j=n)$ [4]

Putting together [3], [4] and changing $S$ with $Y$ we get the thesis.