The Candy model revisited Markov properties and in

CentrumvoorWiskundeenInformaticaPNAProbability,NetworksandAlgorithmsProbability,NetworksandAlgorithmsTheCandymodelrevisited:MarkovpropertiesandinferenceM.N.M.vanLieshout,R.S.StoicaREPORTPNA-R0115AUGUST2001CWIistheNationalResearchInstituteforMathematicsandComputerScience.ItissponsoredbytheNetherlandsOrganizationforScientificResearch(NWO).CWIisafoundingmemberofERCIM,theEuropeanResearchConsortiumforInformaticsandMathematics.CWI'sresearchhasatheme-orientedstructureandisgroupedintofourclusters.Listedbelowarethenamesoftheclustersandinparenthesestheiracronyms.Probability,NetworksandAlgorithms(PNA)SoftwareEngineering(SEN)Modelling,AnalysisandSimulation(MAS)InformationSystems(INS)Copyright©2001,StichtingCentrumvoorWiskundeenInformaticaP.O.Box94079,1090GBAmsterdam(NL)Kruislaan413,1098SJAmsterdam(NL)Telephone[phone]Telefax+31205924199ISSN1386-3711TheCandyModelRevisited:MarkovPropertiesandInferenceM.N.M.vanLieshoutandR.S.StoicaCWIP.O.Box94079,1090GBAmsterdam,TheNetherlandsABSTRACTThispaperstudiestheCandymodel,amarkedpointprocessintroducedbyStoicaetal.(2000).WeproveRuelleandlocalstability,investigateitsMarkovproperties,anddiscusshowthemodelmaybesampled.Finally,weconsiderestimationofthemodelparametersandpresentsomeexamples.2000MathematicsSubjectClassication:60G55,62M40.KeywordsandPhrases:Candymodel,MarkovchainMonteCarlosimulation,Markovmarkedpointprocess,maximumlikelihoodestimation,stability.Note:WorkcarriedoutunderprojectPNA4.3‘StochasticGeometry’.ThisresearchwassupportedbyNWOgrant‘Inferenceforrandomsets’(613-03-045).1.Set-upandnotationIn[36,37],Stoica,DescombesandZerubiaintroducedamarkedpointprocessmodelforlinesegments{dubbedCandy{aspriordistributionfortheimageanalysisproblemofextractinglinearnetworkssuchasroadsorriversfromimages(usuallyobtainedbyaerialphotographyorsatellites).Inthispaperweinvestigatetheanalyticalpropertiesofthemodel,focusingontheRuellecondition,localstabilityandtheinteractionstructure.Wealsostudystatisticalaspects,includingsimulationbyMarkovchainMonteCarloandparameterestimation.WeshallrepresentalinesegmentasapointinsomecompactsubsetKR2ofstrictlypositivevolume0(K)1withanattachedmarktakingvaluesintheCartesianproduct[lmin;lmax][0;)forsome0lminlmax1.Eachmarkedpoint(k;l;)canbeinterpretedasalinesegmentwithmidpointk,lengthl,andorientation.Ifrequired,anextramarkforthewidthofthesegmentmaybeadded.Notethatintheoriginalformulation[36,37],themarkspacefororientationsis[0;2].Acongurationoflinesegmentsisanitesetofmarkedpoints.Thus,forn2N0,writeSnforthesetofall(unordered)congurationss=fs1;:::;sngthatconsistofn,notnecessarilydistinct,markedpointssi2S=K[lmin;lmax][0;).Hence,thecongurationspacecanbewrittenas=[1n=0Sn,whichmaybeequippedwiththe-algebraFgeneratedbythemappingsfs1;:::;sng7!Pni=11fsi2AgthatcountthenumberofmarkedpointsinBorelsetsAS=K[lmin;lmax][0;).Ifthemarksarediscarded,thecongurationspaceofmidpointsisK=[1n=0Kn,whereKnisthesetofallcongurationsx=fk1;:::;kngthatconsistofn,notnecessarilydistinct,pointski2K;theassociated-algebraFKisgeneratedbythemappingscountingthenumberofpointsfallinginBorelsubsetsofK.ApointprocessonKisameasurablemappingfromsomeprobabilityspaceinto(K;FK);amarkedpointprocesswithpointsinKandmarksin[lmin;lmax][0;)isapointprocessontheproductspaceK[lmin;lmax][0;)withtheadditionalpropertythatthemarginalprocessofsegmentcentersisapointprocessonK.Forfurtherdetails,see[4].2PerhapsthesimplestmarkedpointprocessmodelisthePoissonprocessdenedbytheprobabilitymeasure(F)=1Xn=0e(K)n!f(lmaxlmin)gnZSZS1F(f(k1;l1;1);;(kn;ln;n)gd(k1)d(kn)dl1dlnd1dnon(;F).Inotherwords,under,midpointsareplacedinKaccordingtoaPoissonprocesswithintensitymeasure,towhichpointsindependent,uniformlydistributedmarksareassignedtodeterminethelengthandorientation.Exhibitingnointeractions,theabovePoissonmarkedpointprocessistheidealreferenceprocess.Indeed,onemaydenemorecomplicatedmodelsbyspecifyingaRadon{Nikodymderivativepwithrespectto.FortheCandymodel,ats=fs1;:::;sngwithsi=(ki;li;i)2K[lmin;lmax][0;),i=1;:::;n,p(s)=n(s)(nYi=1explilmaxlmax)nf(s)1ns(s)2nr(s)3no(s)4(1.1)where1;2;3;42(0;1)and0arethemodelparameters.Stoicaetal.recommend12.Thesucientstatisticsn(s),nf(s),ns(s),nr(s),no(s)representrespectivelythetotalnumberofsegments,thenumberof‘free’ones,thenumberofsegmentswithasingleoneofitsendpointsnearanothersegmentendpoint,thenumberofpairsofsegmentscrossingattoosharpangles,andthenumberofpairsthataredisoriented.Amoreprecisedenitionwillbegiveninsection2below.Intuitivelyspeaking,therearepenaltiesattachedtoeachfreeandsinglyconnectedsegment,aswellastoeachsharpcrossingandtoeverydisagreementinorientation.Theplanofthispaperisasfollows.Insection2,arigorousdenitionoftheCandymodelisgiven.WeestablishtheRuelleconditionandlocalstability.Furthermore,wedeneseveralrelationsonthecongurationspace,andinvestigatetheMarkovbehavioroftheCandymodel.Insection3,aMetropolis{HastingsalgorithmbasedonbirthsanddeathsissuggestedforsamplingfromtheCandymodel.Wediscusstheconvergenceofthealg