Self-Correction of Transmission on Regular Trees

arXiv:math/0703762v1[math.PR]26Mar2007Self-CorretionofTransmissiononRegularTrees∗AlbertoGandol†andRobertoGuenzani‡February2,2008AbstratWeonsidernoisybinaryhannelsonregulartreesandintrodueperi-odienhanementsonsistingofloallyself-orretingthesignalinblokswithoutbreakofthesymmetryofthemodel.Wefousontherealistilassofwithin-desentself-orretionrealizedbyidentifyingalldesen-dantskgenerationsdownavertexwiththeirmajority.Weshowthatthisalsoallowsreonstrutionstritlybeyondtheritialdistortion.Wefur-theridentifythelimitatwhihtheritialdistortionsofwithin-desentkself-orretedtransmissiononverge,whihturnsouttobetheriti-alpointforferromagnetiIsingmodelonthattree.Wenallydisusshowsimilarphenomenatakeplaewiththebiologiallymoreplausiblemehanismofeliminatingsignalswhihareloallynotoherentwiththemajority.∗AMS2000subjetlassiation:Primary60K35;Seondary90B15,92C15Keywordsandphrases:tree,transmission,Isingmodel,majority,orretion,ellpat-terns.†ResearhpartiallysupportedbyitalianMIURPRINGrant#2004015228‡ResearhpartiallysupportedbyitalianMIURPRINGrant#200401522811IntrodutionWeonsiderabinaryhannelonaregulartree,asin[1℄,withadistortionrateε0ateverytransmissionandareinterestedinthereonstrutionofthestartingbitσ0fromthesignalsσWnatthen-thgenerationofthetree.Wefousonthemajorityrule,bywhihσ0isreonstrutedasthesymbolhavingmajorityinσWn.In[1℄itisshownthatforregulartreesthemajorityruleisasymptotiallyequivalenttotheoptimalmaximum-likelihoodrule,andthatthereisaritialdistortion¯εc=√r−12√rsuhthatforε¯εcnoasymptotireonstrutiontakesplaeandforε¯εcthereisasymptotireonstrution;seealso[11℄forareviewand[12℄foradynamialversionoftheseresults.Theaimofthispaperistoinvestigatehowanon-symmetrybreakingmeh-anismoforretionperformedwhiletransmittingthesignalanimprovereon-strutionbyeithermajorityormaximumlikelihood.Tothispurpose,wepro-posealoalself-orretionmethodbywhihthesignalisperiodiallyenhanedinbloksformedwithinthegenerations.Theenhanementusesmajorityruleandonsistsoftakingallsignalsinablokandhangingthemtoallagreewiththeirmajorityvalue(withrandomhoietobreaktie).Theself-orretionisbasedontheinformationavailableatthelevelofinterest,andthusaninpriniplebeperformedwhilethesignalistransmitted.Fromeveryvertexthetransmissionisthenontinuedasitusedtobeintheoriginalmehanismandthesymmetryofthemodelisnotbroken.Itiseasytoseethatwithnon-loalenhanementoneanreonstrutbeyondtheritialdistortion:infat,byforingallvertiesofeahgenerationtoagreewiththeirmajority,oneanreonstrutforeveryε∈[0,12).However,suhorretioninvolvestakingmajorityonlargerandlargerbloks,whihisnotanimplementablestrategy.Aslightlylessexpensiveself-orretionstrategyonsistsofusingbloksofxedsizeM(assoonasthegenerationislargeenough)andthenperformingself-orretionateverygeneration.Insetion2weshowthatforanynoiselevelε12itispossibletoahievereonstrutioninthiswaywithsuientlylargebloksizeM.Thisproedurehastheadvantageofinvolvingonlyaboundednumberofwithingenerationinformationexhangeinself-orretingablok,andthusouldinpriniplebeimplementedbyarealmahine.However,itstillinvolvesaverylargenumberofwithingenerationoperations,performedateahgeneration:iftheostofeahsuhoperationisnotzero(asinbasiallyallreasonablesituations)thenthetotalostmightbeometoohigh.We,therefore,restritourattention,inthesequel,toaself-orretionmeha-nismwhihontainsostsbyperformingself-orretionlessoften,andwhihhastheadditionaladvantageofbeingperformedwithinthedesentofsomesignalinvolvedinthepreviousorretion.Thiswithindesentself-orretionreduesimplementationosts,andallowssignalstobedispersedandlooseontataftertheirinvolvementintheenhanement,afeaturewhihouldbemeaningfulinarealistisetting.Thewithin-desentself-orretionatlevelkisperformedby2takingeahvertexatsomelk-thgeneration,l∈N,onsideringitsrkdesen-dantskgenerationsdown,andthenhangingthemtoagreewiththeirmajority(randomlybreakingties).Atrstsight,itisnotevenobviousthatsuhreonstrutionimprovesuponthenonself-orretedtransmission,butinsetion3weshowthat,exeptfork=1andr=2,thewithin-desentself-orretionatlevelkstritlyinreasestheritialdistortions,andthusisaneetiveenhanement.Theproofisbasedontheomparisonbetweentheself-orretionbasedonthemajoritytransformationwithoneorretionbasedonrandomtransformationwhihleavestheritialpointsunhanged.Therestoftheworkisdevotedtoidentifyingthelimitoftheritialdistor-tionsofthewithin-desentself-orretionoflevelkaskdiverges.Althoughitmightseemthatsuhmehanismisalmostuselessforlargek,itturnsoutthatinsteaditimprovesthetransmissionfurther.Toidentifythelargeklimit,insetion4weexploittheorrespondenewiththeIsingmodel.Infat,itiseasytoseethat,forregulartrees,thereonstru-tionproblemisequivalenttothefreeboundaryonditionsphasetransitionoftheferromagnetiIsingmodelonthetreewithinversetemperatureβsuhthat1−2ε=tanh(β).Suhtransitionoursattheritialinversetemperature¯βcsuhthatforβ¯βcthefreeboundaryIsingmodelisonvexombinationoftheextremalstates(see[1℄foradetaileddesription).Ontheotherhand,theIsingmodelundergoesitsregularphasetransition(withboundaryonditions)atalowerinversetemperatureβc¯βc.Intermsofp=tanh(β)andonareg-ulartreewithforwardbr