A PROOF OF POLLACZEK-SPITZER IDENTITY

Internat. J. Math. & Math. Sci.

VOL. 13 NO. 4 (1990) 737-740

737

A PROOF OF POLLACZEK-SPITZER IDENTITY

S. PARAMASAMY

Department

of Mathematics TheUniversityofthe

West

Indies

St.

Augustine Trinidad,

W.I.

(Received November 27, 1989 and in revised form July 12, 1990)

ABSTRACT. In

this note we derive a

proof

ofPollaczek-Spitzer identity usinga

generalization

ofTakacs ballottheorem.

KEY WORDS AND PHRASES.

Random

walk,

ballottheorem,

Pollaczek-Spitzer

identity.

1980 AMS SUBJECT CLASSIFICATION CODE.

60J15.

1.

INTRODUCTION.

Consider thefollowing generalizationofTakacs ballot theorem

(Takacs ]): Suppose k,

k.

k,,,

arenon-negative integerswithsumk<mn for someinteger^tnand

letn,

be the number ofcyclic permutations

(kl,k ki,)of (kl, k.z, ...,k,)

such that

kil

⁺

k6

^{+ +}

k

^{jm rfor allj 1,2 n, with}equality holding for at least one of thesej’s,r 1,2 ,m. Then

, rn,-nm-k (1.1)

On

setting

r

^{tn ki,wegetthe}following generalization:

Let r,

r2,...,

r,,

beintegerswithsum s and let

n,

be the numberof cyclic permutationsin whichall thepartial sumsaregreater^or

equal

to r withat leastone sum

equal

tor. Then

rn,-s (1.2)

PROOF

of

(1.1).

Consider n boxes

arranged

in a circle andnumbered 1tonin the clockwise direction. Initially^box contains

k

^balls.

^Starting

^{frombox nsearch}the boxes in the anti-clockwise direction and should a box containtn+ r balls for some r>0,then remove r balls from the boxcontaining thesem+ r ballsand

place

them inthe boxthat follows immediately in theanti-clockwise direction.

Repeat

the above

steps

untilthe numberofballs contained ineachbox isless than or

equal

tom.

Let B

^{be the}

numberof balls contained in box after the re-allocations asspecifiedare

completed

andlet nl be the number of

integers amongB,B2, B,,

whichare

equal

tom i,

0,1

m. Since

E (m i)ni

kand

E n

^n,

wehave

E ini

^{-nm k.}

Letk,/i-kiand So-ki+ki+l+... ^{+ki+j, i,j- 1,2}

^{n. Then}

Bi-m-r

^1rm, ifandonly if

Sii

^{jm r foralljwith at}least one index forwhich

S,

tm r.

To prove

thisassume withoutloss of generalitythat 1.

Suppose B

^{m r, 1 r m,and}

^S,

^{> tm rforsome >2. Thenwe must}

738 S. PARAMASAMY

have

Bt-B,_t B2.m

^and

^Bt>m-r,

^a contradiction.

So So<jm-r

for all j>l.

Suppose S

₀<jm rforallj. Then we must have

kt

^{m and}

ki

^{gm for all}

^2,

^{whichimpliesthat}

Bt

^{<m r,a}

contradiction.

Now (1.1)

follows immediately.

2.

POLLACZEK-SPITZER IDENTITY.

Using (1.2),

^wegivea

proof

ofthe well-known

Pollaczek-Spitzer

identity

(2.1).

^This

proof appears

tobenew.

To

keepthearguments simple,weconsiderinteger-valuedrandom variablesonly.

THEOREM. Let X,

1, 2 beaninfinite

sequence

of independentandidenticallydistributed integer-valued random variables;

S,-X1 +X2

⁺

^+X,; mi.

^and

Mi.,

the minimum and maximum

respectively ofX/,X/+X/+,...,X/+X,./

+

+X/+j;

F,- , exp(-Xs)P{S,-s}/i,

i-1,2

,;

.>0

G,- X exp(-)P{Mt.,-t O,S-s},

1,2,...;

F tF, ^G- , G,

^{0< <1}

-1 -1

Then

F log(1 -G) (2.1)

PROOF. By (1.2),

^wehave

XJ ^{P{ml.. "J} IS. ^-s}

^-s/n

^(2.2)

providedthe conditionalprobabilityexists.

Now

forr<s,

{mx..-rlS..s}.u[{(mt.,-rlS,-s-t)n(s,-s-t)}n{m,/l,.-tls.-$,-t}] ^(2.3)

wherethe union is over all z1andall1 s r. Alsonote the

easily

verifiableduality

property

P{m.. -sis ^{s} P{M.._} OIS ^{s} (2.4)}

Consequently,

using

(2.3)

^and

(2.4),

wehaveforr<s,

P{mL.-s IS. ^-s} -P{ml,,-r IS,-s-t}P{S,-s-t}P{M,/t.._ <OIS.-S,-t} ^(2.5)

So multiplying (2.5) ^by

^{r s}

^1,

adding^thequantity

P {mr,.

^s

S.

^s

}

^{tobothsidesofthe}

^equation,

^and

summing,weget,

by (2.2),

s/n-s

P{M.._t

^gO

IS. ^-s}

⁺

^{(s -t) p{s}

^-s

-t}P{M/t.._t ^O IS ^{-s -t}}

whichimpliesthat

s

P{S. -s}ln

^-s

P{M,._t

^.:0

IS. -s}P{S. -s}

+ (s-t)p{S,’s-t}P{M,/,.. OIS.-S,’t}P{S.-S,’t} ^(2.6)

Then

multiplying (2.6) by exp(-,a)

and

summing

overall sa

1,

we obtain

F,,’- G,,’

+

, Fi’G,, _, ^(2.7)

where

F/-dFdd

^and

G’-dGdd. Multiplying (2.7) ^{by ",}

^0<t<1, and summing overn

1,2

we have

A PROOF OF POLLACZEK-SPITZER IDENTITY 739

So

integrating,wegettheidentity

(2.1). (Let

k ^ootoshowthat thearbitraryconstant is

zero.)

Proofsof

(2.1)

^{and other}closelyrelated results can be found in the references

[2] [10].

ACKNOWLEDGEMENT.

The author would liketothankthe

anonymous

referee for pointingoutsome notable omissions in theoriginal referencelist.

10.

REFERENCES

1.

TAKACS, L C3rrlbinatoril

^Methodsinthe

^Tl3ory

of Stochastic

Processes,

John Wileyand

Sons,

1974.

2.

BAXTER, G. An Operator

Identity,Pacific

J.

Math 8

(1958),

^649-663.

3.

BAXTER, G. An

Analytic

Approach

toFiniteFluctuationProblemsinProbability Theory,

Jour

d’

Analyse

Math,9

(1961),

31-70.

4.

FELLER, W. An I..ntroduction

^toProbability

Theory_

and

Its

Applications,^Vol.2,

Chap.

18,John Wileyand

Sons,

1966.

5.

KARLIN, S.

and

TAYLOR, H. M. ,A S0nd ^Course

^{inStochasticProcesses,}

^Chap.

^17,Academic

Press,

1981.

6.

POLLACZEK, E

Functionscaracteristiquesdes certainesrepartitions definiesau moven de la notiond’ordre.

Application

alatheode desattentes,

C. R.

Acad. Sci.Paris234

(1952),

2334-2336.

7.

SPFIER, E L A

Combinatorial

Lemma

andits

Application

^toProbability Theory,

Trans. Am.

Math. ^Soc,

²⁸

(1956),

329-339.

8.

SP1TZER, E L

lrinciples of

Random

^Walk,

Chap.

4,

Springer-Verlag,

1976.

9.

TAKACS, L On

Fluctuations of

Sums

of Random Variables,

Advances in

Mathematics,

Supplementary

Studies2

(1978),

^45-93.

WENDEL, J. G. Spitzer’s

Formula:

A

Short Proof,

Proc. Amer.

Math.

Soc.

9

(1958),

905-908.