WienerHopf Factorization:
Probabilistic Methods
Philippe Robert
Inria Rocquencourt
Algorithms Seminar
March 17, 1997
[summary by JeanFrançois Dantzer]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
1 Introduction
We consider a discrete random walk on Z, defined by
S_{0}=0 and 
S_{n}= 

X_{i}, n>0, 
where (X_{i})_{i³ 1} is an independent identically
distributed (i.i.d.) sequence of random variables.
We define two hitting times n_{+} and n_{},
n_{+}=inf{k>0/S_{k}>0}, n_{}=inf{k>0/S_{k}£ 0},
with the convention inf(Ø)=+¥.
Figure 1: Random walks (S_{n})_{n³ 0} and (S_{n+n}_{})_{n³ 0} (in
dotted line)
We also define M and L two variables indicating respectively the
maximum of the random walk and the hit moments at which it is attained
M= 

{S_{n}}, L= 

{S_{n}=M}. 
This talk presents the classical probabilistic methods to derive the
join distributions of (n_{+},S_{n}_{+}), (n_{},S_{n}_{}) and (M,L).
Applications of these results have been found in
biology [3, 4] or in queueing theory [2]. For more
details on this subject, see [1, 5].
2 Distribution of (n_{+},S_{n}_{+}) and (n_{},S_{n}_{})
The distributions of the pairs (n_{+},S_{n}_{+})
and (n_{},S_{n}_{}) will be expressed through their generating
functions, i.e., E(u^{n}_{+}z^{S}_{n}_{+}) and E(u^{n}_{}z^{S}_{n}_{}).
We consider three variables
Y_{+}(u,z) 

on {u<1,z£ 1}, 
Y_{}(u,z) 

on {u<1,z³ 1}, 
Y (u,z) 

on {u<1,z= 1}. 
The main result, the factorization of WienerHopf described in
the following proposition, gives an analytic characterization of Y_{+} and
Y_{}.
Proposition 1
Y can be uniquely decomposed on {z=1} as:
Y (u,z)=Y_{+} (u,z)Y_{} (u,z),
where Y_{+} and Y_{} have the following properties:

Y_{+} is analytic on {z<1};
 Y_{+} and 1/Y_{+} are continuous and bounded on {z£ 1};
 Y_{+}(u,0)=1;
and

Y_{} is analytic on {z>1};
 Y_{} and 1/Y_{} are continuous and bounded on
{z³ 1}.
Proof.
The proof is based on the following arguments:

The function Y can be expressed with the distribution of X_{1},
the sequence (X_{i})_{n³ 1} is independent identically
distributed, then E(Z^{S}_{n})=E(Z^{å}_{i=1}^{n}^{X}_{i})=E(Z^{X}_{1})^{n}, thus
Y (u,z)= 

u^{n} E(z 

)^{n}= 

; 
 (S_{n})_{n³ 0} and (S_{n+n}_{})_{n³ 0} have same
distribution, (S_{n+n}_{})_{n³ 0} is the
random walk beginning at the time n^{};
 The independence between the pair (n_{},S_{n}_{}) and the
sequence (S_{n+n}_{})_{n³ 0};
 the same properties are also valid for (S_{n+n}_{+})_{n³ 0}.
3 Examples
The factorization is easy when Y has a finite number of
poles and zeros. We consider two such examples.
3.1 Random walk ± 1
We suppose X_{i}=1 with probability p and X_{i}=1 with probability
(1p). In that case,
Y has only two poles
a_{1}(u)= 
1(14u^{2}p(1p))^{1/2} 

2up 

, a_{2}(u)= 
1+(14u^{2}p(1p))^{1/2} 

2up 

, 
with 0£a_{1}(u)£ 1£a_{2}(u).
The decomposition gives:
Y_{+}(u,z)= 

and
Y_{}(u,z)= 

. 
Here, we obtain the generating functions:
E(u 

z 

)= 

, E(u 

z 

)=(1a_{2}(u)up)+ 

. 
3.2 Random walk left bounded
We suppose Pr(X_{i}<1)=0.
In that case, the factorization is easy because by Rouché's
theorem the function
z® zuE(z^{X+1}) has one only root which belongs to
{z<1}, which we denote by a (u). One proves that
a (u)Î [0,1] and the decomposition of Y is the following:
Y_{+}(u,z)= 


, Y_{}(u,z)= 


, 
and the generating functions are:
4 Distribution of the Maximum and its first Hitting time (M,L)
The distribution of the pair (M,L) is expressed through its generating
function E(x^{L}z^{M}).
Proof.
We define the variables M_{n} and L_{n}, as
M_{n}= 

S_{k}, L_{n}=inf{k/S_{k}=M_{n}}, 
and the function H on {u<1,x< 1, z< 1} as
Using the same arguments as in proposition 1, it can be proved that:
H(u,x,z)= 
Y_{+}(ux,z) 

Y_{+}(u,1)(1u) 

. 
We conclude applying

(1u)H(u,x,z)= 

(1u)E( 

u^{n}x 

z 

)= 

E(x 

z 

)=E(x^{L}z^{M}). 
For the case of the random walk of subsection 3.1, it gives for p<1/2:
then
Pr(L<+¥,M<+¥)=1,
and the distribution of M is geometric with parameter
p/1p,
for p>1/2:
E(x^{L}z^{M})=0 and
Pr(L=M=+¥)=1.
References
 [1]

Feller (William). 
An introduction to probability theory and its applications. 
John Wiley & Sons, New York, 1971, 2nd edition,
vol. II.
 [2]

Iglehart (Donald L.). 
Extreme values in the GI/G/1 queue. Annals of Mathematical
Statistics, vol. 43, n°2, 1972, pp. 627635.
 [3]

Karlin (Samuel) and Altschul (Stephen F.). 
Methods for assesing the statistical significance of molecular
sequences features by using general scoring schemes. Proceedings of the
National Academy of Sciences of the USA, vol. 87, 1990,
pp. 22642268.
 [4]

Karlin (Samuel) and Dembo (Amir). 
Strong limit theorems of empirical functionals for large exedances of
partial sums of i.i.d. variables. Annals of Probability, vol. 19,
n°4, 1991, pp. 17371755.
 [5]

Spitzer (F.). 
Principles of Random Walk. 
Van Nostrand, 1964.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.