Vicious Random Walkers and a Discretization of Gau

arXiv:cond-mat/0107221v220Nov2001ViciousRandomWalkersandaDiscretizationofGaussianRandomMatrixEnsemblesTaroNagaoandPeterJ.Forrester†DepartmentofPhysics,GraduateSchoolofScience,OsakaUniversity,Toyonaka,Osaka560-0043,Japan†DepartmentofMathematicsandStatistics,UniversityofMelbourne,Victoria3010,AustraliaAbstractTheviciousrandomwalkerproblemonaonedimensionallatticeisconsidered.Manywalkerstakesimultaneousstepsonthelatticeandtheconfigurationsinwhichtwoofthemarriveatthesamesiteareprohibited.ItisknownthattheprobabilitydistributionofNwalkersafterMstepscanbewritteninadeterminantform.Usinganintegrationtechniqueborrowedfromthetheoryofrandommatrices,weshowthatarbitraryk-thordercorrelationfunctionsofthewalkerscanbeexpressedasquaterniondeterminantswhoseelementsarecompactlyexpressedintermsofsymmetricHahnpolynomials.11IntroductionTheviciouswalkerproblemfirstintroducedbyFisher[1]andthendevelopedbyForrester[2](seealso[3])recentlyattractsmuchattentioninmathematicalphysics.Fascinatingcon-nectionstootherresearchfields,suchasYoungtableauxincombinatorics[4],Kardar-Parisi-Zhang(KPZ)universalityinthetheoryofgrowthprocess[5]andthetheoryofrandommatrices[6],havebeenrevealedoneafteranother.Inthecontextofrandomma-trixtheory,theensembleofviciouswalkersinonedimensioncorrespondstoadiscretiza-tionoftheGaussianensemblesofrandommatrices.Thereforethetheoryofdiscretizedrandommatricesisexpectedtoshedlightonalloftherelatedproblems.Indeeddis-cretizedrandommatricesintheguiseofdiscreteCoulombgasesarecentraltotheworkofJohansson[4,7,8]inthesedirections.SupposethatthereareNwalkersonaonedimensionallattice.Inthelockstepversionofthemodel(asdistinctfromtherandomturnsversionconsideredintherecentwork[9]),ateachtimestepeachwalkermovestotheleftorrightonelatticesitewithequalprobability.Walkersare”vicious”sothattwoormorewalkersareprohibitedtoarriveatthesamesitesimultaneously.Thej-thwalkerstartsatthepositionx=2j−2and,afterMsteps,arrivesatx=Xj.Thewalkerconfigurationsformnonintersectingpathsinthex–tplane.AnexampleisgiveninFigure1.Furthermoreithaslongbeenrealized[10]thatthereisaone-to-onecorrespondencebetweensuchnonintersectingpathsandrandomrhombustilingsofahexagon,orsuitabletruncationthereof,involvingthreetypesofrhombi.ThisisalsoillustratedinFigure1.Thenumberoflocksteppathsisknowntobeexpressedasabinomialdeterminant[11,12,13]P1(X1,X2,···,XN)=detMM+Xj2−l+1j,l=1,2,···,N.(1.1)ThebinomialdeterminantcanbefurtherrewrittenasaproductformulaP1(X1,X2,···,XN)=2−N(N−1)/2NYj=1(M+N−j)!M+Xj2!M−Xj2+N−1!NYjl(Xj−Xl),(1.2)whereX1X2···XN.Nowweintroducenewvariablesxj=Xj−N+12,L=M+N−1(1.3)inordertoobtainacompactandsymmetricexpressionP1(x1,x2,···,xN)=CMNNYj=1qw(xj)NYjl|xj−xl|.(1.4)HereCMN=NYj=1(M+N−j)!(1.5)2MxtFigure1:NonintersectingpathsrepresentingaviciouswalkerconfigurationwithN=3walkersandM=4steps.Inthetopdiagramthesepathsaredrawninthex–tplane.Inthebottomdiagramsuperimposedonthepathsistheequivalentrhombitiling,involvingleftslopingrhombi(steptotheleft),rightslopingrhombi(steptotheright)andverticalrhombi.andw(x)=1L2+x!L2−x!2.(1.6)Insomeapplicationsoftheviciouswalkerproblemoneimposestheadditionalcon-straintthateachwalkerreturnstotheinitialpositionafter2Msteps.OneexampleistherhombustilingproblemofFigure1withtheregiontobetiledextendedtobesymmetricalaboutt=Mandthusmadeintoahexagon[8].InsuchcasesthenumberofpathsisgivenbythesquareofP1(x1,x2,···,xN):P2(x1,x2,···,xN)=C2MNNYj=1w(xj)NYjl|xj−xl|2.(1.7)Aswillberevisedbelow,thefunctionw(x)isaspecialcaseoftheHahnweightfunctionfromthetheoryofdiscreteorthogonalpolynomials.Theprobabilitydensity(1.7)withtheHahnweightisintimatelyrelatedtoHahnpolynomialsandsohasbeentermedtheHahnensemble[7,8].Weareinterestedinthenumberofpathsundertheconditionthatkwalkerstakefixedpositionsx1,x2,···,xkafterMsteps(k≤N).ThisnumberisgivenbythecorrelationfunctionsI(β)k(x1,x2,···,xk)=1(N−k)!∞Xxk+1=−∞∞Xxk+2=−∞···∞XxN=−∞Pβ(x1,x2,···,xN)(1.8)inboththecasesβ=1andβ=2.3Inthecasewithreturningwalkers(β=2),theevaluationofthecorrelationfunc-tionsisrelativelyeasy.IntroducingmonicorthogonalpolynomialsCj(x)=xj+···withorthogonalityrelations∞Xx=−∞w(x)Cj(x)Cl(x)=δjlhj,(1.9)wecanreadilyobtainI(2)k(x1,x2,···,xk)=C2MNN−1Yj=0hjdet[K(xj,xl)]j,l=1,2,···,k(1.10)withK(x,y)=qw(x)w(y)N−1Xj=01hjCj(x)Cj(y)=qw(x)w(y)1hN−1CN(x)CN−1(y)−CN−1(x)CN(y)x−y.(1.11)WecallCj(x)symmetricHahnpolynomialsanddefinethemintermsoftheHahnpoly-nomialsin§2.Themainpurposeofthispaperistoderiveananalogousformulaforthecorrelationfunctionswithnoreturningconstraint(β=1).Forthatpurpose,weagainmakeuseoftheabovesymmetricHahnpolynomialstorewritethecorrelationfunctionsintheformofadeterminantalthoughnowwithquaternionelements.TheHahnpolynomialsandtheirsymmetrizationareintroducedin§2.In§3,weintroducequaterniondeterminantformulasforthecorrelationfunctionsI(1)k(x1,···,xk).In§4,thecontinuouslimittotheGaussianensemblesisdiscussed.2SymmetricHahnPolynomialsTheHahnpolynomialsQn(x)areorthogonalpolynomialswithrespecttotheweightfunction[14]wH(x)=(a+x)!a!x!(L+b−x)!b!(L−x)!(2.1)onadiscretemeasure(xisrestrictedtobeaninteger).Whenthecoefficientof