# On the convergence of multiple Fourier series of functions of bounded
partial generalized variation

Ushangi Goginava and Artur Sahakian  U. Goginava, Department of Mathematics,
Faculty of Exact and Natural Sciences, Iv. Javakhishvili Tbilisi State
University, Chavchavadze str. 1, Tbilisi 0128, Georgia<EMAIL_ADDRESS>A. Sahakian, Yerevan State University, Faculty of Mathematics and Mechanics,
Alex Manoukian str. 1, Yerevan 0025, Armenia<EMAIL_ADDRESS>
###### Abstract.

The convergence of multiple Fourier series of functions of bounded partial
$\Lambda$-variation is investigated. The sufficient and necessary conditions
on the sequence $\Lambda=\\{\lambda_{n}\\}$ are found for the convergence of
multiple Fourier series of functions of bounded partial $\Lambda$-variation.

00footnotetext: 2010 Mathematics Subject Classification: 42B08 Key words and
phrases: Fourier series, Bounded $\Lambda$-variation .

##  1\. Classes of Functions of Bounded Generalized Variation

In 1881 Jordan [10] introduced a class of functions of bounded variation and
applied it to the theory of Fourier series. Hereafter this notion was
generalized by many authors (quadratic variation, $\Phi$-variation,
$\Lambda$-variation ets., see [10, 15, 14, 11]). In two dimensional case the
class BV of functions of bounded variation was introduced by Hardy [9].

Let $T:=[0,2\pi]$ and

$J^{k}=\left(a^{k},b^{k}\right)\subset T,\qquad k=1,2,\ldots d.$

Consider a measurable function $f\left(x\right)$ defined on $R^{d}$ and
$2\pi$-periodic with respect to each variable. For $d=1$ we set

$f\left(J^{1}\right):=f\left(b^{1}\right)-f\left(a^{1}\right).$

If for any function of $d-1$ variables the expression
$f\left(I^{1}\times\cdots\times I^{d-1}\right)$ is already defined, then for a
function of $d$ variables the mixed difference is defined as follows:

$f\left(J^{1}\times\cdots\times J^{d}\right):=f\left(J^{1}\times\cdots\times
J^{d-1},b^{d}\right)-f\left(J^{1}\times\cdots\times J^{d-1},a^{d}\right).$

Let $E=\\{I_{k}\\}$ be a collection of nonoverlapping intervals from $T$
ordered in arbitrary way and let $\Omega$ be the set of all such collections
$E$. We denote by $\Omega_{n}$ the set of all collections of $n$
nonoverlapping intervals $I_{k}\subset T.$

For sequences of positive numbers
$\Lambda^{j}=\\{\lambda^{j}_{n}\\}_{n=1}^{\infty}$, $j=1,2,\ldots,d$, the
$\left(\Lambda^{1},\ldots,\Lambda^{d}\right)$-variation of $f$ with respect to
index set $D:=\\{1,2,...,d\\}$ is defined as follows:

$V_{\Lambda^{1},\ldots,\Lambda^{d}}^{D}\left(f\right):=\sup\limits_{\\{I_{i_{j}}^{j}\\}_{i_{j}=1}^{k_{j}}\in\Omega}\
\sum\limits_{i_{1},...,i_{d}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|}{\lambda_{i_{1}}\cdots\lambda_{i_{d}}}.$

For an index set $\alpha=\\{j_{1},...,j_{p}\\}\subset D$ and any
$x=\left(x^{1},...,x^{d}\right)\in R^{d}$ we set
${\widetilde{\alpha}}:=D\setminus\alpha$ and denote by $x^{\alpha}$ the vector
of $R^{p}$ consisting of components $x^{j},j\in\alpha$, i.e.

$x^{\alpha}=\left(x^{j_{1}},...,x^{j_{p}}\right)\in R^{p}.$

By
$V_{\Lambda^{j_{1}},...,\Lambda^{j_{p}}}^{{\alpha}}\left(f,x^{\widetilde{\alpha}}\right)$
and $f\left(I_{i_{j_{1}}}^{1}\times\cdots\times
I_{i_{j_{p}}}^{p},x^{\widetilde{\alpha}}\right)$ we denote respectively the
$\left(\Lambda^{j_{1}},...,\Lambda^{j_{p}}\right)$-variation and the mixed
difference of $f$ as a function of variables $x^{j_{1}},...,x^{j_{p}}$ over
the $p$-dimensional cube $T^{p}$ with fixed values $x^{\widetilde{\alpha}}$ of
other variables. The
$\left(\Lambda^{j_{1}},...,\Lambda^{j_{p}}\right)$-variation of $f$ with
respect to index set ${\alpha}$ is defined as follows:

$V_{\Lambda^{j_{1}},...,\Lambda^{j_{p}}}^{{\alpha}}\left(f\right)=\sup\limits_{x^{{\widetilde{\alpha}}}\in
T^{d-p}}V_{\Lambda^{j_{1}},...,\Lambda^{j_{p}}}^{{\alpha}}\left(f,x^{\widetilde{\alpha}}\right).$

######  Definition 1.

We say that the function $f$ has total Bounded
$\left(\Lambda^{1},...,\Lambda^{d}\right)$-variation on $T^{d}=[0,2\pi]^{d}$
and write $f\in BV_{\Lambda^{1},...,\Lambda^{d}}$, if

$V_{\Lambda^{1},...,\Lambda^{d}}(f):=\sum\limits_{\alpha\subset
D}V_{\Lambda^{j_{1}},...,\Lambda^{j_{p}}}^{{\alpha}}\left(f\right)<\infty.$

######  Definition 2.

We say that the function $f$ is continuous in
$\left(\Lambda^{1},...,\Lambda^{d}\right)$-variation on $T^{d}=[0,2\pi]^{d}$
and write $f\in CV_{\Lambda^{1},...,\Lambda^{d}}$, if

$\lim\limits_{n\rightarrow\infty}V_{\Lambda^{j_{1}},...,\Lambda^{j_{k-1}},\Lambda_{n}^{j_{k}},\Lambda^{j_{k+1}},...,\Lambda^{j_{p}}}^{{\alpha}}\left(f\right)=0,\qquad
k=1,2,\ldots,p$

for any $\alpha\subset D,\ \alpha:=\\{j_{1},...,j_{p}\\}$, where
$\Lambda_{n}^{j_{k}}:=\left\\{\lambda_{s}^{j_{k}}\right\\}_{s=n}^{\infty}$.

######  Definition 3.

We say that the function $f$ has Bounded Partial
$\left(\Lambda^{1},...,\Lambda^{d}\right)$-variation and write $f\in
PBV_{\Lambda^{1},...,\Lambda^{d}}$ if

$PV_{\Lambda^{1},...,\Lambda^{d}}(f):=\sum\limits_{i=1}^{d}V_{\Lambda^{i}}^{\\{i\\}}\left(f\right)<\infty.$

In the case $\Lambda^{1}=\cdots=\Lambda^{d}=\Lambda$ we denote

$BV_{\Lambda}:=BV_{\Lambda^{1},...,\Lambda^{d}},\quad
CV_{\Lambda}:=CV_{\Lambda^{1},...,\Lambda^{d}},\quad
PBV_{\Lambda}:=PBV_{\Lambda^{1},...,\Lambda^{d}}$

and

$CV_{\Lambda}:=V_{\Lambda^{1},...,\Lambda^{d}}(f)CV_{\Lambda},\qquad
PV_{\Lambda}(f):=PV_{\Lambda^{1},...,\Lambda^{d}}(f).$

If $\lambda_{n}\equiv 1$ (or if $0<c<\lambda_{n}<C<\infty,\ n=1,2,\ldots$) the
classes $BV_{\Lambda}$ and $PBV_{\Lambda}$ coincide with the Hardy class $BV$
and $PBV$ respectively. Hence it is reasonable to assume that
$\lambda_{n}\rightarrow\infty$ and since the intervals in $E=\\{I_{i}\\}$ are
ordered arbitrarily, we suppose, without loss of generality, that the sequence
$\\{\lambda_{n}\\}$ is increasing. Thus,

(1)
$1<\lambda_{1}\leq\lambda_{2}\leq\ldots,\qquad\lim_{n\rightarrow\infty}\lambda_{n}=\infty.$

When $\lambda_{n}=n$ for all $n=1,2\ldots$ we say Harmonic Variation instead
of $\Lambda$-variation and write $H$ instead of $\Lambda$ ($BV_{H}$,
$PBV_{H}$, $CV_{H}$, ets).

######  Remark 1.

The notion of $\Lambda$-variation was introduced by Waterman [14] in one
dimensional case, by Sahakian [13] in two dimensional case and by Sablin [12]
in the case of higher dimensions. The notion of bounded partial variation
(class $PBV$) was introduced by Goginava in [6, 7]. These classes of functions
of generalized bounded variation play an important role in the theory Fourier
series.

Observe, that the number of variations in Definition 1 of total variation is
$2^{d}-1$, while the number of variations in Definition 2 of partial variation
is only $d$.

The statements of the following theorem are known.

######  Theorem A.

1) (Dragoshanski [5]) If $d=2$, then $BV_{H}=CV_{H}$.

2) (Bakhvalov [1]) $CV_{H}=\bigcup_{\Gamma}BV_{\Gamma}$ for any $d$, where the
union is taken over all sequences $\Gamma=\\{\gamma_{n}\\}_{n=1}^{\infty}$
with $\gamma_{n}=o(n)$ as $n\rightarrow\infty$.

3) (Goginava, Sahakian [8]) If $d=2$, then $PBV_{\Lambda}\subset BV_{H}$,
provided that

(2) $\frac{\lambda_{n}}{n}\downarrow
0\quad\mathrm{{and}\quad\sum\limits_{n=1}^{\infty}\frac{\lambda_{n}}{n^{2}}<\infty,}$

Using the third statement of Theorem A, we have proved in [8] the convergence
of double Fourier series of functions of any class $PBV_{\Lambda}$ with (2).
To obtain similar result for higher dimensions we need stronger result, since
the inclusion $PBV_{\Lambda}\subset BV_{H}$ is not enough in this case (see
next section for details).

######  Theorem 1.

Let $\Lambda=\\{\lambda_{n}\\}_{n=1}^{\infty}$ and $d\geq 2$. If

(3) $\frac{\lambda_{n}}{n}\downarrow
0\quad\mathrm{{and}\quad\sum\limits_{n=1}^{\infty}\frac{\lambda_{n}\log^{d-2}n}{n^{2}}<\infty,}$

then there exists a sequence $\Gamma=\\{\gamma_{n}\\}_{n=1}^{\infty}$ with

(4) $\gamma_{n}=o(n)\quad\mathrm{as}\quad n\rightarrow\infty,$

such that $PBV_{\Lambda}\subset BV_{\Gamma}$.

###### Proof.

Choosing the sequence $\\{A_{n}\\}_{n=1}^{\infty}$ such that

(5) $A_{n}\uparrow\infty,\qquad\frac{\lambda_{n}A_{n}}{n}\downarrow
0,\qquad\sum\limits_{n=1}^{\infty}\frac{\lambda_{n}\log^{d-2}nA_{n}^{d}}{n^{2}}<\infty,$

we set

(6) $\gamma_{n}=\frac{n}{A_{n}},\qquad n=1,2,\ldots$

We prove that there is a constant $C>0$ such that

(7)
$\sum_{i_{1},\ldots,i_{p}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{p}}^{p},x^{\widetilde{\alpha}}\right)\right|}{\gamma_{i_{1}}\cdots\gamma_{i_{p}}}<C\cdot
PV_{\Lambda}(f),$

for any $f\in PBV_{\Lambda}$ and $\alpha:=\\{i_{1},...,i_{p}\\}\subset D$,
${\\{I_{i_{j}}^{j}\\}_{i_{j}=1}^{k_{j}}\in\Omega}$.

To prove (7) observe, that

(8)
$\displaystyle\sum_{i_{1},\ldots,\,i_{p}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{p}}^{p},x^{\widetilde{\alpha}}\right)\right|}{\gamma_{i_{1}}\cdots\gamma_{i_{p}}}$
$\displaystyle=\sum_{\sigma}\sum_{i_{\sigma(1)}\leq\cdots\leq
i_{\sigma(p)}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{p}}^{p},x^{\widetilde{\alpha}}\right)\right|}{\gamma_{i_{1}}\cdots\gamma_{i_{p}}}<\infty,$

where the sum is taken over all rearrangements
$\sigma=\\{\sigma(k)\\}_{k=1}^{p}$ of the set $\\{1,2,\ldots,p\\}$.

Denoting $M=PV_{\Lambda}(f)$ and using (6), (5) and (3) we obtain:

$\displaystyle\sum\limits_{i_{1}\leq i_{2}\leq\cdots\leq
i_{p}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{p}}^{p},x^{\widetilde{\alpha}}\right)\right|}{\gamma_{i_{1}}\cdots\gamma_{i_{p}}}$
$\displaystyle=$ $\displaystyle\sum\limits_{i_{1}\leq i_{2}\leq\cdots\leq
i_{p-1}}\frac{A_{i_{1}}\cdots
A_{i_{p-1}}}{{i_{1}}\cdots{i_{p-1}}}\sum\limits_{i_{p}\geq
i_{p-1}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{p}}^{p},x^{\widetilde{\alpha}}\right)\right|}{\lambda_{i_{p}}}\cdot\frac{\lambda_{i_{p}}A_{i_{p}}}{i_{p}}$
$\displaystyle\leq$ $\displaystyle M\sum\limits_{i_{1}\leq i_{2}\leq\cdots\leq
i_{p-1}}\frac{A_{i_{p-1}}^{p}\lambda_{i_{p-1}}}{i_{p-1}^{2}}\cdot\frac{1}{{i_{1}}\cdots
i_{p-2}}$ $\displaystyle=$ $\displaystyle
M\sum\limits_{i_{i_{p}-1}=1}^{\infty}\frac{A_{i_{p-1}}^{p}\lambda_{i_{p-1}}}{i_{p-1}^{2}}\sum\limits_{i_{p-2}=1}^{i_{p-1}}\frac{1}{i_{p-2}}\sum\limits_{i_{p-3}=1}^{i_{p-2}}\frac{1}{i_{p-3}}\cdots\sum\limits_{i_{1}=1}^{i_{2}}\frac{1}{{i_{1}}}$
$\displaystyle\leq$ $\displaystyle
M\sum\limits_{i_{p-1}=1}^{\infty}\frac{A_{i_{p-1}}^{p}\lambda_{i_{p-1}}}{i_{p-1}^{2}}\left(\sum\limits_{i_{=}1}^{i_{p-1}}\frac{1}{i}\right)^{p-2}\leq
C\cdot
M\sum\limits_{n=1}^{\infty}\frac{A_{n}^{p}\lambda_{n}\log^{d-2}n}{n^{2}}<\infty.$

Similarly we can prove that all other summands in the right hind side of (8)
are finite. Theorem 1 is proved. ∎

In view of Theorem A, Theorem 1 implies

######  Corollary 1.

If the sequence $\Lambda=\\{\lambda_{n}\\}_{n=1}^{\infty}$ satisfies (3), then
$PBV_{\Lambda}\subset CV_{H}$.

######  Definition 4.

The partial modulus of variation $v_{i}\left(n,f\right)$, $i=1,\ldots,d$ of a
function $f$ are defined by

$v_{i}\left(n,f\right):=\sup\limits_{x^{\beta}}\sup\limits_{\\{I_{j}\\}\in\Omega_{n}}\sum\limits_{j=1}^{n}\left|f\left(I_{j},x^{\beta}\right)\right|,\quad\beta=D\setminus\\{i\\},\quad
n=1,2,\ldots.$

For functions of one variable the concept of modulus of variation was
introduced by Chanturia [2].

######  Theorem 2.

Let $f$ be defined on $T^{d}$ and

(9)
$\sum\limits_{j=1}^{\infty}\frac{\sqrt[d]{v_{i}\left(2^{j},f\right)}}{2^{j/d}}<\infty,\qquad
i=1,...,d.$

Then there exists a sequence $\Delta=\\{\delta_{n}\\}_{n=1}^{\infty}$ with

$\delta_{n}=o\left(n\right)\quad\mathrm{as}\quad n\to\infty,$

such that $f\in BV_{\Delta}.$

###### Proof.

We use induction on dimension $d$. We have proved in [8], that in the case
$d=2$ the condition (9) implies $f\in BV_{H}$, which combined with Theorem A
proves Theorem 2 for $d=2$.

Supposing Theorem 2 is true if the dimension is less than $d$, we prove it for
the dimension $d>2$.

According to induction hypothesis it is enough to prove that there exists a
sequence $\delta_{n}=o(n)$ such that

$\sup_{\\{I_{i_{j}}^{j}\\}_{i_{j}=1}^{k_{j}}\in\Omega}\
\sum_{i_{1},\ldots,i_{d}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|}{\delta_{i_{1}}\cdots\delta_{i_{d}}}<\infty.$

Let the sequence $\\{B_{2^{j}}\\}_{j=1}^{\infty}$ be chosen so that

$B_{2^{j}}\uparrow\infty,\qquad\sum\limits_{j=1}^{\infty}\frac{B_{2^{j}}\sqrt[d]{v_{i}\left(2^{j},f\right)}}{2^{j/d}}<\infty,\qquad
i=1,...,d.$

Defining

$B_{n}=B_{2^{N}},\quad\mathrm{for}\quad 2^{N}\leq n<2^{N+1},\qquad
N=0,1,.....,$

we set

(10) $\delta_{n}=\frac{n}{B_{n}},\qquad n=1,2\ldots$

Then we can write

$\displaystyle\sum_{i_{1},\ldots,i_{d}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|}{\delta_{i_{1}}\cdots\delta_{i_{d}}}$
$\displaystyle=$ $\displaystyle\sum_{i_{1},\ldots,i_{d}}B_{i_{1}}\cdots
B_{i_{d}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|}{i_{1}\cdots i_{d}}$ $\displaystyle=$
$\displaystyle\sum\limits_{r_{1}=0}^{\infty}\cdots\sum\limits_{r_{d}=0}^{\infty}\sum\limits_{i_{1}=2^{r_{1}}}^{2^{r_{1}+1}-1}\cdots\sum\limits_{i_{d}=2^{r_{d}}}^{2^{r_{d}+1}-1}B_{i_{1}}\cdots
B_{i_{d}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|}{i_{1}\cdots i_{d}}$ $\displaystyle\leq$
$\displaystyle\sum\limits_{r_{1}=0}^{\infty}\cdots\sum\limits_{r_{d}=0}^{\infty}\frac{B_{2^{r_{1}}}}{2^{r_{1}}}\cdots\frac{B_{2^{r_{d}}}}{2^{r_{d}}}\sum\limits_{i_{1}=2^{r_{1}}}^{2^{r_{1}+1}-1}\cdots\sum\limits_{i_{d}=2^{r_{d}}}^{2^{r_{d}+1}-1}\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|.$

It is easy to show that

$\displaystyle\sum\limits_{i_{1}=2^{r_{1}}}^{2^{r_{1}+1}-1}\cdots\sum\limits_{i_{d}=2^{r_{d}}}^{2^{r_{d}+1}-1}\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|$ $\displaystyle\leq$ $\displaystyle
c\left(d\right)\prod\limits_{i\in\beta}2^{r_{i}}\sup\limits_{x^{\beta}}\sup\limits_{\\{I_{i_{k}}^{k}\\}\in\Omega_{2^{r_{k}}}}\sum\limits_{i_{k}=2^{r_{k}}}^{2^{r_{k}+1}-1}\left|f\left(I_{i_{k}}^{k},x^{\beta}\right)\right|,$

where $\beta:=D\setminus\\{k\\}$, $k=1,...,d$.

Consequently,

$\displaystyle\sum\limits_{i_{1}=2^{r_{1}}}^{2^{r_{1}+1}-1}\cdots\sum\limits_{i_{d}=2^{r_{d}}}^{2^{r_{d}+1}-1}\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|$ $\displaystyle=$
$\displaystyle\left[\left(\sum\limits_{i_{1}=2^{r_{1}}}^{2^{r_{1}+1}-1}\cdots\sum\limits_{i_{d}=2^{r_{d}}}^{2^{r_{d}+1}-1}\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|\right)^{1/d}\right]^{d}$ $\displaystyle\leq$
$\displaystyle
c\left(d\right)\prod\limits_{k=1}^{d}2^{r_{k}\left(1-1/d\right)}\left(\sup\limits_{x^{\beta}}\sup\limits_{\\{I_{i_{k}}^{k}\\}\in\Omega_{2^{r_{k}}}}\sum\limits_{i_{k}=2^{r_{k}}}^{2^{r_{k}+1}-1}\left|f\left(I_{i_{k}}^{k},x^{\beta}\right)\right|\right)^{1/d}$
$\displaystyle=$ $\displaystyle
c\left(d\right)\prod\limits_{k=1}^{d}2^{r_{k}\left(1-1/d\right)}\sqrt[d]{v_{k}\left(2^{r_{k}},f\right)}.$

Combining (1) and (1) we obtain

$\displaystyle\sum_{i_{1},\ldots,i_{d}}\frac{\left|f\left(I_{i_{1}}^{1}\times\cdots\times
I_{i_{d}}^{d}\right)\right|}{\delta_{i_{1}}\cdots\delta_{i_{d}}}$
$\displaystyle\leq$ $\displaystyle
c\left(d\right)\sum\limits_{r_{1}=0}^{\infty}\cdots\sum\limits_{r_{d}=0}^{\infty}\frac{B_{2^{r_{1}}}v_{1}\left(2^{r_{1}},f\right)}{2^{r_{1}/d}}\cdots\frac{B_{2^{r_{d}}}v_{d}\left(2^{r_{d}},f\right)}{2^{r_{d}}/d}<\infty.$

Theorem 2 is proved. ∎

##  2\. Convergence of multiple Fourier series

The Fourier series of function $f\in L^{1}\left(T^{d}\right)$ with respect to
the trigonometric system is the series

$S\left[f\right]:=\sum_{n_{1},...,n_{d}=-\infty}^{+\infty}\widehat{f}\left(n_{1},....,n_{d}\right)e^{i\left(n_{1}x+\cdots+n_{d}x_{d}\right)},$

where

$\widehat{f}\left(n_{1},....,n_{d}\right)=\frac{1}{\left(2\pi\right)^{d}}\int_{T^{d}}f(x^{1},...,x^{d})e^{-i\left(n_{1}x^{1}+\cdots+n_{d}x^{d}\right)}dx^{1}\cdots
dx^{d}$

are the Fourier coefficients of $f$. The rectangular partial sums are defined
as follows:

$\displaystyle S_{N_{1},...,N_{d}}\left(f;x^{1},...,x^{d}\right)$
$\displaystyle:=\sum_{n_{1}=-N_{1}}^{N_{1}}\cdots\sum_{n_{d}=-N_{d}}^{N_{d}}\widehat{f}\left(n_{1},....,n_{d}\right)e^{i\left(n_{1}x^{1}+\cdots+n_{d}x^{d}\right)}$
$\displaystyle=\frac{1}{\pi^{d}}\int\limits_{T^{d}}f\left(x_{1},\cdots,x_{d}\right)\prod\limits_{s=1}^{d}D_{N_{s}}\left(x_{s}\right)dx_{1}\cdots
dx_{d},$

where $D_{N}(t)=\frac{sin\left(N+\frac{1}{2}\right)t}{2sin\frac{t}{2}}$ is the
Dirichlet kernel.

In this paper we consider convergence of only rectangular partial sums
(convergence in the sense of Pringsheim) of $d$-dimensional Fourier series.

We denote by $C(T^{d})$ the space of continuous and $2\pi$-periodic with
respect to each variable functions with the norm

$\|f\|_{C}:=\sup_{\left(x^{1},\ldots,\,x^{d}\right)\in
T^{d}}|f(x^{1},\ldots,x^{d})|.$

We say that the point $x:=\left(x^{1},\ldots,x^{d}\right)$ is a regular point
of function $f$ if the following limits exist

$f\left(x^{1}\pm 0,...,x^{d}\pm
0\right):=\lim\limits_{t^{1},\ldots,\,t^{d}\downarrow 0}f\left(x^{1}\pm
t^{1},\ldots,x^{d}\pm t^{d}\right).$

For the regular point $x:=\left(x^{1},\ldots,x^{d}\right)$ we denote

(13) $f^{\ast}\left(x^{1},\ldots,x^{d}\right):=\frac{1}{2^{d}}\sum
f\left(x^{1}\pm 0,\ldots,x^{d}\pm 0\right).$

######  Definition 5.

We say that the class of functions $V\subset L^{1}(T^{d})$ is a class of
convergence on $T^{d}$, if for any function $f\in V$

1) the Fourier series of $f$ converges to $f^{\ast}({x})$ at any regular point
${x}\in T^{d}$,

2) the convergence is uniform on any compact $K\subset T^{d}$, if $f$ is
continuous on the neighborhood of $K$.

The well known Dirichlet-Jordan theorem (see [16]) states that the Fourier
series of a function $f(x),\ x\in T$ of bounded variation converges at every
point $x$ to the value $\left[f\left(x+0\right)+f\left(x-0\right)\right]/2$.
If $f$ is in addition continuous on $T$, the Fourier series converges
uniformly on $T$.

Hardy [9] generalized the Dirichlet-Jordan theorem to the double Fourier
series and proved that $BV$ is a class of convergence on $T^{2}$.

The following theorem was proved by Waterman (for $d=1$) and Sahakian (for
$d=2$).

######  Theorem WS (Waterman [14], Sahakian [13]).

If $d=1$ or $d=2$, then the class $BV_{H}$ is a class of convergence on
$T^{d}$.

In [1] Bakhvalov showed that the class $BV_{H}$ is not a class of convergence
on $T^{d}$, if $d>2$. On the other hand, he proved the following

######  Theorem B (Bakhvalov [1]).

The class $CV_{H}$ is a class of convergence on $T^{d}$ for any $d=1,2,\ldots$

Convergence of spherical and other partial sums of double Fourier series of
functions of bounded $\Lambda$-variation was investigated in deatails by
Dyachenko [3, 4].

The main result of this paper is the following theorem, that we have proved in
[8] for $d=2$.

######  Theorem 3.

Let $\Lambda=\\{\lambda_{n}\\}_{n=1}^{\infty}$ and $d\geq 2$.

a) If

(14) $\sum\limits_{n=1}^{\infty}\frac{\lambda_{n}\log^{d-2}n}{n^{2}}<\infty,$

then $PBV_{\Lambda}$ is a class of convergence on $T^{d}$.

b) If

(15)
$\frac{\lambda_{n}}{n}=O\left(\frac{\lambda_{[n^{\delta}]}}{[n^{\delta}]}\right)$

for some $\delta>1$, and

(16) $\sum\limits_{n=1}^{\infty}\frac{\lambda_{n}\log^{d-2}n}{n^{2}}=\infty,$

then there exists a continuous function $f\in PBV_{\Lambda}$, the Fourier
series of which diverges at $\left(0,\ldots,0\right).$

###### Proof of Theorem 2.

Part a) immediately follows from Corollary 1 and Theorem B.

To prove part b) we denote

$A_{i_{1},\ldots,i_{d}}:=\left[\frac{\pi
i_{1}}{N+1/2},\frac{\pi\left(i_{1}+1\right)}{N+1/2}\right)\times\cdots\times\left[\frac{\pi
i_{d}}{N+1/2},\frac{\pi\left(i_{d}+1\right)}{N+1/2}\right),$
$W:=\left\\{(i_{1},\ldots,i_{d}):i_{d}<i_{s}<i_{d}+m_{i_{d}},\ 1\leq s<d,\
1\leq i_{d}\leq N_{\delta}\right\\},\quad$
$N_{\delta}=\left[\left(\frac{N}{2}\right)^{\frac{1}{\delta}}\right],\qquad
t_{j}:=\left(\sum\limits_{i=1}^{m_{j}}\frac{1}{\lambda_{i}}\right)^{-1},\qquad
m_{j}:=\left[j^{\delta}\right],$

where $[x]$ is the integer part of $x$.

It is not hard to see, that for any sequence $\Lambda=\\{\lambda_{n}\\}$
satisfying (1) the class $C(T^{d})\cap PBV_{\Lambda}$ is a Banach space with
the norm

$\|f\|_{PBV_{\Lambda}}:=\|f\|_{C}+PV_{\Lambda}(f).$

Consider the following function

$f_{N}\left(x_{1},\ldots,x_{d}\right):=\sum\limits_{\left(i_{1},\ldots,\,i_{d}\right)\in
W}t_{i_{d}}1_{A_{i_{1},\ldots,i_{d}}}\left(x_{1},\ldots,x_{d}\right)\prod\limits_{s=1}^{d}\sin\left(N+1/2\right)x_{s},$

where $1_{A}\left(x_{1},\ldots,x_{d}\right)$ is the characteristic function of
the set $A\subset T^{d}$.

Let $\left(i_{1},\ldots,i_{k-1},i_{k+1},\ldots,i_{d}\right)$ be fixed
$(k=1,\ldots,d-1)$. Then it is easy to show that

$V_{\Lambda}^{{k}}\left(f_{N}\right)\leq C\cdot
t_{i_{d}}\left(\sum\limits_{i_{k}=i_{d}+1}^{i_{d}+m_{i_{d}}}\frac{1}{\lambda_{i_{k}-i_{d}}}\right)\leq
C\cdot
t_{i_{d}}\left(\sum\limits_{i_{k}=1}^{m_{i_{d}}}\frac{1}{\lambda_{i_{k}}}\right)\leq
C<\infty.$

If $\left(i_{1},\ldots,i_{d-1}\right)$ is fixed, the condition
$\left(i_{1},\ldots,i_{d}\right)\in W$ implies

$\max\left\\{i_{d}\left(i_{s}\right):1\leq s\leq
d-1\right\\}<i_{d}<\min\left\\{i_{s}:1\leq s\leq d-1\right\\},$

where

$i_{d}\left(i_{s}\right):=\min\left\\{i_{d}:i_{d}+m_{i_{d}}>i_{s}\right\\}.$

Consequently, by the definition of the function $f_{N}$ we obtain that for any
$s=1,...,d-1$

$\displaystyle V_{\Lambda}^{{d}}\left(f_{N}\right)$ $\displaystyle\leq$
$\displaystyle
C\sum\limits_{i_{d}=i_{d}\left(i_{s}\right)+1}^{i_{s}}\frac{t_{i_{d}}}{\lambda_{i_{d}-i_{d}\left(i_{s}\right)}}$
$\displaystyle\leq$ $\displaystyle C\cdot
t_{i_{d}\left(i_{s}\right)}\sum\limits_{i_{d}=i_{d}\left(i_{s}\right)+1}^{i_{s}}\frac{1}{\lambda_{i_{d}-i_{d}\left(i_{s}\right)}}$
$\displaystyle=$ $\displaystyle C\cdot
t_{i_{d}\left(i_{s}\right)}\sum\limits_{i_{d}=1}^{i_{s}-i_{d}\left(i_{s}\right)}\frac{1}{\lambda_{i_{d}}}\leq
C\cdot
t_{i_{d}\left(i_{s}\right)}\sum\limits_{i_{d}=1}^{m_{i_{d}\left(i_{s}\right)}}\frac{1}{\lambda_{i_{d}}}=C<\infty.$

Hence $f_{N}\in PBV_{\Lambda}$ and

(17) $\|f_{N}\|_{PV_{\Lambda}}\leq C,\quad N=1,2,\ldots.$

Observe, that by (15) we have

$\frac{1}{t_{j}}=\sum_{i=1}^{m_{j}}\frac{1}{\lambda_{i}}=\sum_{i=1}^{m_{j}}\frac{1}{i}\cdot\frac{i}{\lambda_{i}}\leq
C\frac{m_{j}}{\lambda_{m_{j}}}\log m_{j}\leq C\frac{j\log j}{\lambda_{j}}.$

Hence

$t_{j}\log j\geq c\frac{\lambda_{j}}{j}.$

Consequently,

$\displaystyle\pi^{d}S_{N,\cdots,N}\left(f_{N};0,\cdots,0\right)$
$\displaystyle=$
$\displaystyle\int\limits_{T^{d}}f_{N}\left(x^{1},\cdots,x^{d}\right)\prod\limits_{s=1}^{d}D_{N}\left(x^{s}\right)dx^{1}\cdots
dx^{d}$ $\displaystyle=$
$\displaystyle\sum\limits_{\left(i_{1},\cdots,i_{d}\right)\in
W}t_{i_{d}}\int\limits_{A_{i_{1},\cdots,\,i_{d}}}\prod\limits_{s=1}^{d}\frac{\sin^{2}\left(N+1/2\right)x^{s}}{2\sin\left(x^{s}/2\right)}dx^{1}\cdots
dx^{d}$ $\displaystyle\geq$ $\displaystyle
c\sum\limits_{\left(i_{1},\cdots,\,i_{d}\right)\in
W}t_{i_{d}}\frac{1}{i_{1}\cdots i_{d}}$ $\displaystyle\geq$ $\displaystyle
c\sum\limits_{i_{d}=1}^{N_{\delta}}\frac{t_{i_{d}}}{i_{d}}\sum\limits_{i_{1}=i_{d}}^{i_{d}+m_{i_{d}}}\cdots\sum\limits_{i_{d-1}=i_{d}}^{i_{d}+m_{i_{d}}}\frac{1}{i_{1}\cdots
i_{d-1}}$ $\displaystyle\geq$ $\displaystyle
c\sum\limits_{i_{d}=1}^{N_{\delta}}\frac{t_{i_{d}}}{i_{d}}\log^{d-1}\left(\frac{i_{d}+m_{i_{d}}}{i_{d}}\right)$
$\displaystyle\geq$ $\displaystyle
c(\delta-1)^{d-1}\sum\limits_{i_{d}=1}^{N_{\delta}}\frac{t_{i_{d}}\log
i_{d}}{i_{d}}\log^{d-2}i_{d}$ $\displaystyle\geq$ $\displaystyle
c(\delta-1)^{d-1}\sum\limits_{n=1}^{N_{\delta}}\frac{\lambda_{n}\log^{d-2}n}{n^{2}}\rightarrow\infty,$

as $N\rightarrow\infty$, according to (16).

By Banach-Steinhaus Theorem, (17) and (2) imply the existence of a continuous
function $f\in PBV_{\Lambda}$ such that

$\sup_{N}|S_{N,\cdots,N}[f,(0,\cdots,0)]|=\infty.$

∎

######  Corollary 2.

a) If $\Lambda=\left\\{\lambda_{n}\right\\}_{n=1}^{\infty}$ with

$\lambda_{n}=\frac{n}{\log^{d-1+\varepsilon}n},\qquad n=1,2,\ldots$

for some $\varepsilon>0$, then the class $PBV_{\Lambda}$ is a class of
convergence on $T^{d}$.

b) If $\Lambda=\left\\{\lambda_{n}\right\\}_{n=1}^{\infty}$ with

$\lambda_{n}=\frac{n}{\log^{d-1}n},\qquad n=1,2,\ldots,$

then the class $PBV_{\Lambda}$ is not a class of convergence on $T^{d}$.

The second part of Theorem 2 and Corollary 1 imply

######  Corollary 3.

If the sequence $\Lambda=\\{\lambda_{n}\\}_{n=1}^{\infty}$ satisfies (15) and
(16), then $PBV_{\Lambda}\not\subset CV_{H}$.

Theorem 2 and Theorems A and B imply

######  Theorem 4.

The set of functions

$\left\\{f:\sum\limits_{j=0}^{\infty}\frac{\sqrt[d]{v_{i}\left(2^{j},f\right)}}{2^{j/d}}<\infty,\
i=1,...,d\right\\}$

is a class of convergence on $T^{d}$.

######  Corollary 4.

The set of functions

$\left\\{f:v_{i}\left(n,f\right)=O\left(n^{\alpha}\right),\
i=1,...,d\right\\}$

is a class of convergence on $T^{d}$ for any $\alpha\in(0,1)$.

## References

  * [1] Bakhvalov, A. N. Continuity in $\Lambda$-variation of functions of several variables and the convergence of multiple Fourier series (Russian). Mat. Sb. 193, 12(2002), 3–20; English transl. in Sb. Math. 193, 11-12(2002), no. 11-12, 1731–1748.
  * [2] Chanturia, Z. A. The modulus of variation of a function and its application in the theory of Fourier series, Soviet. Math. Dokl. 15 (1974), 67-71.
  * [3] Dyachenko M. I. Waterman classes and spherical partial sums of double Fourier series, Anal. Math. 21(1995), 3-21
  * [4] Dyachenko M. I. Two-dimensional Waterman classes and $u$-convergence of Fourier series (Russian).Mat. Sb. 190 (1999), no.7, 23–40; English transl. in Sb. Math. 190 (1999), no.7-8, 955–972.
  * [5] Dragoshanskiĭ, O. S. Continuity in $\Lambda$-variation of functions of several variables. (Russian) Mat. Sb. 194 (2003), no.7, 57–82; English transl. in Sb. Math. 194 (2003), no.7-8, 1009–1034
  * [6] Goginava U. On the uniform convergence of multiple trigonometric Fourier series. East J. Approx. 3 (1999), no.5, 253-266.
  * [7] Goginava U. Uniform convergence of Cesàro means of negative order of double Walsh-Fourier series. J. Approx. Theory 124 (2003), no. 1, 96–108.
  * [8] Goginava U, Sahakian, A. On the convergence of double Fourier series of functions of bounded partial generalized variation. East J. Approx. 16 (2010), no.2, 109-121.
  * [9] Hardy G. H. On double Fourier series and especially which represent the double zeta function with real and incommensurable parameters. Quart. J. Math. Oxford Ser. 37 (1906), 53-79.
  * [10] Jordan C. Sur la series de Fourier. C.R. Acad. Sci. Paris. 92(1881), 228-230.
  * [11] Marcinkiewicz J. On a class of functions and their Fourier series. Compt. Rend. Soc. Sci. Warsowie, 26 (1934), 71-77.
  * [12] Sablin A. I. $\Lambda$-variation and Fourier series (Russian), Izv. Vyssh. Uchebn. Zaved. Mat. 10 (1987), 66–68; English transl. in  Soviet Math. (Izv. VUZ) 31 (1987).
  * [13] Sahakian A. A. On the convergence of double Fourier series of functions of bounded harmonic variation (Russian).  Izv. Akad. Nauk Armyan. SSR Ser. Mat. 21 (1986), no.6, 517-529; English transl. in,  Soviet J. Contemp. Math. Anal. 21 (1986), no.6, 1-13.
  * [14] Waterman D. On convergence of Fourier series of functions of generalized bounded variation. Studia Math., 44 (1972), no.1, 107-117.
  * [15] Wiener N. The quadratic variation of a function and its Fourier coefficients. Massachusetts J. Math., 3 (1924), 72-94.
  * [16] Zygmund A. Trigonometric series. Cambridge University Press, Cambridge, 1959.


# Left-continuous random walk on $\IZ$ and the parity of its hitting times

Timo Vilkas
Lunds Universitet

###### Abstract

When it comes to random walk on the integers $\IZ$, the arguably first step of
generalization beyond simple random walk is the class of one-sidedly
continuous random walk, where the stepsize in only one direction is bounded by
1. Moreover, the time until state 0 is hit by left-continuous random walk on
$\IZ$ has a direct connection to the total progeny in branching processes. In
this article, the probability of left-continuous random walk to be negative at
an even (resp. odd) time is derived and used to determine the probability of
nearly left-continuous random walk to eventually become negative.

Keywords: Left-continuous random walk on $\IZ$, positive drift, skip-free to
the left, hitting time, parity, separable distribution, branching process.

##  1 Introduction

In 1874, Francis Galton and Henry William Watson published a paper titled “On
the probability of the extinction of families”, laying the foundation of what
is nowadays textbook material of basic courses in probability. Independently
also Irénée-Jules Bienaymé derived and analyzed the following branching
process: Consider a collection $(\xi_{i,j})_{i,j\in\mathbb{N}_{0}}$ of
independent copies of $\xi$, a non-negative, integer-valued random variable.
The process starts with one progenitor who gives rise to $\xi_{0,1}$ children.
Each individual in this first generation then independently gives rise to
$\xi_{1,j}$ individuals, $1\leq j\leq\xi_{0,1}$. This branching continues in
all subsequent generations in the same manner.

The original question (Galton and Watson were concerned with the extinction of
family names) addresses the probability of this branching process to die out,
i.e. to determine $\rho=\mathbb{P}(Z_{i}=0\text{ for some }i\in\mathbb{N})$
where $Z_{i}$ defined via

$Z_{0}=1\quad\text{and}\quad Z_{i}=\sum_{j=1}^{Z_{i-1}}\xi_{i,j}\quad\text{for
}i\in\mathbb{N}$

denotes the number of individuals in the $i$th generation. The fundamental
_extinction criterion_ (cf. Chapter 1 in [1] for instance) states that for a
non-deterministic distribution $\xi$, it holds $\rho<1$ iff
$\mathbb{E}\,\xi>1$. Another way to keep an account of the total progeny is to
explore the family tree individual by individual and count the unexplored
offspring, i.e. adding $\xi_{i,j}-1$ to the current count when individual $j$
in generation $i$ is processed. Given the properties of $\xi$ this random walk
on the integers is what is commonly referred to as left-continuous.

######  Definition 1.

Let $(S_{n})_{n\in\mathbb{N}_{0}}$ be a random walk on the integers. If its
i.i.d. increments $X_{n}=S_{n}-S_{n-1}$ are bounded from below by $-1$, i.e.
$\mathbb{P}(X_{n}\geq-1)=1$, the walk is called left-continuous or skip-free
to the left. Let us write $(p_{k})_{k\geq-1}$ for the probability mass
function and

$g(x)=\sum_{k=-1}^{\infty}p_{k}\,x^{k}=\frac{p_{-1}}{x}+p_{0}+p_{1}\,x+p_{2}\,x^{2}+\dots$

for the probability generating function of the corresponding increment
distribution.

Note that $g$ is not defined in $x=0$ in case $p_{-1}>0$ and that the above
sum converges (absolutely) on $[-1,0)\cup(0,1]$ irrespectively of
$(p_{k})_{k\geq-1}$.

The connection between skip-free random walk and the progeny in the Galton-
Watson-Bienaymé branching process was established in the 1960s, cf. [3], and
one of the reasons why the former received attention. Using this connection,
we can rewrite the extinction probability as

$\rho=\mathbb{P}(S_{n}=0\text{ for some
}n\in\mathbb{N}\,|\,S_{n}=1)=\mathbb{P}(S_{n}=-1\text{ for some
}n\in\mathbb{N}\,|\,S_{n}=0),$

where $(S_{n})_{n\in\mathbb{N}_{0}}$ is the left-continuous walk on $\IZ$ with
increments distributed as $\xi-1$. According to the extinction criterion,
$\rho$ is less than 1 iff $\mathbb{E}\,(\xi-1)>0$, ignoring the trivial case
$\xi\equiv 1$. This corresponds to the random walk having a positive drift.

In a different context, $S_{n}$ can be seen to describe the credit of a
gambler after round $n$ in a game, where each round one token is at stake and
the yield distributed as $\xi$. $\rho$ can then be interpreted as _ruin
probability_.

Left-continuous random walk is a prominent example in standard references on
the matter (e.g. [9]) as it maintains a substantial part of the tractability
of simple random walk without being quite that simplistic. While [8] settles
the question to what extent knowing $\mathbb{P}(S_{n}=0)$ for all
$n\in\mathbb{N}$ determines the increment distribution of left-continuous
random walk on $\IZ$, [7] focusses on the limiting behavior of the walk on
$\mathbb{N}_{0}$ where state 0 is chosen to be absorbing. With simple
martingale methods, the probability of left-continuous random walk to visit a
given level below the starting state can be calculated (cf. Thm. 5.16 in [4]).
We chose to include a different approach, see Lemma 3.1 below. The hitting
time theorem for left-continuous random walk, which states that given
$\\{S_{n}=0\\}$ the probability that $n$ is the first time the walk started at
$k$ visits $0$ equals $\frac{k}{n}$, irrespectively of the increment
distribution, was reproved in [6] using basic yet elaborate combinatorial
arguments. In the article by Brown, Peköz and Ross [2] mean and variance of
the minimum of left-continuous random walk on $\IZ$ are derived using the fact
that the walk with positive drift conditioned to return to state $0$ (or
below) behaves like an unconditioned walk with a different increment
distribution, as widely known and used for simple random walk.

This paper is concerned with the two events of left-continuous random walk on
$\IZ$ to eventually be negative at an _even_ resp.  _odd_ time and with
deriving their probabilities. In the short next section, we warm up by proving
that random walk with positive drift stays non-negative with positive
probability. Section 3 contains the definition of all relevant hitting times
and related probabilities as well as useful relations between the latter and
the probability generating function of the increment distribution. In the last
section, the central Theorem 4.1 as well as some more or less immediate
corollaries are proved. Finally, these results about parity of hitting times
for left-continuous random walk on $\IZ$ are used to determine the probability
to become negative even for random walk that is not quite left-continuous, cf.
Corollary 4.4.

##  2 Random walk with positive drift

Let us start with a short proof of the well-known fact that random walk on
$\IZ$ with positive drift has a positive probability to never hit
$\IZ\setminus\mathbb{N}_{0}=\\{\dots,-2,-1\\}$, if started at $0$.

######  Lemma 2.1.

Let $(X_{n})_{n\in\mathbb{N}}$ be an i.i.d. sequence with
$\mathbb{E}\,(X_{1})>0$. Then the infimum of the random walk
$(S_{n})_{n\in\mathbb{N}_{0}}$, defined by $S_{0}=0,\ S_{n+1}=S_{n}+X_{n+1}$,
is attained at $S_{0}=0$ with positive probability.

###### Proof.

By the law of large numbers it holds almost surely that

$\lim_{n\to\infty}\frac{S_{n}}{n}=\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}X_{k}=\mathbb{E}(X_{1})>0.$

Hence, there exists $n_{0}\in\mathbb{N}$ such that $\mathbb{P}\big{(}S_{n}\geq
1\ \text{ for all }n\geq n_{0}\big{)}>0$. Since $n_{0}$ is finite, there must
be some $0\leq n_{1}<n_{0}$ such that

$\mathbb{P}\Big{(}S_{n_{1}}=\min\big{\\{}S_{n},\;n\in\mathbb{N}_{0}\big{\\}}\Big{)}>0.$

As a consequence, the event $\\{\sum_{k=n_{1}+1}^{n}X_{k}\geq 0$ for all
$n>n_{1}\\}$ must have strictly positive probability. Due to the fact that
$(X_{n})_{n>n_{1}}$ and $(X_{n})_{n\in\mathbb{N}}$ have the same distribution,
the claim follows.

Note that the same proof in fact also works for more general walks on
$\mathbb{R}$ with positive drift, which is why the restriction of $X_{1}$ to
be integer-valued was omitted in the statement of the lemma. For the remainder
of the paper, we will however only be concerned with random walks on the
integers, i.e. increment distributions with $\mathbb{P}(X_{1}\in\IZ)=1$.

##  3 Hitting times and their parity

In this section, we want to determine the probabilities of different hitting
times to be finite (and odd) for a left-continuous random walk
$(S_{n})_{n\in\mathbb{N}_{0}}$, defined by $S_{0}=0,\ S_{n+1}=S_{n}+X_{n+1}$.
To make things non-trivial, we consider walks with positive drift that are not
monotone, i.e. $\mathbb{E}\,(X_{1})>0$ and $p_{-1}>0$. To this end, let

$\displaystyle T_{-1}$ $\displaystyle=\inf\\{n,\;S_{n}=-1\\}\quad\text{and}$
$\displaystyle T_{0}^{+}$ $\displaystyle=\inf\\{n>0,\;S_{n}=0\\}$

denote the hitting time of state $-1$ and the return time to state $0$
respectively. Further we define the following probabilities:

$\displaystyle\begin{aligned} \rho&=\mathbb{P}(T_{-1}<\infty)\\\
\rho_{\mathrm{odd}}&=\mathbb{P}(T_{-1}\text{ is odd}\,|\,T_{-1}<\infty)\\\
\sigma&=\mathbb{P}(S_{n}>0\text{ for all }n\in\mathbb{N})\\\
\tau&=\mathbb{P}(T_{0}^{+}<\infty,\ T_{0}^{+}<T_{-1})\\\
\tau_{\mathrm{odd}}&=\mathbb{P}(T_{0}^{+}\text{ is
odd}\,|\,T_{0}^{+}<\infty,\,T_{0}^{+}<T_{-1}).\end{aligned}$ (1)

In words, $\rho$ denotes the probability, that state $-1$ will be visited,
$\rho_{\mathrm{odd}}$ the conditional probability that given the walk reaches
state $-1$, it will do so for the first time after an odd number of steps;
$\sigma$ is the probability that the walk stays strictly positive after its
start in state $0$, and $\tau$ is the probability that $0$ is revisited,
before $-1$ is visited in case the latter happens. Finally,
$\tau_{\mathrm{odd}}$ is the conditional probability that, given a return to
$0$ before visiting $-1$, this positive excursion will take an odd number of
steps. For ease of notation we write $\tau=\mathbb{P}(T_{0}^{+}<T_{-1})$ etc.
as the strict inequality forces $T_{0}^{+}$ to be finite.

For left-continuous walks, one can easily derive an equation for the
probability $\rho$ that the walk visits $-1$ after start at $0$, cf. Lemma 2
in [2]:

######  Lemma 3.1.

Let $(S_{n})_{n\in\mathbb{N}_{0}}$ be a left-continuous, non-monotonic random
walk with positive drift, i.e. $\mathbb{P}(X_{1}\geq-1)=1>\mathbb{P}(X_{1}\geq
0)$ and $\mathbb{E}\,(X_{1})>0$. Then the probability $\rho$, that state $-1$
is visited after start at $0$, is given by the unique solution to $g(x)=1$ in
the open interval $(0,1)$.

###### Proof.

By the definition of $\rho$ and the strong Markov property it immediately
follows that $\mathbb{P}(T_{-1}<\infty\,|\,S_{0}=k)=\rho^{k+1}$, for all
$k\in\mathbb{N}_{0}$. Consequently, conditioning on the first step gives

$\rho=\sum_{k=-1}^{\infty}p_{k}\,\rho^{k+1}=\rho\cdot g(\rho).$ (2)

Lemma 2.1 (together with $\rho\geq p_{-1}>0)$ implies $0<\rho<1$ and the claim
follows from the strict convexity of $g$ on $(0,1)$ and $g(1)=1$.

Observe that in the setting of the above lemma, from (2) one can in fact
deduce $\rho>p_{-1}$, as $p_{k}>0$ for some $k>0$ since
$0<\mathbb{E}\,(X_{1})<\sum_{k>0}p_{k}\cdot k$. Next, we want to address the
parity of the hitting times $T_{-1}$ and $T_{0}^{+}$.

######  Lemma 3.2.

Let $(S_{n})_{n\in\mathbb{N}_{0}}$ be a left-continuous, non-monotonic random
walk with positive drift, started in $S_{0}=0$. Then the following hold:

  1. (a)

$p_{-1}+\tau+\sigma=1$

  2. (b)

$\sigma=p_{-1}\cdot\frac{1-\rho}{\rho}$ and $\tau=1-\frac{p_{-1}}{\rho}$

###### Proof.

Part (a) follows immediately from left-continuity of the walk, by case
differentiation whether the first step is down or state $0$ revisited if it is
not. As to part (b), conditioning on the first step and using translation
invariance of the walk in the form
$\mathbb{P}(T_{0}^{+}<\infty\,|\,S_{0}=k)=\mathbb{P}(T_{-1}<\infty\,|\,S_{0}=k-1)=\rho^{k}$,
for all $k>0$, gives:

$\sigma=\sum_{k=1}^{\infty}p_{k}\,\big{(}1-\rho^{k}\big{)}=\sum_{k=0}^{\infty}p_{k}\,\big{(}1-\rho^{k}\big{)}=\big{(}1-p_{-1}\big{)}-\Big{(}g(\rho)-\tfrac{p_{-1}}{\rho}\Big{)},$

from which the first claim follows (using $g(\rho)=1$, see Lemma 3.1 above).
The second one is now either a simple consequence of part (a) or derived in
the same vein:

$\tau=\sum_{k=0}^{\infty}p_{k}\,\rho^{k}=g(\rho)-\tfrac{p_{-1}}{\rho}=1-\tfrac{p_{-1}}{\rho}.$

######  Theorem 3.3.

Let $(S_{n})_{n\in\mathbb{N}_{0}}$ be a left-continuous, non-monotonic random
walk with positive drift, started in $S_{0}=0$ and
$\rho_{\mathrm{odd}},\tau_{\mathrm{odd}}$ be the corresponding conditional
probabilities defined in (1). Then the following relations hold:

  1. (a)

$\rho_{\mathrm{odd}}>\frac{1}{2}$ and
$g\big{(}\rho\,(1-2\rho_{\mathrm{odd}})\big{)}=-1$

  2. (b)

$\tau_{\mathrm{odd}}=\frac{p_{-1}\,(1-\rho_{\mathrm{odd}})}{\rho\tau\,(2\rho_{\mathrm{odd}}-1)}$

###### Proof.

To prove the first part, let us begin with the elementary calculation of the
probability that a binomial variable takes on an even value: Let
$Y\sim\mathrm{Bin}(n,p)$, then

$\displaystyle\mathbb{P}(Y\text{ is even})$
$\displaystyle=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}p^{2k}\,(1-p)^{n-2k}$
$\displaystyle=\frac{1}{2}\Bigg{(}\sum_{k=0}^{n}\binom{n}{k}p^{k}\,(1-p)^{n-k}+\sum_{k=0}^{n}\binom{n}{k}(-p)^{k}\,(1-p)^{n-k}\Bigg{)}$
$\displaystyle=\tfrac{1}{2}\,\big{(}1+(1-2p)^{n}\big{)}.$

Assume for now that the random walk starts in $S_{0}=k\geq 0$ and let
$T_{-1}(k)$ stand for $T_{-1}\,|\,S_{0}=k$. Due to its left-continuity, the
time until state $-1$ is visited can then be written as sum of the (possibly
infinite) times

$T_{i\to i-1}=\inf\\{n>0,\;S_{n}=i-1\\}-\inf\\{n>0,\;S_{n}=i\\},\quad\text{for
}0\leq i\leq k,$

it takes to reach level $i-1$ after the first time level $i$ was visited, i.e.

$T_{-1}(k)=\sum_{i=0}^{k}T_{i\to
i-1}\quad\text{and}\quad\big{\\{}T_{-1}(k)<\infty\big{\\}}=\bigcap_{i=0}^{k}\\{T_{i\to
i-1}<\infty\\},$

see Figure 1 for an illustration. By the strong Markov property and
translation invariance of the walk, the random variables $T_{k\to
k-1},\dots,T_{0\to-1}$ are independent and distributed as $T_{-1}(0)$, the
time to hit state $-1$ after a start in $S_{0}=0$.

Figure 1: Starting in $S_{0}=k\geq 0$, the total time $T_{-1}(k)$ until state
$-1$ is hit is the sum of $k+1$ independent copies of $T_{-1}(0)$.

Due to product structure of the set $\\{T_{-1}(k)<\infty\\}$ it further holds
that $T_{-1}(k)$ conditioned to be finite is distributed as the sum of $k+1$
i.i.d. copies of $T_{-1}(0)$ conditioned to be finite. At this point, it is
crucial to observe that $T_{-1}(k)$ is even, if and only if an even number of
these $k+1$ copies are odd, and that given $\\{T_{-1}(k)<\infty\\}$ this
number is binomially distributed with parameters $k+1$ and
$\rho_{\mathrm{odd}}$ by (conditional) independence.

Returning to the walk starting in $S_{0}=0$, we can condition on the first
step once again. In doing so, two things are important to note: On the one
hand, given $X_{1}=k\geq 0$, the subsequent walk behaves like one started in
$S_{0}=k$, besides the fact that this first step flips the parity of $T_{-1}$.
On the other hand, conditioning on $\\{T_{-1}<\infty\\}$ also changes the
distribution of the first increment $X_{1}$. Applying Bayes’ theorem, we find
for all $k\geq-1$:

$\mathbb{P}(X_{1}=k\,|\,T_{-1}<\infty)=\frac{\mathbb{P}(X_{1}=k)}{\mathbb{P}(T_{-1}<\infty)}\cdot\mathbb{P}(T_{-1}<\infty\,|\,X_{1}=k)=\frac{p_{k}}{\rho}\rho^{k+1}=p_{k}\,\rho^{k}.$

With the above reasoning, we established the following recursion for
$\rho_{\mathrm{odd}}$:

$\displaystyle\rho_{\mathrm{odd}}$
$\displaystyle=\sum_{k=-1}^{\infty}\mathbb{P}(X_{1}=k\,|\,T_{-1}<\infty)\cdot\mathbb{P}(T_{-1}\text{
is even}\,|\,S_{0}=k,\ T_{-1}<\infty)$
$\displaystyle=\sum_{k=-1}^{\infty}p_{k}\,\rho^{k}\cdot\frac{1}{2}\,\Big{(}1+(1-2\rho_{\mathrm{odd}})^{k+1}\Big{)}$
$\displaystyle=\frac{1}{2}\Big{(}g(\rho)+(1-2\rho_{\mathrm{odd}})\cdot
g\big{(}\rho\,(1-2\rho_{\mathrm{odd}})\big{)}\Big{)}.$

Here we tacitly used the fact that $\rho\,(1-2\rho_{\mathrm{odd}})\neq 0$,
i.e. that $g$ is defined for this argument. Assuming
$\rho_{\mathrm{odd}}\leq\frac{1}{2}$ in the second equation, however, would
lead to

$\rho_{\mathrm{odd}}\geq\frac{p_{-1}}{\rho}+\sum_{k=0}^{\infty}p_{k}\,\rho^{k}\cdot\frac{1}{2}\,(1+0)=\frac{p_{-1}}{2\rho}+\frac{g(\rho)}{2}>\frac{1}{2},$

i.e. a contradiction. With help of a small algebraic manipulation (using
$g(\rho)=1$ and $(1-2\rho_{\mathrm{odd}})\neq 0$) we finally arrive at
$1+g\big{(}\rho\,(1-2\rho_{\mathrm{odd}})\big{)}=0$.

Very much like for $\rho_{\mathrm{odd}}$ we can calculate
$\tau_{\mathrm{odd}}$ by conditioning on the first step, however, this time
with $\mathbb{P}(X_{1}=-1\,|\,T_{0}^{+}<T_{-1})=0$ and

$\mathbb{P}(X_{1}=k\,|\,T_{0}^{+}<T_{-1})=\mathbb{P}(T_{0}^{+}<\infty\,|\,X_{1}=k)\cdot\frac{\mathbb{P}(X_{1}=k)}{\mathbb{P}(T_{0}^{+}<T_{-1})}\\\
=\rho^{k}\cdot\frac{p_{k}}{\tau},$

for all $k\geq 0$. The first equation here follows (besides using Bayes) from
the fact that for $k\geq 0$ it holds $\\{X_{1}=k,\
T_{0}^{+}<T_{-1}\\}=\\{X_{1}=k,\ T_{0}^{+}<\infty\\}$, by left-continuity of
the walk.

Using translation invariance of the walk, we arrive at

$\displaystyle\tau_{\mathrm{odd}}$ $\displaystyle=\mathbb{P}(T_{0}^{+}\text{
is odd}\,|\,T_{0}^{+}<T_{-1})$
$\displaystyle=\sum_{k=0}^{\infty}\mathbb{P}(X_{1}=k\,|\,T_{0}^{+}<T_{-1})\cdot\mathbb{P}(T_{0}^{+}\text{
is odd}\,|\,T_{0}^{+}<\infty,\,X_{1}=k)$
$\displaystyle=\sum_{k=0}^{\infty}\rho^{k}\cdot\frac{p_{k}}{\tau}\cdot\mathbb{P}(T_{-1}\text{
is even}\,|\,T_{-1}<\infty,\,S_{0}=k-1)$
$\displaystyle=\sum_{k=0}^{\infty}\rho^{k}\cdot\frac{p_{k}}{\tau}\cdot\frac{1}{2}\,\Big{(}1+(1-2\rho_{\mathrm{odd}})^{k}\Big{)}$
$\displaystyle=\frac{1}{2\tau}\Bigg{(}g(\rho)-\frac{p_{-1}}{\rho}+g\Big{(}\rho\,(1-2\rho_{\mathrm{odd}})\Big{)}-\frac{p_{-1}}{\rho\,(1-2\rho_{\mathrm{odd}})}\Bigg{)}$
$\displaystyle=\frac{p_{-1}\,(1-\rho_{\mathrm{odd}})}{\rho\tau\,(2\rho_{\mathrm{odd}}-1)}.$

Note that $\rho\in(p_{-1},1)$, thus $\tau>0$, and
$\rho_{\mathrm{odd}}>\frac{1}{2}$, which gives
$\rho\tau\,(2\rho_{\mathrm{odd}}-1)>0$. Besides that, both $g(\rho)=1$ and
part (a) were used in the last step.

######  Example.

Consider increments of the form $X_{n}=Y_{n}-1$, where
$(Y_{n})_{n\in\mathbb{N}}$ is an i.i.d. sequence of random variables that are
Poisson distributed with parameter $\lambda>1$, i.e.

$p_{k}:=\mathbb{P}(X_{1}=k)=\mathrm{e}^{-\lambda}\frac{\lambda^{k+1}}{(k+1)!},\text{
for all }k\geq-1.$

Then $p_{-1}=\mathrm{e}^{-\lambda}$ and
$g(x)=\frac{1}{x}\,\mathrm{e}^{\lambda(x-1)}$.

Choosing a numerical value for the parameter $\lambda$ one can calculate the
relevant (conditional) probabilities using Lemma 3.2 and Theorem 3.3. With
$\lambda=\frac{3}{2}$ for instance, the corresponding computations give
(approximately): $\rho=0.417188$, $\sigma=0.311713,$ $\tau=0.465157$ as well
as $\rho_{\mathrm{odd}}=0.706513$ and $\tau_{\mathrm{odd}}=0.817032.$

##  4 Using parity to deal with nearly left-continuous walks on $\IZ$ with
separable increments

Given $(S_{n})_{n\in\mathbb{N}_{0}}$ as above, we can use Lemma 3.2 and
Theorem 3.3 to define and analyze an auxiliary Markov chain, designed to
determine the probability of the event $E=\\{S_{2n}<0\textup{ for some
}n\in\mathbb{N}\\}$, i.e. that the walk is negative at an even time.

######  Theorem 4.1.

Let $(S_{n})_{n\in\mathbb{N}_{0}}$ be a left-continuous, non-monotonic random
walk on $\IZ$ with positive drift and $\sigma$, $\rho$ and $\tau$ as well as
$\rho_{\mathrm{odd}}$ and $\tau_{\mathrm{odd}}$ be the corresponding
(conditional) probabilities defined in (1). Then it holds

$\mathbb{P}(E\,|\,S_{0}=0)=\rho\,\bigg{(}1-\frac{\sigma\cdot\rho_{\mathrm{odd}}}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}\bigg{)}.$
(3)

###### Proof.

As already mentioned, to calculate the probability of the event $E$, that
$(S_{n})_{n\in\mathbb{N}_{0}}$ visits
$\IZ\setminus\mathbb{N}_{0}=\\{\dots,-2,-1\\}$ at an even time, the results
from Section 3 come in useful. Let us define a Markov chain, by disecting the
trajectory of $(S_{n})_{n\in\mathbb{N}_{0}}$ into the starting point $S_{0}=0$
and segments leading to visits in $\IZ\setminus\mathbb{N}_{0}$, keeping track
of the parity of time. The states “no further visit to $-1$” and “$S_{n}<0$
for $n$ even” are considered to be absorbing. However, the state “$S_{n}=-1$
for $n$ odd” is transient, as it does not give an answer to the question
whether $E$ eventually occurs or not. Representing the relevant segments by
nodes as depicted below in Figure 2, we get a finite absorbing Markov chain
with transition probabilities as shown, cf. (1).

Figure 2: Simple MC tracking the parity of time when
$(\tilde{S}_{n})_{n\in\mathbb{N}_{0}}$ becomes negative.

The event that the smallest $n$ for which $S_{n}=-1$ is (finite and) odd, for
instance, corresponds to $\\{T_{-1}\text{ is odd}\\}$, which has probability
$\rho\cdot\rho_{\mathrm{odd}}$. Given that we are in state $-1$ at an odd
time, the probability that the trajectory takes a positive excursion of even
length (to be in $-1$ again at an odd time next) is $\tau$ (for taking a
positive excursion from $-1$ to $-1$) times $1-\tau_{\mathrm{odd}}$, the
conditional probability that, given the walk returns to $-1$ before visiting
$-2$, this excursion consists of an even number of steps. Note that the Markov
property is inherited from the random walk $(S_{n})_{n\in\mathbb{N}_{0}}$ due
to the fact that the two transient states of the chain correspond to states
(with time stamp) of the walk.

Ordering the states from left to right, we arrive at the following transition
matrix:

$P=\begin{bmatrix}0&\rho\cdot\rho_{\mathrm{odd}}&1-\rho&\rho\,(1-\rho_{\mathrm{odd}})\\\
0&\tau\,(1-\tau_{\mathrm{odd}})&\sigma&p_{-1}+\tau\cdot\tau_{\mathrm{odd}}\\\
0&0&1&0\\\ 0&0&0&1\end{bmatrix}.$

Given that the chain starts in the first state “$S_{0}=0$”, the probability to
get absorbed in the fourth one “$S_{n}\leq-1$ for $n$ even” is given by
element $b_{12}$ of the matrix $B=NR\in\mathbb{R}^{2\times 2}$, where
$N=(\mathbf{I}-Q)^{-1}$ is the so-called fundamental matrix, $\mathbf{I}$
refers to the $2\times 2$ identity matrix and $Q,R$ are the submatrices the
canonical form of $P$ consists of:

$P=\begin{bmatrix}Q&R\\\ \mathbf{0}&\mathbf{I}\\\ \end{bmatrix},\text{ i.e.}\
\ Q=\begin{bmatrix}0&\rho\cdot\rho_{\mathrm{odd}}\\\
0&\tau\cdot(1-\tau_{\mathrm{odd}})\\\ \end{bmatrix},\ \
R=\begin{bmatrix}1-\rho&\rho\cdot(1-\rho_{\mathrm{odd}})\\\
\sigma&p_{-1}+\tau\cdot\tau_{\mathrm{odd}}\\\ \end{bmatrix}.$

The claim (3) now follows by some basic matrix calculations. For details see
Chapter 11.2 in [5].

######  Corollary 4.2.

Letting $O=\\{S_{2n-1}<0\textup{ for some }n\in\mathbb{N}\\}$ denote the event
that the walk $(S_{n})_{n\in\mathbb{N}_{0}}$, defined as above, is negative at
an odd time instead, we can conclude

$\mathbb{P}(O\,|\,S_{0}=0)=\rho\,\bigg{(}1-\frac{\sigma\cdot(1-\rho_{\mathrm{odd}})}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}\bigg{)}.$

and

$\mathbb{P}(E\cap
O\,|\,S_{0}=0)=\rho\,\bigg{(}1-\frac{\sigma}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}\bigg{)}=\rho\,\frac{p_{-1}+\tau\cdot\tau_{\mathrm{odd}}}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}.$

###### Proof.

To determine $\mathbb{P}(O\,|\,S_{0}=0)$ we can adapt the approach above by
essentially letting the states “$S_{n}=-1$ for $n$ odd” and “$S_{n}\leq-1$ for
$n$ even” change their roles, cf. Figure 3.

Figure 3: Slightly altered Markov chain construction

Given the slightly changed transition matrix ($\rho_{\mathrm{odd}}$ and
$1-\rho_{\mathrm{odd}}$ get swapped) and

$Q=\begin{bmatrix}0&\rho\cdot(1-\rho_{\mathrm{odd}})\\\
0&\tau\cdot(1-\tau_{\mathrm{odd}})\\\ \end{bmatrix},\ \
R=\begin{bmatrix}1-\rho&\rho\cdot\rho_{\mathrm{odd}}\\\
\sigma&p_{-1}+\tau\cdot\tau_{\mathrm{odd}}\\\ \end{bmatrix}$

following the above reasoning verbatim, element $b_{12}$ of the matrix
$B=(\mathbf{I}-Q)^{-1}R$ corresponds to the probability we were looking for.
Using

$\displaystyle\rho$
$\displaystyle=\mathbb{P}(T_{-1}<\infty\,|\,S_{0}=0)=\mathbb{P}(E\cup
O\,|\,S_{0}=0)$
$\displaystyle=\mathbb{P}(E\,|\,S_{0}=0)+\mathbb{P}(O\,|\,S_{0}=0)-\mathbb{P}(E\cap
O\,|\,S_{0}=0)$

and Lemma 3.2(a), we arrive at the second claim.

In contrast to the probability of hitting $\IZ\setminus\mathbb{N}_{0}$, i.e.
the event $\\{T_{-1}<\infty\\}$, which simply becomes $\rho^{k+1}$ for a left-
continuous random walk on $\IZ$ started in general $k\in\mathbb{N}_{0}$, the
probability of the event $E=\\{S_{2n}<0\textup{ for some }n\in\mathbb{N}\\}$
given a start at $k>0$ is not just a power of $\mathbb{P}(E\,|\,S_{0}=0)$.
However, the construction above can be used to determine this probability even
for $S_{0}>0$:

######  Corollary 4.3.

For general $k\in\mathbb{N}_{0}$ it holds

$\mathbb{P}(E\,|\,S_{0}=k)=\rho^{k+1}\,\bigg{(}1-\frac{\sigma}{2}\cdot\frac{1-(1-2\rho_{\mathrm{odd}})^{k+1}}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}\bigg{)},$
$\mathbb{P}(O\,|\,S_{0}=k)=\rho^{k+1}\,\bigg{(}1-\frac{\sigma}{2}\cdot\frac{1+(1-2\rho_{\mathrm{odd}})^{k+1}}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}\bigg{)}\quad\text{and}$
$\mathbb{P}(E\cap
O\,|\,S_{0}=k)=\rho^{k+1}\,\bigg{(}1-\frac{\sigma}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}\bigg{)}.$

###### Proof.

Using the same construction as above, we end up with the Markov chain and
corresponding transition probabilities as depicted in Figure 4.

Figure 4: A different starting value $S_{0}$ only changes the transition
probabilities of the Markov chain from this state.

This leads to

$P=\begin{bmatrix}0&\frac{\rho^{k+1}}{2}\big{(}1-(1-2\rho_{\mathrm{odd}})^{k+1}\big{)}&1-\rho^{k+1}&\frac{\rho^{k+1}}{2}\big{(}1+(1-2\rho_{\mathrm{odd}})^{k+1}\big{)}\\\
0&\tau(1-\tau_{\mathrm{odd}})&\sigma&p_{-1}+\tau\cdot\tau_{\mathrm{odd}}\\\
0&0&1&0\\\ 0&0&0&1\end{bmatrix},$

hence

$Q=\begin{bmatrix}0&\rho^{k+1}\,(1-q)\\\ 0&\tau(1-\tau_{\mathrm{odd}})\\\
\end{bmatrix}\quad\text{and}\quad
R=\begin{bmatrix}1-\rho^{k+1}&\rho^{k+1}\,q\\\
\sigma&p_{-1}+\tau\cdot\tau_{\mathrm{odd}}\\\ \end{bmatrix},$

where $q:=\tfrac{1}{2}\,(1+(1-2\rho_{\mathrm{odd}})^{k+1})$ denotes the
probability of a random variable, which is binomially distributed with
parameters $k+1$ and $\rho_{\mathrm{odd}}$, to be even. The second element in
the first row of matrix $B=(\mathbf{I}-Q)^{-1}R$ finally gives the probability
of interest as before.

Changing parities translates to swapping $q$ and $1-q$ in the construction and
calculations above, which gives the second claim. Finally, the probability for
$E\cap O$ follows immediately by the inclusion-exclusion principle.

To extend the analysis of random walk on $\IZ$ to increment distributions
concentrated on $\\{-2,-1\\}\cup\mathbb{N}_{0}$, rather than
$\\{-1\\}\cup\mathbb{N}_{0}$ as for left-continuous walks, we consider the
special case in which the increment distribution arises as the convolution of
two i.i.d. integer-valued random variables:

######  Definition 2.

Let $X$ be an integer-valued random variable. Let its distribution be called
separable, if there exist independent and identically distributed, integer-
valued random variables $Y_{1}$ and $Y_{2}$, such that

$X\stackrel{{\scriptstyle d}}{{=}}Y_{1}+Y_{2}.$

The first observation to make is that the restriction of $Y_{i}$ to be
integer-valued is a non-trivial one. Since the sum $Y_{1}+Y_{2}$ is integer-
valued and the summands i.i.d., there are two possible cases: either
$\mathbb{P}(Y_{i}\in\IZ)=1$ or $\mathbb{P}(Y_{i}\in\IZ+\frac{1}{2})=1$. To
give a concrete example, let $Z\sim\mathrm{Bin}(2,\frac{1}{2})$. Then the
integer-valued random variable $X=Z-1$, with probability mass function
$p_{-1}=p_{1}=\frac{1}{4},\ p_{0}=\frac{1}{2}$ can be written as the sum of
two independent $\mathrm{unif}\\{-\frac{1}{2},\frac{1}{2}\\}$ random variables
but not as the sum of two i.i.d. integer-valued random variables.

Further, it is worth mentioning that this property (besides the restriction to
integer-valued summands) is a lot weaker than the one of being infinitely
divisible as the latter requires a decomposition into not only two, but
arbitrarily many summands, i.e. that for any $n\in\mathbb{N}$ there exist
i.i.d. $Y_{1},\dots,Y_{n}$ such that $X$ has the same distribution as the sum
$Y_{1}+\ldots+Y_{n}$.

######  Corollary 4.4.

For fixed $k\in\mathbb{N}_{0}$, consider the random walk
$(S_{n})_{n\in\mathbb{N}_{0}}$ on $\IZ$, defined by $S_{0}=k,\
S_{n+1}=S_{n}+X_{n+1}$, where $(X_{n})_{n\in\mathbb{N}}$ is an i.i.d. sequence
of integer-valued random variables with $\mathbb{E}\,(X_{1})>0$ and
$\mathbb{P}(X_{1}\geq-2)=1$. If the marginal increment distribution
$\mathcal{L}(X_{1})$ is separable, i.e. there exist i.i.d. random variables
$Y_{1},Y_{2}$ such that

$X_{1}\stackrel{{\scriptstyle d}}{{=}}Y_{1}+Y_{2},$

the probability of the random walk $(S_{n})_{n\in\mathbb{N}_{0}}$ to
eventually become negative is given by

$\mathbb{P}(S_{n}<0\textup{ for some
}n\in\mathbb{N})=\rho^{k+1}\,\bigg{(}1-\frac{\sigma}{2}\cdot\frac{1-(1-2\rho_{\mathrm{odd}})^{k+1}}{1-\tau\cdot(1-\tau_{\mathrm{odd}})}\bigg{)}.$

The (conditional) probabilities $\sigma$, $\rho$ and $\tau$ as well as
$\rho_{\mathrm{odd}}$ and $\tau_{\mathrm{odd}}$ appearing here refer to the
ones introduced in (1) corresponding to the left-continuous random walk on
$\IZ$ starting at $0$ with increments distributed as $Y_{1}$.

###### Proof.

This result readily follows from Corollary 4.3: Define the random walk
$(\tilde{S}_{n})_{n\in\mathbb{N}_{0}}$ by $\tilde{S}_{0}=k$ and
$\tilde{S}_{n}=\tilde{S}_{n-1}+Y_{n}$, $n\in\mathbb{N}$, where
$(Y_{n})_{n\in\mathbb{N}}$ is an i.i.d. sequence of copies of $Y_{1}$. Then
$(\tilde{S}_{n})_{n\in\mathbb{N}_{0}}$ is a left-continuous, non-monotonic
random walk on $\IZ$ with positive drift, to which Corollary 4.3 applies. The
final observation needed to conclude is that
$(\tilde{S}_{2n})_{n\in\mathbb{N}_{0}}\stackrel{{\scriptstyle
d}}{{=}}(S_{n})_{n\in\mathbb{N}_{0}}$.

######  Remark.

In the same way, one could treat a random walk on $\IZ$ with increment
distribution being the convolution of $k\geq 3$ i.i.d.
$\\{-1\\}\cup\mathbb{N}_{0}$-valued random variables by introducing $k-1$
intermediate steps and analyze $(\tilde{S}_{kn})_{n\in\mathbb{N}_{0}}$
instead. Lemma 3.2 and Theorem 3.3 still apply to the skip-free walk
$(\tilde{S}_{n})_{n\in\mathbb{N}_{0}}$, however, the Markov chain and
corresponding matrix calculations used in the proof of Theorem 4.1 would
become a lot harder to handle resp. to perform.

######  Example.

Consider the random walk $(S_{n})_{n\in\mathbb{N}_{0}}$ with increments
$X_{n}=S_{n}-S_{n-1}$, where $(X_{n})_{n\in\mathbb{N}}$ is an i.i.d. sequence
and $X_{n}+2$ Poisson distributed with parameter $\lambda>2$. Then $X_{n}$ can
be written as the sum of two independent $\mathrm{Poi}(\frac{\lambda}{2})$
random variables shifted to the left by 1. The auxiliary random walk (with
intermediate steps) is therefore left-continuous and has increments as in the
example at the end of Section 3. Choosing $\lambda=3$ for instance, we can
therefore conclude by Corollary 4.4 for arbitrary $k\in\mathbb{N}_{0}$:

$\mathbb{P}(S_{n}<0\textup{ for some }n\in\mathbb{N}\,|\,S_{0}=k)\approx
0.417^{k+1}\,\bigg{(}1-\frac{0.156\cdot\big{(}1-(-0.413)^{k+1}\big{)}}{0.915}\bigg{)}.$

Given a start at e.g. $0$ or $2$ this amounts to $\mathbb{P}(S_{n}<0\textup{
for some }n\in\mathbb{N}\,|\,S_{0}=0)\approx 0.317$ and
$\mathbb{P}(S_{n}<0\textup{ for some }n\in\mathbb{N}\,|\,S_{0}=2)\approx
0.059$ respectively.

## References

  * [1] K.B. Athreya and P.E. Ney (1972): “Branching Processes”, Springer Berlin, Heidelberg.
  * [2] M. Brown, E.A. Peköz and S.M. Ross (2010): Some results for skip-free random walk, Probability in the Engineering and Informational Sciences, Vol. 24 (4), pp. 491-507.
  * [3] M. Dwass (1969): The Total Progeny in a Branching Process and a Related Random Walk, Journal of Applied Probability, Vol. 6 (3), pp. 682-686.
  * [4] R. Durrett, “Essentials of Stochastic Processes (2nd edition)”, Springer, 2012.
  * [5] C.M. Grinstead, and J.L. Snell: (2012) “Introduction to Probability (2nd edition)”, American Mathematical Society.
  * [6] R. van der Hofstad and M. Keane (2008): An Elementary Proof of the Hitting Time Theorem, The American Mathematical Monthly, Vol. 115 (8), pp. 753-756.
  * [7] G. Letac, P. Mazet and G. Schiffmann (1976): A Note on Left-Continuous Random Walks, Journal of Applied Probability, Vol. 13 (4), pp. 814-817.
  * [8] A.G. Pakes (1973): Conditional limit theorems for a left-continuous random walk, Journal of Applied Probability, Vol. 10 (1), pp. 39-53.
  * [9] F. Spitzer, “Principles of Random Walk (2nd edition)”, Springer New York, 1964.

Timo Vilkas
Statistiska institutionen,
Ekonomihögskolan vid Lunds universitet,
220 07 Lund, Sweden.
<EMAIL_ADDRESS>