(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: final_uai02.dvi %%Pages: 8 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -o final_uai02.ps final_uai02.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2002.06.03:1055 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet %%BeginProcSet: special.pro %! TeXDict begin/SDict 200 dict N SDict begin/@SpecialDefaults{/hs 612 N /vs 792 N/ho 0 N/vo 0 N/hsc 1 N/vsc 1 N/ang 0 N/CLIP 0 N/rwiSeen false N /rhiSeen false N/letter{}N/note{}N/a4{}N/legal{}N}B/@scaleunit 100 N /@hscale{@scaleunit div/hsc X}B/@vscale{@scaleunit div/vsc X}B/@hsize{ /hs X/CLIP 1 N}B/@vsize{/vs X/CLIP 1 N}B/@clip{/CLIP 2 N}B/@hoffset{/ho X}B/@voffset{/vo X}B/@angle{/ang X}B/@rwi{10 div/rwi X/rwiSeen true N}B /@rhi{10 div/rhi X/rhiSeen true N}B/@llx{/llx X}B/@lly{/lly X}B/@urx{ /urx X}B/@ury{/ury X}B/magscale true def end/@MacSetUp{userdict/md known {userdict/md get type/dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N/note{}N/legal{}N/od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{ itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{closepath}}pathforall newpath counttomark array astore/gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack} if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{ noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N/cp{pop pop showpage pm restore}N end}if}if}N/normalscale{ Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale }if 0 setgray}N/psfts{S 65781.76 div N}N/startTexFig{/psf$SavedState save N userdict maxlength dict begin/magscale true def normalscale currentpoint TR/psf$ury psfts/psf$urx psfts/psf$lly psfts/psf$llx psfts /psf$y psfts/psf$x psfts currentpoint/psf$cy X/psf$cx X/psf$sx psf$x psf$urx psf$llx sub div N/psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR/showpage{}N/erasepage{}N/copypage{}N/p 3 def @MacSetUp}N/doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N/endTexFig{end psf$SavedState restore}N/@beginspecial{SDict begin/SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count/ocount X/dcount countdictstack N}N/@setspecial{ CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if/showpage{}N/erasepage{}N/copypage{}N newpath}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end} repeat grestore SpecialSave restore end}N/@defspecial{SDict begin}N /@fedspecial{end}B/li{lineto}B/rl{rlineto}B/rc{rcurveto}B/np{/SaveX currentpoint/SaveY X N 1 setlinecap newpath}N/st{stroke SaveX SaveY moveto}N/fil{fill SaveX SaveY moveto}N/ellipse{/endangle X/startangle X /yrad X/xrad X/savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 39158280 55380996 1000 600 600 (final_uai02.dvi) @start %DVIPSBitmapFont: Fa cmex7 7 2 /Fa 2 20 df<150E151C1538157015E0EC01C0EC0380EC07005C141E5C5CA25C495AA249 5A13075C130F49C7FCA2133EA25BA25BA3485AA212035BA212075BA2120FA25BA2121FA2 90C8FCA25AA4123E127EA7127C12FCB3A5127C127EA7123E123FA47EA27FA2120FA27FA2 1207A27F1203A27F1201A26C7EA3137CA27FA27FA26D7E13078013036D7EA26D7E1478A2 80808080EC0380EC01C0EC00E015701538151C150E1F8B728231>18 D<12E012707E7E7E7E6C7E6C7E7F6C7E13787FA27F7FA26D7E801303806D7EA26D7EA214 7CA280A380A21580140FA215C01407A215E0A21403A215F0A21401A215F8A4140015FCA7 157C157EB3A5157C15FCA715F81401A415F0A21403A215E0A21407A215C0A2140F1580A2 141F1500A2143EA35CA25CA2495AA2495A5C13075C49C7FCA2131E5BA25B5B485A5B485A 48C8FC120E5A5A5A5A1F8B7D8231>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb lasy10 10 1 /Fb 1 51 df<003FB712FEB9FCA300F0C9120FB3B3A4B9FCA4303079B43E>50 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmmi12 12 4 /Fc 4 101 df97 DIII E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd line10 10 4 /Fd 4 75 df<1C0C1C1E1C3E1C7E1CFCF301F8F303F0F307E0F30FC0F31F80F33F001B7E 63505A505A505A505A505A50C7FC1A7E624F5A4F5A4F5A4F5A4F5A4FC8FC197E614E5A4E 5A4E5A4E5A4E5A4EC9FC187E604D5A4D5A4D5A4D5A4D5A4DCAFC177E5F4C5A4C5A4C5A4C 5A4C5A4CCBFC167E5E4B5A4B5A4B5A4B5A4B5A4BCCFC157E5D4A5A4A5A4A5A4A5A4A5A4A CDFC147E5C495A495A495A495A495A49CEFC137E5B485A485A485A485A485A48CFFC127E 5A5A1260575782D453>0 D<19C0F001E01803180719C0F00F80181F1900183E187E187C 601701604D5A1707604D5A171F95C7FC173E177E177C5F16015F4C5A16075F4C5A161F94 C8FC163E167E167C5E15015E4B5A15075E4B5A151F93C9FC153EA25D15FC5D4A5A14035D 4A5A140F5D4ACAFC5C143E5C14FC5C495A13035C495A130F5C49CBFC5B133E5B13FC5B48 5A12035B485A120F5B48CCFC5A123E5A12FC5A5A12603B5782D437>10 D<126012F87E127E7E6C7E6C7E6C7E6C7E6C7E6C7E137E7F6D7E6D7E6D7E6D7E6D7E6D7E 147E806E7E6E7E6E7E6E7E6E7E6E7E157E816F7E6F7E6F7E6F7E6F7E6F7E167E82707E70 7E707E707E707E707E177E83717E717E717E717E717E717E187E84727E727E727E727E72 7E727E197E85737E737E737E737E737E737E1A7E86747E747E747E747E747E747E1B7E87 F31F80F30FC0F307E0F303F0F301F8F300FC1C7E1C3E1C1E1C0C575782D453>64 D<126012F07E7E127C7E123F7E6C7E7F12076C7E7F12016C7E7F137C7F133F7F6D7E8013 076D7E8013016D7E80147C80143F806E7E8114076E7E8114016E7E81157C81A28182150F 6F7E8215036F7E821500167C167E163E8283160F707E831603707E831600177C177E173E 8384170F717E841703717E841700187C187E183E841980180FF007C019E018031801F000 C03B5782D437>74 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe lcircle10 10 1 /Fe 1 105 df104 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmsy5 5 4 /Ff 4 111 df102 D<12FEEAFFC0EA07E0EA01F01200AD1378 7FEB1FE01307131FEB3C005B5BAD1201EA07E0B45A48C7FC13297B9E1F>I<12E0B3B3A5 0329799E13>106 D<12E0A27E1270A212781238123C121C121E120EA2120F7E7F12037F 1201A27F12007F1370A213781338133C131C131E130EA2130F7F1480130314C01301A214 E01300146013297B9E1F>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmmi5 5 14 /Fg 14 116 df<000C147015F85A0038147800301438EA60039038078018A239C00F0030 A21570D8E00E136039F01F01E039FCFFEFC0007FEBFF8001F31300383FE1FE380F80F81D 127E9125>33 D<127012F812FCA2127C120CA31218A2123012601240060D7A8413>59 D64 DI<0003B512F815FE3A003E001F80ED0FC015 0715035B1507A2ED0F8049EB1F00157E90B512F85D3901F001F8EC007E153E81485AA315 1E4848133E5D5DEC07F0B612C04AC7FC221C7C9B2B>I78 D<903807F02090381FFC609038780EE09038E003C03801C001EA0380A2D8 07001380A26DC7FCA27FEA03FC3801FFC06C13F0EB3FF8EB01FCEB003E141E140EA21230 A200705BA25C00785B38FE01E038C7FF80D881FEC7FC1B1E7B9C24>83 D<001FB61280A2393E01F00F0038EC030012701260EB03E012C0A3C64848C7FCA4495AA4 49C8FCA4133EA4381FFFF85C211C7C9B23>I<137F3801FFC0EA07C3380F03E0381C07C0 EA3C0348C7FCA25AA500701340007813E0383C03C0381FFF00EA07F813127C911B>99 D<137013F8A213F013E01300A6EA0F80EA1FC0EA31E01261A2EAC3C01203EA0780A3EA0F 001308EA1E18A213301370EA0FE0EA07800D1D7D9C16>105 DII<380F03F0383F87FC3833DC1EEA63F8EAC3F0 13E0EA03C0A248485AA3EC7820D80F00136014F015C014F1001EEB7F80000CEB3E001B12 7D9125>110 D<137E3801FF80EA0381380703C0380E0780EB0300EA0F80EA07F86CB4FC 6C1380EA000FEA3003127812F8EB0700EAF00EEA7FFCEA1FF012127C911C>115 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmr5 5 7 /Fh 7 127 df3 D<48B5FCA2380007C0A4EB3FF80003B51280390FC7C7E0391F07C1 F0003CEBC078007C147C00F8143EA4007C147C003C1478001FEBC1F0390FC7C7E00003B5 128039003FF800EB07C0A448B5FCA21F1C7C9B28>8 D<13301360EA01C0EA0380130012 06120E5AA25AA35AA312F0AB1270A37EA37EA27E12067E1380EA01C0EA006013300C297B 9E16>40 D<12C0126012387E120C7E1207EA0380A2EA01C0A3EA00E0A313F0AB13E0A3EA 01C0A3EA0380A2EA070012065A121C5A12605A0C297C9E16>I<1360EA01E0120F12FF12 F11201B3A3387FFF80A2111C7B9B1C>49 DI126 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmr7 7 12 /Fi 12 127 df0 D<1438A3147CA314FEA2497E14BFA201037F141FA20106 7F140FA2010C7F1407A201187F1403A201307F1401A201607F140001E07F49137EA20001 147F497FA248C71380151FA24815C05AD81FC0EB3FE03AFFF001FFFEA2272A7EA92D>3 D<90383FFFFCA2010090C7FC147EA5903803FF80013F13F89038FC7E7ED803E0EB0F80D8 0FC0EB07E0D81F00EB01F04815F8007EEC00FCA248157EA6007E15FCA26CEC01F86C15F0 D80FC0EB07E0D803E0EB0F80D800FCEB7E0090383FFFF801031380D9007EC7FCA514FF01 3F13FCA227287DA72F>8 D<903803FF80011F13F090387E00FCD801F8133FD807E0EB0F C04848EB07E04848EB03F048C7EA01F8A2007EEC00FCA248157EA7007E15FCA36CEC01F8 A26C6CEB03F0000F15E0A26C6CEB07C0000315806C6CEB0F00A26C6C131ED8C070EB1C06 0178133CD86038EB380C01181330011C13700070151CD87FFCEB7FFC003F15F8A327297D A82F>10 D<1306130C13181330136013E0EA01C0EA0380A2EA07005A120E121EA2121C12 3CA35AA512F85AAB7E1278A57EA3121C121EA2120E120F7EEA0380A2EA01C0EA00E01360 13301318130C13060F3B7AAB1A>40 D<12C012607E7E7E120E7EEA0380A2EA01C013E012 0013F0A213701378A3133CA5133E131EAB133E133CA51378A3137013F0A213E0120113C0 EA0380A2EA0700120E120C5A5A5A5A0F3B7DAB1A>I<140EB3A2B812E0A3C7000EC8FCB3 A22B2B7DA333>43 D48 D<13381378EA01F8121F12FE12E01200B3AB487EB5 12F8A215267BA521>I<13FF000313E0380E03F0381800F848137C48137E00787F12FC6C EB1F80A4127CC7FC15005C143E147E147C5C495A495A5C495A010EC7FC5B5B9038700180 13E0EA0180390300030012065A001FB5FC5A485BB5FCA219267DA521>I61 D<380F8010381FF038383FFFF04813E038E07FC038400F80 15067BA621>126 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj msbm7 7 1 /Fj 1 84 df<017F13C03803FFE1380FC0FF381F803E383F001C0076130E0066130700E6 130300C61301A200C7130012C36D1300EAC1E0EAE070EA603C38700F80383803E0381C00 78000F131E380380073901F0038039007C01C090380F00E09038038070903801E0309038 007038EC3818141C00C0130C140E6C1306A215386C14306C147000DCEB0EE000CEEB0DC0 00DFEB1F8039FFC07E0038E1FFF838C03FC01D2A7EA830>83 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmti10 10 54 /Fk 54 123 df12 D<150C151C153815F0EC01E0EC03C0EC0780EC0F00141E5C147C5C5C495A1303 495A5C130F49C7FCA2133EA25BA25BA2485AA212035B12075BA2120F5BA2121FA290C8FC A25AA2123EA2127EA2127CA412FC5AAD1278A57EA3121C121EA2120E7EA26C7E6C7EA212 001E5274BD22>40 D<140C140E80EC0380A2EC01C015E0A2140015F0A21578A4157C153C AB157CA715FCA215F8A21401A215F0A21403A215E0A21407A215C0140F1580A2141F1500 A2143EA25CA25CA2495AA2495A5C1307495A91C7FC5B133E133C5B5B485A12035B48C8FC 120E5A12785A12C01E527FBD22>I44 D<387FFFF8A2B5FCA214F0150579941E>I<120EEA3F80127F12FFA31300127E123C0909 778819>I<15181538157815F0140114031407EC0FE0141F147FEB03FF90383FEFC0148F EB1C1F13001580A2143FA21500A25CA2147EA214FEA25CA21301A25CA21303A25CA21307 A25CA2130FA25CA2131FA25CA2133FA291C7FC497EB61280A31D3877B72A>49 DII<157F913803FFC0020F13E0EC3F8191387E00F002 F81370903903F003F0903807E007EB0FC0EB1F80020013E04914C0017E90C7FC13FE5B48 5AA21203485AA2380FE07E9038E1FF809038E783E0391FCE01F09038DC00F813F8484813 7C5B157E5B485AA390C712FE5A5AA214015D5AA214035DA348495A5D140F5D4A5A6C49C7 FC127C147C6C485A6C485A6CB45A6C1380D801FCC8FC243A76B72A>54 D<133C137E13FF5AA313FE13FCEA00701300B2120EEA3F80127F12FFA31300127E123C10 2477A319>58 D65 D<0107B612FCEFFF8018C0903B000FF0001FF04BEB07F81703021F15FC17014B14FEA202 3F1400A24B1301A2147F18FC92C7120318F84A140718F04AEC0FE0EF1FC00101ED3F80EF 7F004AEB01FEEE07F849B612E05F9139F80007F0EE01FC01076E7E177F4AEC3F80A2010F 16C0171F5CA2131F173F5CA2133FEF7F805C1800017F5D4C5A91C7485A5F49140FEE1FE0 494A5A00014AB45AB748C7FC16F816C037397BB83A>II<0103B612FEEFFFC018F0903B0007F8 000FF84BEB03FCEF00FE020F157FF03F804B141F19C0021F150F19E05D1807143F19F05D A2147FA292C8FCA25C180F5CA2130119E04A151FA2130319C04A153FA201071780187F4A 1600A2010F16FEA24A4A5A60011F15034D5A4A5D4D5A013F4B5A173F4A4AC7FC17FC017F EC03F84C5A91C7EA1FC04949B45A007F90B548C8FCB712F016803C397CB83F>I<0107B8 FCA3903A000FF000034BEB007F183E141F181E5DA2143FA25D181C147FA29238000380A2 4A130718004A91C7FC5E13015E4A133E167E49B512FEA25EECF8000107147C163C4A1338 A2010F147818E04A13701701011F16C016004A14031880013F150718004A5CA2017F151E 173E91C8123C177C4915FC4C5A4914070001ED7FF0B8FCA25F38397BB838>I<0107B712 FEA3903A000FF000074B1300187C021F153CA25DA2143FA25D1838147FA292C8FCEE0380 4A130718004A91C7FCA201015CA24A131E163E010314FE91B5FC5EA2903807F800167C4A 1378A2130FA24A1370A2011F14F0A24A90C8FCA2133FA25CA2137FA291CAFCA25BA25B48 7EB6FCA337397BB836>II<0103B5D8F80FB512E0A390260007F8C7381FE0004B5D A2020F153F615DA2021F157F96C7FC5DA2023F5D605DA2027F14016092C7FCA24A140360 5CA249B7FC60A202FCC712070103150F605CA20107151F605CA2010F153F605CA2011F15 7F95C8FC5CA2013F5D5F5CA2017F14015F91C7FC491403007FD9FE01B512F8B55BA24339 7CB83E>I<0103B512F8A390390007F8005DA2140FA25DA2141FA25DA2143FA25DA2147F A292C7FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133F A25CA2137FA291C8FC497EB6FCA25C25397CB820>I<0107B512FCA25E9026000FF8C7FC 5D5D141FA25DA2143FA25DA2147FA292C8FCA25CA25CA21301A25CA21303A25CA21307A2 5CA2130F170C4A141CA2011F153C17384A1478A2013F157017F04A14E01601017F140317 C091C71207160F49EC1F80163F4914FF000102071300B8FCA25E2E397BB834>76 D<902607FFF8923807FFF0614F13E0D9000FEFF0004F5AA2021F167FF1EFC0141DDA1CFC EC01CF023C16DF9538039F800238ED071FA20278ED0E3F97C7FC0270151CA202F04B5AF0 707E14E0037E14E0010117FE4D485A02C0EC0380A20103ED0701610280140EA20107ED1C 0305385B14006F137049160705E05B010EEC01C0A2011E913803800F61011CEC0700A201 3C020E131F4C5C1338ED1FB80178163F04F091C8FC01705CA201F04A5B187E00015DD807 F816FEB500C09039007FFFFC151E150E4C397AB84A>I<902603FFF891B512E0A281D900 07923807F8006F6E5A61020F5E81DA0E7F5DA2021E6D1307033F92C7FC141C82DA3C1F5C 70130EEC380FA202786D131E0307141C147082DAF003143C70133814E0150101016E1378 030014705C8201036E13F0604A1480163F010715C1041F5B91C7FC17E149EC0FE360010E 15F31607011E15FF95C8FC011C80A2013C805F1338160013785F01F8157CEA03FC267FFF E0143CB51538A243397CB83E>I<0107B612F817FF1880903B000FF0003FE04BEB0FF0EF 03F8141FEF01FC5DA2023F15FEA25DA2147FEF03FC92C7FCA24A15F817074A15F0EF0FE0 1301EF1FC04AEC3F80EFFE0001034A5AEE0FF091B612C04CC7FCD907F8C9FCA25CA2130F A25CA2131FA25CA2133FA25CA2137FA291CAFCA25BA25B1201B512FCA337397BB838>80 D<0103B612F017FEEFFF80903B0007F8003FC04BEB0FF01707020FEC03F8EF01FC5DA202 1F15FEA25DA2143FEF03FC5DA2027FEC07F818F092C7120F18E04AEC1FC0EF3F004A14FE EE01F80101EC0FE091B6128004FCC7FC9138FC003F0103EC0F80834A6D7E8301071403A2 5C83010F14075F5CA2011F140FA25CA2133F161F4AECE007A2017F160F180E91C7FC4902 0F131C007F01FE153CB5913807F078040313F0CAEAFFE0EF3F80383B7CB83D>82 D<92383FC00E913901FFF01C020713FC91391FC07E3C91393F001F7C027CEB0FF84A1307 49481303495A4948EB01F0A2495AA2011F15E091C7FCA34915C0A36E90C7FCA2806D7E14 FCECFF806D13F015FE6D6D7E6D14E0010080023F7F14079138007FFC150F15031501A215 00A2167C120EA3001E15FC5EA3003E4A5AA24B5AA2007F4A5A4B5A6D49C7FC6D133ED8F9 F013FC39F8FC03F839F07FFFE0D8E01F138026C003FCC8FC2F3D7ABA2F>I<0007B812E0 A25AD9F800EB001F01C049EB07C0485AD900011403121E001C5C003C1780140312380078 5C00701607140700F01700485CA2140FC792C7FC5DA2141FA25DA2143FA25DA2147FA292 C9FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CEB3FF0007FB512F8B6FC A2333971B83B>I86 DI<14F8EB07FE90381F871C90383E03FE137CEBF8011201 48486C5A485A120FEBC001001F5CA2EA3F801403007F5C1300A21407485C5AA2140F5D48 ECC1C0A2141F15831680143F1587007C017F1300ECFF076C485B9038038F8E391F0F079E 3907FE03FC3901F000F0222677A42A>97 D<133FEA1FFFA3C67E137EA313FE5BA312015B A312035BA31207EBE0F8EBE7FE9038EF0F80390FFC07C013F89038F003E013E0D81FC013 F0A21380A2123F1300A214075A127EA2140F12FE4814E0A2141F15C05AEC3F80A215005C 147E5C387801F8007C5B383C03E0383E07C0381E1F80D80FFEC7FCEA01F01C3B77B926> I<147F903803FFC090380FC1E090381F0070017E13784913383901F801F83803F0031207 13E0120FD81FC013F091C7FC485AA2127F90C8FCA35A5AA45AA3153015381578007C14F0 007EEB01E0003EEB03C0EC0F806CEB3E00380F81F83803FFE0C690C7FC1D2677A426>I< ED01F815FFA3150316F0A21507A216E0A2150FA216C0A2151FA21680A2153FA202F81300 EB07FE90381F877F90383E03FF017C5BEBF80112013803F00048485B120FEBC001121F5D EA3F801403127F01005BA214075A485CA2140FA248ECC1C0A2141F15C3ED8380143F1587 007C017F1300ECFF076C485B9038038F8E391F0F079E3907FE03FC3901F000F0253B77B9 2A>I<147F903803FFC090380FC1E090383F00F0017E13785B485A485A485A120F4913F8 001F14F0383F8001EC07E0EC1F80397F81FF00EBFFF891C7FC90C8FC5A5AA55AA2153000 7C14381578007E14F0003EEB01E0EC03C06CEB0F806CEB3E00380781F83803FFE0C690C7 FC1D2677A426>IIIII107 DI< D801E001FEEB07F03C07F803FF801FFC3C0E3C0F07C0783E3C1E3E3C03E1E01F261C1F78 D9F3C013803C383FF001F7800F02E01400007801C013FE007018C002805B4A4848EB1F80 EAF07FD8E07E5CA200000207143F01FE1700495CA2030F5C0001177E495C18FE031F5C12 0349DA8001131C18F8033F153C00070403133849020013F0A24B1570000F17E049017E15 F019E003FEECE1C0001FEE01E34949903800FF000007C70038143C3E2679A444>II<147F903803FFC090380FC1F090381F00F801 7E137C5B4848137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA215FF5A48 14FEA2140115FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F00147E6C 13F8380F83F03803FFC0C648C7FC202677A42A>I<9039078007C090391FE03FF090393C F0787C903938F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E113C15CA2 D80003143FA25CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E013F495A6E 485A5E6E48C7FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A25BA21203 A25B1207B512C0A3293580A42A>II<3903 C003F0390FF01FFC391E783C0F381C7C703A3C3EE03F8038383FC0EB7F80007815000070 1300151CD8F07E90C7FCEAE0FE5BA2120012015BA312035BA312075BA3120F5BA3121F5B A3123F90C9FC120E212679A423>I<14FE903807FF8090380F83C090383E00E04913F001 78137001F813F00001130313F0A215E00003EB01C06DC7FC7FEBFFC06C13F814FE6C7F6D 13807F010F13C01300143F141F140F123E127E00FE1480A348EB1F0012E06C133E00705B 6C5B381E03E06CB45AD801FEC7FC1C267AA422>II<13F8D803FEEB01C0D8078FEB03E0390E0F8007121E121C0038 140F131F007815C01270013F131F00F0130000E015805BD8007E133FA201FE14005B5D12 0149137EA215FE120349EBFC0EA20201131E161C15F813E0163CD9F003133814070001EC F07091381EF8F03A00F83C78E090393FF03FC090390FC00F00272679A42D>I<01F0130E D803FC133FD8071EEB7F80EA0E1F121C123C0038143F49131F0070140FA25BD8F07E1400 00E08013FEC6485B150E12015B151E0003141C5BA2153C000714385B5DA35DA24A5A1403 00035C6D48C7FC0001130E3800F83CEB7FF8EB0FC0212679A426>I<01F01507D803FC90 3903801F80D8071E903907C03FC0D80E1F130F121C123C0038021F131F49EC800F007016 07A249133FD8F07E168000E0ED000313FEC64849130718000001147E5B03FE5B0003160E 495BA2171E00070101141C01E05B173C1738A217781770020314F05F0003010713016D48 6C485A000190391E7C07802800FC3C3E0FC7FC90393FF81FFE90390FE003F0322679A437 >I<903907E007C090391FF81FF89039787C383C9038F03E703A01E01EE0FE3803C01F01 8013C0D8070014FC481480000E1570023F1300001E91C7FC121CA2C75AA2147EA214FEA2 5CA21301A24A1370A2010314F016E0001C5B007E1401010714C000FEEC0380010F130701 0EEB0F0039781CF81E9038387C3C393FF03FF03907C00FC027267CA427>I<13F0D803FC EB01C0D8071EEB03E0D80E1F1307121C123C0038140F4914C01270A249131FD8F07E1480 12E013FEC648133F160012015B5D0003147E5BA215FE00075C5BA214015DA314035D1407 0003130FEBF01F3901F87FE038007FF7EB1FC7EB000F5DA2141F003F5C48133F92C7FC14 7E147C007E13FC387001F8EB03E06C485A383C1F80D80FFEC8FCEA03F0233679A428>I< 903903C0038090380FF007D91FF81300496C5A017F130E9038FFFE1E9038F83FFC3901F0 07F849C65A495B1401C7485A4A5A4AC7FC141E5C5C5C495A495A495A49C8FC131E5B4913 1C5B4848133C48481338491378000714F8390FF801F0391FFF07E0383E1FFFD83C0F5B00 785CD8700790C7FC38F003FC38E000F021267BA422>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl msbm10 10 1 /Fl 1 84 df83 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmmi10 10 41 /Fm 41 127 df13 D<1403EC3FF891387FFF80D901E313C014800103133F9138001F80ED070092C7FC80A280 A2808013018080130080147F81143F8149B47E130790380F8FF0EB3E0F496C7E13F83801 F003D803E07F1207380FC0011380121FEA3F0014005A127EA212FE5D481301A35DA24813 035D6C13075D127C4A5A6C91C7FC5C6C133E6C6C5A3807C0F03801FFE0D8003FC8FC223D 7DBB25>II<1406A6ED7FC0913807FFE0ED806091381FFF E091383C7F8002F0C7FC495A495A495A49C8FC130E131E5B5B5BA2485AA2485A485AA248 C9FCA3121EA2123E123CA3127C1278A412F8A57EA2127C127E127F7F6C7E13F0EA1FFE38 0FFFC06C13F86C13FEC66D7E013F7F01077F1300EC1FF0140714031401A35DA290381803 C0131C90380F0780D903FEC7FCEB00F8234B7CB924>II<133F14C0EB07F06D7E801301A26D7EA3147FA36E 7EA36E7EA36E7EA36E7EA36E7EA36E7EA26E7EA214014A7E5C4A7E91381E3F80143C1478 4A6C7E1301EB03E049486C7EEB0F80EB1F00496D7E137E5B48486D7E485A485A000F6E7E 485A485A48C87E12FE167F4816800070151F293B7CB930>21 DI<0140151E01E015 3F00015E484816805B120790C9123F000E161F170F5A1707481700A2003014C014010070 010314061260A2170E00E04948130C5A171C92C7FC5FA26C495C4A14F04A7E6C017F495A 4A6C485A3AF801F7E00F3BFE0FF3F83F80267FFFE3B5FC02C191C7FC6C01815B02005BD8 0FFCEB7FF0D803F0EB0FC031267FA434>33 D<121C127FEAFF80A5EA7F00121C09097988 17>58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E 5A5A5A12600A19798817>II<126012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF90 38007FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF9238007FC0EE1FF0EE 07FCEE01FF9338007F80EF1FC0A2EF7F80933801FF00EE07FCEE1FF0EE7FC04B48C7FCED 07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848 CAFCEA07FCEA3FF0EA7FC048CBFC12FC1270323279AD41>62 D64 D<1760177017F01601A21603A21607160FA24C7EA216331673166316C3A2ED0183A2ED03 03150683150C160115181530A21560A215C014011580DA03007FA202061300140E140C5C 021FB5FC5CA20260C7FC5C83495A8349C8FC1306A25BA25B13385B01F01680487E000716 FFB56C013F13FF5EA2383C7DBB3E>I<0103B77E4916F018FC903B0007F80003FE4BEB00 FFF07F80020FED3FC0181F4B15E0A2141FA25DA2143F19C04B143F1980027F157F190092 C812FE4D5A4A4A5AEF0FF04AEC1FC005FFC7FC49B612FC5F02FCC7B4FCEF3FC00103ED0F E0717E5C717E1307844A1401A2130F17035CA2131F4D5A5C4D5A133F4D5A4A4A5A4D5A01 7F4BC7FC4C5A91C7EA07FC49EC3FF0B812C094C8FC16F83B397DB83F>I<0103B812F05B A290260007F8C7123F4B1407F003E0020F150118005DA2141FA25D19C0143FA24B1330A2 027F1470190092C7126017E05C16014A495A160F49B6FCA25F9138FC000F01031407A24A 6DC8FCA201075C18034A130660010F160693C7FC4A150E180C011F161C18184A1538A201 3F5E18F04A4A5AA2017F15074D5A91C8123F49913803FF80B9FCA295C7FC3C397DB83D> 69 D71 D<0103B5D8F803B512F8495DA290260007 F8C73807F8004B5DA2020F150F615DA2021F151F615DA2023F153F615DA2027F157F96C7 FC92C8FCA24A5D605CA249B7FC60A202FCC7120101031503605CA201071507605CA2010F 150F605CA2011F151F605CA2013F153F605CA2017F157F95C8FC91C8FC496C4A7EB690B6 FCA345397DB845>I<0107B512FCA216F890390007F8005DA2140FA25DA2141FA25DA214 3FA25DA2147FA292C7FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CA213 1FA25CA2133FA25CA2137FA291C8FC497EB6FCA326397DB824>I<0103B6FC5B5E902600 07FCC8FC5D5D140FA25DA2141FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25C A21303A25CA2130718404A15C0A2010F150118804A1403A2011F16005F4A1406170E013F 151E171C4A143C177C017F5D160391C7120F49EC7FF0B8FCA25F32397DB839>76 D<902603FFF891381FFFF8496D5CA2D90007030113006FEC007C02061678DA0EFF157081 020C6D1460A2DA1C3F15E0705CEC181F82023815016F6C5C1430150702706D1303030392 C7FC02607FA2DAE0015C701306ECC0008201016E130EEF800C5C163F0103EDC01C041F13 1891C713E0160F49EDF03818300106140717F8010E02031370EFFC60130CEE01FE011C16 E004005B011815FF177F1338600130153FA20170151F95C8FC01F081EA07FCB512E01706 A245397DB843>78 D<4BB4FC031F13F09238FE01FC913903F0007EDA07C0EB1F80DA1F80 EB0FC0023EC7EA07E002FCEC03F0495A4948EC01F8495A4948EC00FC495A013F16FE49C9 FC13FE187F485A12035B12075B120F4916FF121FA2485AA34848ED01FEA448C9EA03FCA3 EF07F8A218F0170F18E0171F18C0EF3F807EEF7F0017FEDA07C05B6C90391FF001F89039 80383803001F496C485A9139E00C0FE0260FC0C0EB1F80D807E1D90E3FC7FC0280137ED8 03F1EB07F8D801F95C3A007FC00FC0903A3FE07F0003903807FFFE0100018F5BDA000F13 06170E171E705A177CEEC1F816FF5FA25F5F6F5B6F48C7FCED00F8384B7CBA42>81 D<0103B612F849EDFF8018E0903B0007F8001FF84BEB03FCEF00FE020F157FA24BEC3F80 A2021F16C0A25DA2143FF07F805DA2027FEDFF006092C7485A4D5A4A4A5A4D5A4AEC1F80 057FC7FC0101EC07F891B612E094C8FC9139FC000FC00103EC03F0707E4A6D7E83130717 7E5C177F010F5D5F5CA2011F1401A25CA2133F16034A4A1360A2017F17E019C091C71401 496C01011480B61503933900FE0700EF7E0ECAEA1FFCEF07F03B3B7DB83F>I<92391FE0 0380DBFFFC130002036D5A91390FE01F8F91393F0007DF027EEB01FE02F81300495A4948 147E177C4948143C495AA2011F153891C8FCA3491530A28094C7FC80806D7E14FEECFFE0 6D13FE6DEBFFC06D14F06D806D80021F7F02037FEC003F03037F1500167F163F161FA312 0C160FA2001C151F94C7FCA3003C153EA25E003E5D127E007F4A5A6D495A6DEB0FC0D8F9 F0495AD8F0FE01FEC8FC39E03FFFF8010F13E0D8C00190C9FC313D7CBA33>I<0003B812 FEA25A903AF8003FC00101C0913880007E4848163C90C7007F141C121E001C92C7FCA248 5CA200305C007017180060130112E0485CA21403C716005DA21407A25DA2140FA25DA214 1FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25CEB0FFC003FB6FC 5AA237397EB831>I<91B712FCA25B9239E00007F84AC7EA0FF0D903F8EC1FE04AEC3FC0 4AEC7F804A150049485C91C7485A4C5A010E4A5A4C5A010C4A5A011C4A5A01185D167F4C C7FC90C7485A4B5A4B5A4B5A5E151F4B5A4B5A4BC8FC4A5A4A5A4A5A5D140F4A5A4A5A4A 48130C4AC7FC495A4A141C01031518495A494814384948143049481470495A49C812F049 5D000115014848140348484A5A4848140F4848141F4848EC7F804848EB07FF90B7FCB8FC 94C7FC36397BB839>90 D<147E903803FF8090390FC1C38090391F00EFC0017E137F4913 3F485A4848EB1F8012075B000F143F48481400A2485A5D007F147E90C7FCA215FE485C5A A214015D48150CA21403EDF01C16181407007C1538007E010F1330003E131F027B13706C 01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F0026267DA42C>97 D<133FEA1FFFA3C67E137EA313FE5BA312015BA312035BA31207EBE0FCEBE3FF9038E707 C0390FFE03E09038F801F001F013F8EBE000485A15FC5BA2123F90C7FCA214015A127EA2 140312FE4814F8A2140715F05AEC0FE0A215C0EC1F80143F00781400007C137E5C383C01 F86C485A380F07C06CB4C7FCEA01FC1E3B7CB924>II<163FED1FFFA3ED007F167EA216 FEA216FCA21501A216F8A21503A216F0A21507A2027E13E0903803FF8790380FC1CF9038 1F00EF017EEB7FC049133F485A4848131F000715805B000F143F485A1600485A5D127F90 C7127EA215FE5A485CA21401A248ECF80CA21403161CEDF0181407007C1538007E010F13 30003E131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F00283B7DB9 2B>II<16F8ED03FEED0F8792381F0F80ED3E3F167F157CA215FC1700161C4A48 C7FCA414035DA414075DA20107B512F0A39026000FE0C7FC5DA4141F5DA4143F92C8FCA4 5C147EA514FE5CA413015CA4495AA45C1307A25C121E123F387F8F80A200FF90C9FC131E 12FEEA7C3CEA7878EA1FF0EA07C0294C7CBA29>I<14E0EB03F8A21307A314F0EB01C090 C7FCAB13F8EA03FEEA070F000E1380121C121812381230EA701F1260133F00E0130012C0 5BEA007EA213FE5B1201A25B12035BA20007131813E01438000F133013C01470EB806014 E014C01381EB838038078700EA03FEEA00F815397EB71D>105 D<150FED3F80A2157FA3 1600151C92C7FCABEC0F80EC3FE0ECF0F0903801C0F849487E14005B130E130C131CEB18 01133801305BA2EB0003A25DA21407A25DA2140FA25DA2141FA25DA2143FA292C7FCA25C A2147EA214FEA25CA21301001E5B123F387F83F0A238FF87E0495A00FE5BD87C1FC8FCEA 707EEA3FF8EA0FC0214981B722>III< D803E0017F14FE3D07F801FFE003FFC03D0E3C0781F00F03E03D1C3E1E00F83C01F02638 3F38D9FC707F00304914E04A90387DC000007049EB7F8000604991C7FCA200E090C700FE 1301485A017E5CA200000201140301FE5F495CA203031407000160495C180F03075D1203 494A011F13601980030F023F13E00007F000C0495C1901031F023E1380000F1803494A15 0061033F150E001FEF1E1C4991C7EA0FF80007C7000EEC03E043267EA449>II<14FF010313C090380F80F090383E00380178131C 153C4913FC0001130113E0A33903F000F06D13007F3801FFE014FC14FF6C14806D13C001 1F13E013039038003FF014071403001E1301127FA24814E0A348EB03C012F800E0EB0780 0070EB0F006C133E001E13F83807FFE0000190C7FC1E267CA427>115 D<903907E001F090391FF807FC9039783E0E0F9039E01F1C1FD801C09038383F803A0380 0FF07F0100EBE0FF5A000E4A1300000C157E021F133C001C4AC7FC1218A2C7123FA292C8 FCA25CA2147EA214FEA24A130CA20101141C001E1518003F5BD87F81143801835C00FF15 60010714E03AFE0E7C01C0D87C1C495A2778383E0FC7FC391FF00FFC3907C003F029267E A42F>120 D<1504151E151FA2ED0F8016C0ED07E0007FB612F0B712F8A26C15F0C8EA1F C0ED3F00157E5D5D5D1560251271BB2A>126 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmex10 10 10 /Fn 10 90 df<1430147014E0EB01C01303EB0780EB0F00A2131E5BA25B13F85B12015B 1203A2485AA3485AA3121F90C7FCA25AA3123EA2127EA6127C12FCB3A2127C127EA6123E A2123FA37EA27F120FA36C7EA36C7EA212017F12007F13787FA27F7FA2EB0780EB03C013 01EB00E0147014301462738226>0 D<12C07E12707E123C7E7EA26C7E6C7EA26C7E7F12 007F1378137CA27FA37FA31480130FA214C0A31307A214E0A6130314F0B3A214E01307A6 14C0A2130FA31480A2131F1400A3133EA35BA2137813F85B12015B485AA2485A48C7FCA2 121E5A12385A5A5A14627C8226>I56 D58 D60 D62 D80 DI88 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmsy7 7 19 /Fo 19 111 df0 D<1238127C12FEA3127C123807077A9114>I< 1338A50060130C00F8133E00FC137E00FE13FE383FBBF83807FFC000011300EA007C48B4 FC000713C0383FBBF838FE38FE00FC137E00F8133E0060130C00001300A517197B9A22> 3 D<49B512FE130F133F01FFC8FCEA01F8EA03E0EA078048C9FC121E121C123C12381278 1270A212F05AA77E1270A212781238123C121C121E7E6C7EEA03E0EA01F86CB4FC013FB5 12FE130F130190C9FCAB003FB612FE5A7E27357AA734>18 D<12E012F812FEEA3F80EA0F E0EA03F8EA00FEEB3F80EB0FE0EB03F8EB00FEEC3F80EC0FE0EC03F8EC00FEED3F80ED0F E0ED03F8ED00FE163E16FEED03F8ED0FE0ED3F80EDFE00EC03F8EC0FE0EC3F8002FEC7FC EB03F8EB0FE0EB3F8001FEC8FCEA03F8EA0FE0EA3F80007EC9FC12F812E0CAFCAB007FB6 12FCB712FEA227357AA734>21 D<176017F01770A217781738173C171C171E83717E717E 717EEF00F8BAFC19801900CB12F8EF01E04D5A4D5A4DC7FC171E171C173C173817781770 A217F01760391F7C9D42>33 D<017F157F2601FFE0903803FFC0000701F890380FF1F026 0F83FC90381F0038261E00FF013C7F001890263F8078130C4890261FC0E07F007090260F E1C07F0060EB07E3913803F780486DB4C7EA01806E5A157E157F81824B7E0060DAF7E0EB 0300913801E3F0DBC3F85B6C90260381FC13066C90260F00FE5B001C011E90387F803C6C 017C90381FE0F82607C7F86DB45A2601FFE0010313C06C6CC86CC7FC391B7C9942>49 D<49B5FC130F133F01FFC7FCEA01F8EA03E0EA078048C8FC121E121C123C123812781270 A212F05AA2B7FCA300E0C8FCA27E1270A212781238123C121C121E7E6C7EEA03E0EA01F8 6CB4FC013FB5FC130F130120277AA12D>I<387FFF80B512F06C13FCC7B4FCEC1F80EC07 C0EC01E0EC00F015781538153C151C151E150EA2150F1507A2B7FCA3C81207A2150F150E A2151E151C153C1538157815F0EC01E0EC07C0EC1F80ECFF00387FFFFCB512F06C138020 277AA12D>II<150EA2151E151C 153C1578157015F015E0140115C0140315801407EC0F00140E141E141C143C1438147814 7014F0495A5C13035C130791C7FC5B131E131C133C13381378137013F05B1201485A5B12 0790C8FC5A120E121E121C123C5A127012F05A12601F3576A800>54 D<140C141CA2143CEB3FB8EBFFF8EA03E03807807C380F007E001E13FF001C13E7003C14 80A2D87C0113C0007813C3A2130300F8EB83E0A213071403A2130F130EA3131E131CA213 3C1338A21378D8787013C0A2387CF00713E0003C1480A2001FEB0F0013C0000F131E0007 5B3803E0F8EBFFF03807BF8090C8FCA31B317DAC22>59 D<0207B612C0023F15E091B7FC 903A01E07C0007D90780EC03C090260F00781400011E01F890C7FC5B137C01785BEB7001 1300A25D1403A25D1407A292B512C05C5FDB0006C7FC4A90C8FCA2141E143E143C147C14 7814F85C13015CEA180300785BEAFC0700FE5BD8FF8FCAFCEA7FFEEA3FF8EA0FE0332A7E A730>70 D<027F143E49486C137F010715FF90260F1FC0133FD91E0F141F131C90260007 E0131E173C1778020314E0EE03C0EE0780EE1E00167CEDF0F0EDF3C0EDFF806E48C7FC15 F85D1407141FEC7DF8EB01F1EB03C1EB0F00133E1378EA01E0485A48C77E121E5A48147C 00F8EC7E075E6CEC7F1EB4EC3FFC4815F0007CEC1FC030287CA730>88 D<0060153000E01570B3A76C15F0007015E0007814016CEC03C0001FEC0F80D80FC0EB3F 003907F801FE0001B512F86C6C13E0010F90C7FC24247CA22D>91 DI<147EEB03FEEB0FE0EB1F0013 3E5BB35BA2485AEA07E0EAFF8000FCC7FCB47EEA07E0EA01F06C7EA2137CB37F7FEB0FE0 EB03FEEB007E173B7BAB22>102 D<12FCB47EEA0FE0EA01F06C7E137CB37FA27FEB0FC0 EB03FEEB007EEB03FEEB0FC0EB1F00133EA25BB35B485AEA0FE0EAFF8000FCC7FC173B7B AB22>I<12E0A27E1270A212781238123C121CA2121E120E120F7EA27F1203A27F12017F 1200A27F137013781338A2133C131C131E130EA2130F7F801303A2801301801300A28014 70A214781438143C141CA2141E140E140F80A2158014031401193B7CAB22>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fp cmmi7 7 21 /Fp 21 127 df<14C0A4ECFF8015C013039038073F80010EC7FC5B5B5B5B485A485A1207 90C8FC120E121EA25AA212381278A312F8A25A7EA47E127E127FEA3FC013F86CB47E0007 13E06C7FC66C7EEB0FFC1301EB007C143CA214381340EB7070EB3FE0EB0F801A347DA71E >16 D<16E00003140148EC03F0120E000C1401001C14005A003015701660481330147014 F04815C0A25C0101EB018014C015031600D8E0035B903807E00E39F01FF03E39FFFEFFFC 6C486C5AD83FF85B391FE03FE0390F800F80241B7E992A>33 D<1238127C12FE12FFA212 7F123B1203A31206A3120C121812381270122008127A8614>59 D64 D<4B7E1503150782150F151FA2153FA2156F15CF82EC018714 0315071406140E140C02187FA2EC30031460A214C013011480D903007F91B5FC5B90380C 0001A25B13380130805B01E013005B12011203000F4A7ED8FFF890381FFFE0A22B2A7DA9 32>I<013FB512F816FF903A01FC001FC04AEB07E0EE03F001031401A24A14F8A2130717 F04A130317E0010F1407EE0FC04AEB1F80EE7E00011F495A91B512F0A291388001FC013F EB007E8291C7EA1F80160F4915C0A2137EA213FEEE1F805BEE3F000001153E16FE49EB01 F84B5A0003EC1FC0B7C7FC15F82D287DA732>I<013FB612FCA2903901FC00014AEB007C 173C0103153817185CA21307A24A13C0A2010F010113005E14C01503011F130F91B5C7FC A2EC800F013F7F15061400A249010E13E0030C13C0017E90C7FC160101FEEC0380A249EC 0700A20001150E161E495C16FC0003EC07F8B7FC5E2E287DA731>69 D<903B3FFFF01FFFF8A2D901FCC7EAFE004A5CA2010314015F5CA2010714035F5CA2010F 14075F5CA2011F140F91B65AA2913880000F013F141F5F91C7FCA249143F94C7FC137EA2 01FE5C167E5BA2000115FE5E5BA200031401B539C07FFFE0A235287DA736>72 D78 D<91381FE0089138FFFC18903903E01E3890390780077090390E0003F049130149130001 7814E0137013F0A2000115C0A216007F7F6CB47E14F86DB47E6D13F06D7F01077F01007F 1407EC00FF153F81A3001880A20038141E12300038141C153C00781438007C5C007E5C00 77EB03C026E3E00FC7FC38C0FFFE38801FF0252A7CA829>83 D<000FB712E05A9039800F E007D81E009038C001C05A0038011F1300123000705C00601501023F148012E0481400A2 C74890C7FCA2147EA214FEA25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131F 001FB57EA22B287DA727>I98 D<15F8141FA2EC01F0A21403A215E0A21407A215C0A2140FEB1F8F90387FCF80EBF0EF38 03C03FEA0780390F001F00A2001E5B123E003C133E127C147E5A147CA214FC5AECF830A3 903801F060A2EA7803010E13C0393C1CF980381FF07F3907C01E001D297CA723>100 D<130E131F5BA2133E131C90C7FCA7EA03E0487EEA0C78EA187C1230A212605B12C0A2EA 01F0A3485AA2485AA2EBC180EA0F81A2381F0300A213066C5A131CEA07F06C5A11287DA6 17>105 D<1407EC0F80141FA21500140E91C7FCA7EB03E0EB07F8EB0C3C1318EB303E13 6013C0A248485AA2C7FCA25CA4495AA4495AA4495AA4495AA21238D87C1FC7FC12FC133E 485AEA70F8EA7FE0EA1F80193380A61B>I<133EEA07FEA2EA007CA213FCA25BA21201A2 5BA21203EC07809038E01FC0EC38600007EB61E014C3EBC187EBC307D80FC613C09038CC 038001B8C7FC13E0487E13FEEB3F80EB0FC0486C7E1303003E1460A2127EECC0C0127CEC C18012FC903801E30038F800FE0070137C1B297CA723>I<3907801FC0390FE07FF03918 F0E0F83930F1807CEBFB00D860FE133C5B5B00C1147C5B1201A248485BA34A5AEA07C016 60EC03E0A23A0F8007C0C0A2EDC180913803C300D81F0013C7EC01FE000EEB00F8231B7D 9929>110 D115 D119 D<90387C03C03901FF0FF03907 079C30390E03B078000CEBF0F8001813E1123015F0396007C0E015001200A2495AA449C7 FC15301238007C1460EAFC3E15C0EAF87E39F06F03803970C70700383F83FE381F01F81D 1B7D9926>I<1404140EA2140FEC0780B612C015E015C0C7EA0F80EC1E005C143814101B 0D74A922>126 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fq cmsy10 10 26 /Fq 26 111 df<007FB81280B912C0A26C17803204799641>0 D<121C127FEAFF80A5EA 7F00121C0909799917>I<0060150600F8150F6C151F007E153F6C157E6C6C14FC6C6CEB 01F86C6CEB03F06C6CEB07E06C6CEB0FC06C6CEB1F80017EEB3F006D137E6D6C5A90380F C1F8903807E3F0903803F7E06DB45A6D5B6EC7FCA24A7E497F903803F7E0903807E3F090 380FC1F890381F80FC90383F007E017E7F49EB1F804848EB0FC04848EB07E04848EB03F0 4848EB01F84848EB00FC48C8127E007E153F48151F48150F00601506282874A841>I15 D<007FB812F8B912FCA2 6C17F8CCFCAE007FB812F8B912FCA26C17F8CCFCAE007FB812F8B912FCA26C17F836287B A841>17 D20 D<126012F812FEEA7F80EA3FE0EA0FF8EA03FEC66C7EEB3FE0EB0FF8 EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0ED0FF8ED03FE923800FF80 EE3FE0EE0FF8EE03FE933800FF80EF3FC0171FEF7F80933801FF00EE07FCEE1FF0EE7FC0 4B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0 EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270CCFCAE007FB81280B912C0A26C 1780324479B441>I<020FB6128091B712C01303010F1680D91FF8C9FCEB7F8001FECAFC EA01F8485A485A485A5B48CBFCA2123EA25AA2127812F8A25AA87EA21278127CA27EA27E A26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF86DB71280010316C01300020F1580323279 AD41>26 D<007FB512FCB712C016F06C15FCC8EA07FE9238007F80EE1FC0EE07E0707E70 7E707E177C83A283A2EF0F80A2170718C0A21703A81707A21880170FA2EF1F00A2173EA2 5F17FC4C5A4C5A4C5AEE1FC0EE7F80DB07FEC7FC007FB65AB712F016C06C02FCC8FC3232 79AD41>I<181EA4181F84A285180785727EA2727E727E85197E85F11F80F10FC0F107F0 007FBA12FCBCFCA26C19FCCCEA07F0F10FC0F11F80F13F00197E61614E5A4E5AA24E5A61 180F96C7FCA260181EA4482C7BAA53>33 D49 D<91381FFFFE91B6FC1303010F14FED91FF0C7FCEB7F8001FEC8FCEA01F8485A48 5A485A5B48C9FCA2123EA25AA2127812F8A25AA2B712FE16FFA216FE00F0C9FCA27EA212 78127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF06DB512FE010314FF1300 021F13FE283279AD37>I54 D<126012F0AD12FCA412F0AD126006207BA400>I<0060161800F0163C6C167CA2007816 78007C16F8A2003C16F0003E1501A26CED03E0A26C16C06D1407A2000716806D140FA26C 6CEC1F00A26CB612FEA36C5D01F8C7127CA2017C5CA2013C5C013E1301A2011E5C011F13 03A26D6C485AA201075CECC00FA2010391C7FC6E5AA2903801F03EA20100133CECF87CA2 EC7878EC7CF8A2EC3FF0A26E5AA36E5AA36E5A6EC8FC2E3C80B92F>I<156015F0A21401 EB07F190383FFFE0EB7C1FEBF00748486C5AD803C07F4848487ED80F007FA248497E001E 14BC153C003E143E141FA248EB1E1F143EA2143CA2147C00FC1580147814F8A214F0A213 01A214E01303A214C0A21307A21480A2130FA214005B007C1500131EA2D87E3E5BA2D83E 3C133E137CA21378001F5C13F8000F14784913F800075C0003495AEBE0033901F0078026 03FC1FC7FCEBFFFEEBC7F0D807C0C8FCA25BA26CC9FC21477CBF2A>59 D<0307B612FE033FEDFF804AB812C0140791260F807EC7FC91263C00FEEC3F004A161E4A 491418010194C7FC495A01071301A2D90FC05B148014000118130390C75BA34B5AA3150F 5EA34B5AA293B512FC4B5C604B14C0037ECAFCA25DA25D1401A24A5AA25D14075D140F5D 141F92CBFC5C0006133E003E137E007E137CB413FC6D5AEBC1F0EBF1E06CB45A6C90CCFC 6C5AEA07F0423C7EB83C>70 D<0203B512F8027FECFF8049B712F0010F8290273FC3F003 13FED978039038003FFF2601E00702071380D803C06F13C0D807801500000F177FD81F00 EE3FE0484A141F123E5A0078010F150F12C0C7FC4B15C0A3021FED1F80A24B1500183EA2 023F5D6092C85A4D5A4D5A4A4A5A027E020EC7FC173C17F84AEB03E0EE3F80DB1FFEC8FC 0101EB7FF89138F8FFC0DAF9FCC9FC02F8CAFC495AA3495AA3495AA3495AA291CBFC5BA2 137EA35B13F013C03B3D7FB83A>80 D<1A801907F10F00023FB712FE49B85A010F17F001 3F17C0494CC7FC2801E00003F0C9FC48481307485A120F48C7485A5A5AA200FE4A5A5A12 F01280C8485AA44BCAFCA415FEA44A5AA44A5AA44A5AA4140F5DA35D141FA25D143FA292 CBFC5CA2147E14FE5CA2495A5C495A5C0102CCFC41427DBB2D>84 D<03FF15F802076DEB01FC4A6D1307023F150FDA7C7F14034A6C6C1301903801F01F02C0 16F890C7FC030F15F0F003E07014C0F00780F00F00181C0307147860EF03C04D5A051EC7 FC5F17F0EEF9E0EEFF8094C8FC16FC6F5AA21507151F153F15F3EC03E3EC078391381E03 FC143C14F0EB01E09038078001EB0F00133C5B13E0EA03C048488048C7FC5A123E007E14 007013E000FE1603EF87C06CEECF8001C06EB4C7FC4915FC90C86C5A007CED1FC03E397C B83B>88 D92 D102 D<12FCEAFFC0EA07F0EA01FCEA007E7F80131F80130FB3A7801307806D7E6D7EEB007EEC 1FF0EC07F8EC1FF0EC7E00495A495A495A5C130F5CB3A7131F5C133F91C7FC137E485AEA 07F0EAFFC000FCC8FC1D537ABD2A>I<126012F0B3B3B3B3A91260045377BD17>106 D<0070131C00F0131EB3B3B3B3A80070131C175277BD2A>I<126012F07EA21278127CA2 123C123EA2121E121FA27E7FA212077FA212037FA212017FA212007FA21378137CA2133C 133EA2131E131FA27F80A2130780A26D7EA2130180A2130080A21478147CA2143C143EA2 141E141FA2801580A2140715C0A2140315E0A2140115F0A2140015F8A21578157CA2153C 153EA2151E150C1F537BBD2A>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fr cmbx12 12 39 /Fr 39 119 df49 DII<163FA25E5E 5D5DA25D5D5D5DA25D92B5FCEC01F7EC03E7140715C7EC0F87EC1F07143E147E147C14F8 EB01F0EB03E0130714C0EB0F80EB1F00133E5BA25B485A485A485A120F5B48C7FC123E5A 12FCB91280A5C8000F90C7FCAC027FB61280A531417DC038>I<0007150301E0143F01FF EB07FF91B6FC5E5E5E5E5E16804BC7FC5D15E092C8FC01C0C9FCAAEC3FF001C1B5FC01C7 14C001DF14F09039FFE03FFC9138000FFE01FC6D7E01F06D13804915C0497F6C4815E0C8 FC6F13F0A317F8A4EA0F80EA3FE0487E12FF7FA317F05B5D6C4815E05B007EC74813C012 3E003F4A1380D81FC0491300D80FF0495AD807FEEBFFFC6CB612F0C65D013F1480010F01 FCC7FC010113C02D427BC038>I<4AB47E021F13F0027F13FC49B6FC01079038807F8090 390FFC001FD93FF014C04948137F4948EBFFE048495A5A1400485A120FA248486D13C0EE 7F80EE1E00003F92C7FCA25B127FA2EC07FC91381FFF8000FF017F13E091B512F89039F9 F01FFC9039FBC007FE9039FF8003FF17804A6C13C05B6F13E0A24915F0A317F85BA4127F A5123FA217F07F121FA2000F4A13E0A26C6C15C06D4913806C018014006C6D485A6C9038 E01FFC6DB55A011F5C010714C0010191C7FC9038003FF02D427BC038>I65 DII71 D73 D76 DI<923807FFC092B512FE0207ECFFC0021F15F091267FFE0013FC 902601FFF0EB1FFF01070180010313C04990C76C7FD91FFC6E6C7E49486F7E49486F7E01 FF8348496F7E48496F1380A248496F13C0A24890C96C13E0A24819F04982003F19F8A300 7F19FC49177FA400FF19FEAD007F19FC6D17FFA3003F19F8A26D5E6C19F0A26E5D6C19E0 A26C6D4B13C06C19806E5D6C6D4B13006C6D4B5A6D6C4B5A6D6C4B5A6D6C4A5B6D01C001 075B6D01F0011F5B010101FE90B5C7FC6D90B65A023F15F8020715C002004AC8FC030713 C047467AC454>79 DI82 DI85 D87 D<903801FFE0011F13FE017F6D7E 48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7EA26F7FA36F7F6C5A6C5AEA00F090 C7FCA40203B5FC91B6FC1307013F13F19038FFFC01000313E0000F1380381FFE00485A5B 127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013EEBFFC03A1FFF80FC7F0007EBFFF8 6CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 DIIIIIII<137C48B4FC4813804813C0A24813E0A56C13 C0A26C13806C1300EA007C90C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA518467CC520> I107 DI<90277F8007FEEC0FFCB590 263FFFC090387FFF8092B5D8F001B512E002816E4880913D87F01FFC0FE03FF8913D8FC0 0FFE1F801FFC0003D99F009026FF3E007F6C019E6D013C130F02BC5D02F86D496D7EA24A 5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7CAC5E>I<90397F8007FEB590383FFF 8092B512E0028114F8913987F03FFC91388F801F000390399F000FFE6C139E14BC02F86D 7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E>II113 D<90387F807FB53881FFE0028313F0028F13F8ED8FFC91389F1FFE000313BE 6C13BC14F8A214F0ED0FFC9138E007F8ED01E092C7FCA35CB3A5B612E0A5272D7DAC2E> I<90391FFC038090B51287000314FF120F381FF003383FC00049133F48C7121F127E00FE 140FA215077EA27F01E090C7FC13FE387FFFF014FF6C14C015F06C14FC6C800003806C15 806C7E010F14C0EB003F020313E0140000F0143FA26C141F150FA27EA26C15C06C141FA2 6DEB3F8001E0EB7F009038F803FE90B55A00FC5CD8F03F13E026E007FEC7FC232F7CAD2C >IIII E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fs cmr10 10 83 /Fs 83 127 df0 D<15E0A34A7EA34A7EA34A7EA3 4A7EA2140DEC1DFF14191418A24A7F157FA202607F153FA202C07F151FA2D901807F150F A2D903007F1507A20106801503A2010E80130C1501011C80131881A24981167FA2498116 3FA24981161FA20001821203486C81D81FF84A7EB50107B512E0A3333C7DBB3A>3 D<011FB512FEA39026001FFEC8FCEC07F8A8EC3FFE0103B512E0D91FF713FC90397F07F8 7F01FCEC1F80D803F8EC0FE0D807F06E7ED80FE06E7E001F82D83FC06E7EA2007F820180 8000FF1780A7007F170001C05C003F5EA2D81FE04A5A000F5ED807F04A5AD803F84A5AD8 00FCEC1F80017F027FC7FC90391FF7FFFC0103B512E09026003FFEC8FCEC07F8A8EC1FFE 011FB512FEA331397BB83C>8 D10 DIIII<001C13 1C007F137F39FF80FF80A26D13C0A3007F137F001C131C00001300A40001130101801380 A20003130301001300485B00061306000E130E485B485B485B006013601A197DB92A>34 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485A A212075B120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F1207 7F1203A26C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>I<12 C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7FA214 80A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A25BA2 485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<15301578B3A6007FB812F8B9 12FCA26C17F8C80078C8FCB3A6153036367BAF41>43 D<121C127FEAFF80A213C0A3127F 121C1200A412011380A2120313005A1206120E5A5A5A12600A19798817>II<121C127FEAFF80A5EA7F00121C0909798817>I48 DIII<1538A2157815F8A2140114031407A2140F 141F141B14331473146314C313011483EB030313071306130C131C131813301370136013 C01201EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800AB4A7E0103B5 12F8A325397EB82A>I<0006140CD80780133C9038F003F890B5FC5D5D158092C7FC14FC 38067FE090C9FCABEB07F8EB3FFE9038780F803907E007E090388003F0496C7E12066E7E C87EA28181A21680A4123E127F487EA490C71300485C12E000605C12700030495A00385C 6C1303001E495A6C6C485A3907E03F800001B5C7FC38007FFCEB1FE0213A7CB72A>II<12301238123E003FB612E0A316C05A168016000070C7 12060060140E5D151800E01438485C5D5DC712014A5A92C7FC5C140E140C141C5CA25CA2 14F0495AA21303A25C1307A2130FA3495AA3133FA5137FA96DC8FC131E233B7BB82A>I< EB03F8EB1FFF017F13C09038FC07F03901E001F848486C7E4848137C90C77E48141E000E 141F001E80A3121FA27F5D01E0131E6C6C133E01FC133C6D5B6C6C6C5AECC1E06CEBF3C0 6C01FFC7FC6C5BEB3FFF6D13C081017F13F801F07F3903E07FFE3907801FFF48486C1380 481303003E6D13C0003CEB007F007C143F0078EC0FE000F814075A1503A21501A36C15C0 12781503007C15806CEC07006C5C6C6C131ED807E0137C3903F803F0C6B55A013F1380D9 07FCC7FC233A7DB72A>II<121C127FEAFF80A5EA7F00121C C7FCB2121C127FEAFF80A5EA7F00121C092479A317>I<121C127FEAFF80A5EA7F00121C C7FCB2121C127F5A1380A4127F121D1201A412031300A25A1206A2120E5A121812385A12 60093479A317>I<007FB812F8B912FCA26C17F8CCFCAE007FB812F8B912FCA26C17F836 167B9F41>61 D63 DI<1538A3157CA315FEA34A7EA34A6C7EA202077FEC063FA202 0E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202C07F1501A2D90180 7F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7EA3496E7EA3496E7E A213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>II<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03FC000F0FD90F F0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F4848150FA24848 1507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A3123F7F001F1603 18006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE05C6D6CEB03C0 D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D7BBA3C>IIIIIII<013FB512E0 A39039001FFC00EC07F8B3B3A3123FEA7F80EAFFC0A44A5A1380D87F005B0070131F6C5C 6C495A6C49C7FC380781FC3801FFF038007F80233B7DB82B>IIIIIII82 DI<003FB812E0A3D9C003EB001F273E0001FE130348EE01F00078160000701770A3006017 30A400E01738481718A4C71600B3B0913807FF80011FB612E0A335397DB83C>II87 D89 D91 D<3901800180000313033907000700000E130E485B0018 131800381338003013300070137000601360A200E013E0485BA400CE13CE39FF80FF806D 13C0A3007F137FA2393F803F80390E000E001A1974B92A>II97 DIIII<147E903803 FF8090380FC1E0EB1F8790383F0FF0137EA213FCA23901F803C091C7FCADB512FCA3D801 F8C7FCB3AB487E387FFFF8A31C3B7FBA19>IIIIIII<2703F00FF0EB1FE000FFD9 3FFCEB7FF8913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013CE01 FE14DC49D907F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA34025 7EA445>I<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE 496D7EA25BA35BB3A3486C497EB500C1B51280A329257EA42E>II<39 03F01FE000FFEB7FF89038F1E07E9039F3801F803A0FF7000FC0D803FEEB07E049EB03F0 4914F849130116FC150016FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE0 01F614C09039F7803F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357E A42E>II<3807E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038 EC03E09038FC0080491300A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A313F812 0112031207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5A EB0FFEEB01F81A347FB220>IIIII< B538803FFEA33A0FF8000FF06C48EB07C00003EC03806C7E16007F00001406A2017E5BA2 137F6D5BA26D6C5AA2ECC070010F1360A26D6C5AA214F101035BA2D901FBC7FCA214FF6D 5AA2147CA31438A21430A214701460A25CA2EA7C0100FE5B130391C8FC1306EAFC0EEA70 1C6C5AEA1FF0EA0FC027357EA32C>I<003FB512FCA2EB8003D83E0013F8003CEB07F000 38EB0FE012300070EB1FC0EC3F800060137F150014FE495AA2C6485A495AA2495A495A49 5AA290387F000613FEA2485A485A0007140E5B4848130C4848131CA24848133C48C7127C 48EB03FC90B5FCA21F247EA325>I126 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ft cmbx10 10 49 /Ft 49 123 df<913803FFC0027F13F00103B512FC010FEB00FED93FF8133FD97FE0EBFF 8049485A5A1480484A13C04A6C1380A36F1300167E93C7FCA592383FFFC0B8FCA4000390 C7FCB3ABB5D8FC3F13FFA4303A7EB935>12 D39 D44 D46 D<141E143E14FE1307133FB5FCA313CFEA000FB3B3A6007FB61280A4213779B630>49 DIII<001C15C0D81F80 130701F8137F90B61280A216005D5D15F05D15804AC7FC14F090C9FCA8EB07FE90383FFF E090B512F89038FC07FC9038E003FFD98001138090C713C0120EC813E0157F16F0A216F8 A21206EA3F80EA7FE012FF7FA44914F0A26C4813FF90C713E0007C15C06C5B6C491380D9 C0071300390FF01FFE6CB512F8000114E06C6C1380D90FF8C7FC25387BB630>II<123C123EEA3FE090B71280A41700485D5E5E 5EA25E007CC7EA0FC000784A5A4BC7FC00F8147E48147C15FC4A5A4A5AC7485A5D140F4A 5A143F92C8FC5C147E14FE1301A2495AA31307A2130F5CA2131FA5133FA96D5A6D5A6D5A 293A7BB830>I58 D65 DIII70 DI73 D<010FB612C0A4D90001EBE000B3B3EA0F80EA3FE0EA7F F0A2EAFFF8A35E5C13F0007F495BD83FE091C7FC391F800FFE390FF03FFC6CB512F00001 14C026003FFCC8FC2A3A7FB831>I76 DI80 D82 DI<003FB91280A4D9F800EBF003D87FC09238007FC049 161F007EC7150FA2007C1707A200781703A400F818E0481701A4C892C7FCB3AE010FB7FC A43B387DB742>I97 D<13FFB5FCA412077EAF4AB47E020F13F0023F13FC91 38FE03FFDAF00013804AEB7FC00280EB3FE091C713F0EE1FF8A217FC160FA217FEAA17FC A3EE1FF8A217F06E133F6EEB7FE06E14C0903AFDF001FF80903AF8FC07FE009039F03FFF F8D9E00F13E0D9C00390C7FC2F3A7EB935>I<903801FFC0010F13FC017F13FFD9FF8013 802603FE0013C048485AEA0FF8121F13F0123F6E13804848EB7F00151C92C7FC12FFA912 7FA27F123FED01E06C7E15036C6CEB07C06C6C14806C6C131FC69038C07E006DB45A010F 13F00101138023257DA42A>II<903803FF80011F13F0017F13FC3901FF83FE3A03FE007F804848133F 484814C0001FEC1FE05B003FEC0FF0A2485A16F8150712FFA290B6FCA301E0C8FCA4127F A36C7E1678121F6C6C14F86D14F000071403D801FFEB0FE06C9038C07FC06DB51200010F 13FC010113E025257DA42C>II<161FD907FEEBFFC090387FFFE348B6EAEFE02607FE07138F260FF8 01131F48486C138F003F15CF4990387FC7C0EEC000007F81A6003F5DA26D13FF001F5D6C 6C4890C7FC3907FE07FE48B512F86D13E0261E07FEC8FC90CAFCA2123E123F7F6C7E90B5 12F8EDFF8016E06C15F86C816C815A001F81393FC0000F48C8138048157F5A163FA36C15 7F6C16006D5C6C6C495AD81FF0EB07FCD807FEEB3FF00001B612C06C6C91C7FC010713F0 2B377DA530>I<13FFB5FCA412077EAFED7FC0913803FFF8020F13FE91381F03FFDA3C01 138014784A7E4A14C05CA25CA291C7FCB3A3B5D8FC3F13FFA4303A7DB935>II<13FFB5FCA412077EAF92380FFFE0A4923803FC0016F0ED0FE0ED1F804BC7FC15 7E5DEC03F8EC07E04A5A141FEC7FE04A7E8181A2ECCFFEEC0FFF496C7F806E7F6E7F8215 7F6F7E6F7E82150F82B5D8F83F13F8A42D3A7EB932>107 D<13FFB5FCA412077EB3B3AC B512FCA4163A7DB91B>I<01FED97FE0EB0FFC00FF902601FFFC90383FFF80020701FF90 B512E0DA1F81903983F03FF0DA3C00903887801F000749DACF007F00034914DE6D48D97F FC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB50083B512F0A44C257DA451>I<01FEEB7F C000FF903803FFF8020F13FE91381F03FFDA3C011380000713780003497E6D4814C05CA2 5CA291C7FCB3A3B5D8FC3F13FFA430257DA435>I<903801FFC0010F13F8017F13FFD9FF 807F3A03FE003FE048486D7E48486D7E48486D7EA2003F81491303007F81A300FF1680A9 007F1600A3003F5D6D1307001F5DA26C6C495A6C6C495A6C6C495A6C6C6CB45A6C6CB5C7 FC011F13FC010113C029257DA430>I<9039FF01FF80B5000F13F0023F13FC9138FE07FF DAF00113800007496C13C06C0180EB7FE091C713F0EE3FF8A2EE1FFCA3EE0FFEAA17FC16 1FA217F8163F17F06E137F6E14E06EEBFFC0DAF00313809139FC07FE0091383FFFF8020F 13E0020390C7FC91C9FCACB512FCA42F357EA435>I<9038FE03F000FFEB0FFEEC3FFF91 387C7F809138F8FFC000075B6C6C5A5CA29138807F80ED3F00150C92C7FC91C8FCB3A2B5 12FEA422257EA427>114 D<90383FF0383903FFFEF8000F13FF381FC00F383F0003007E 1301007C130012FC15787E7E6D130013FCEBFFE06C13FCECFF806C14C06C14F06C14F812 03C614FC131F9038007FFE140700F0130114007E157E7E157C6C14FC6C14F8EB80019038 F007F090B512C000F8140038E01FF81F257DA426>I<130FA55BA45BA25B5BA25A120700 1FEBFFE0B6FCA3000390C7FCB21578A815F86CEB80F014816CEBC3E090383FFFC06D1380 903803FE001D357EB425>I<01FFEC3FC0B5EB3FFFA4000714016C80B3A35DA25DA26C5C 6E4813E06CD9C03E13FF90387FFFFC011F13F00103138030257DA435>III121 D<003FB612C0A3D9F0031380EB800749481300003E5C00 3C495A007C133F5D0078495A14FF5D495B5BC6485B92C7FC495A131F5C495A017FEB03C0 EBFFF014E04813C05AEC80074813005A49EB0F80485A003F141F4848133F9038F001FFB7 FCA322257DA42A>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fu cmbx12 14.4 21 /Fu 21 122 df66 D<932601FFFCEC01C0047FD9FFC013030307B600F81307033F03FE131F92B8EA803F0203 DAE003EBC07F020F01FCC7383FF0FF023F01E0EC0FF94A01800203B5FC494848C9FC4901 F8824949824949824949824949824990CA7E494883A2484983485B1B7F485B481A3FA248 49181FA3485B1B0FA25AA298C8FC5CA2B5FCAE6C057FB712E0A280A36C94C7003FEBC000 A36C7FA36C7FA27E6C7FA26C7F6C7FA26D7E6D7F6D7F6D6D5E6D7F6D01FC93B5FC6D13FF 6D6C6D5C6E01F0EC07FB020F01FEEC1FF10203903AFFF001FFE0020091B6EAC07F033FEE 001F030703FC1307DB007F02E01301040149CAFC5B5479D26A>71 D76 DI80 D97 DI<4DB47E0407B5FCA5EE001F17 07B3A4913801FFE0021F13FC91B6FC010315C7010F9038E03FE74990380007F7D97FFC01 01B5FC49487F4849143F484980485B83485B5A91C8FC5AA3485AA412FFAC127FA36C7EA3 7EA26C7F5F6C6D5C7E6C6D5C6C6D49B5FC6D6C4914E0D93FFED90FEFEBFF80903A0FFFC0 7FCF6D90B5128F0101ECFE0FD9003F13F8020301C049C7FC41547CD24B>100 D<913803FFC0023F13FC49B6FC010715C04901817F903A3FFC007FF849486D7E49486D7E 4849130F48496D7E48178048497F18C0488191C7FC4817E0A248815B18F0A212FFA490B8 FCA318E049CAFCA6127FA27F7EA218E06CEE01F06E14037E6C6DEC07E0A26C6DEC0FC06C 6D141F6C6DEC3F806D6CECFF00D91FFEEB03FE903A0FFFC03FF8010390B55A010015C002 1F49C7FC020113F034387CB63D>III<137F497E000313E0487FA2487FA76C5BA26C5BC613806DC7FC90C8FCADEB3F F0B5FCA512017EB3B3A6B612E0A51B547BD325>105 D108 D110 D<913801FFE0021F13FE91B612C0010315 F0010F9038807FFC903A1FFC000FFED97FF86D6C7E49486D7F48496D7F48496D7F4A147F 48834890C86C7EA24883A248486F7EA3007F1880A400FF18C0AC007F1880A3003F18006D 5DA26C5FA26C5F6E147F6C5F6C6D4A5A6C6D495B6C6D495B6D6C495BD93FFE011F90C7FC 903A0FFF807FFC6D90B55A010015C0023F91C8FC020113E03A387CB643>I<903A3FF001 FFE0B5010F13FE033FEBFFC092B612F002F301017F913AF7F8007FFE0003D9FFE0EB1FFF C602806D7F92C76C7F4A824A6E7F4A6E7FA2717FA285187F85A4721380AC1A0060A36118 FFA2615F616E4A5BA26E4A5B6E4A5B6F495B6F4990C7FC03F0EBFFFC9126FBFE075B02F8 B612E06F1480031F01FCC8FC030313C092CBFCB1B612F8A5414D7BB54B>I<90397FE003 FEB590380FFF80033F13E04B13F09238FE1FF89139E1F83FFC0003D9E3E013FEC6ECC07F ECE78014EF150014EE02FEEB3FFC5CEE1FF8EE0FF04A90C7FCA55CB3AAB612FCA52F367C B537>114 D<903903FFF00F013FEBFE1F90B7FC120348EB003FD80FF81307D81FE01301 48487F4980127F90C87EA24881A27FA27F01F091C7FC13FCEBFFC06C13FF15F86C14FF16 C06C15F06C816C816C81C681013F1580010F15C01300020714E0EC003F030713F0150100 78EC007F00F8153F161F7E160FA27E17E07E6D141F17C07F6DEC3F8001F8EC7F0001FEEB 01FE9039FFC00FFC6DB55AD8FC1F14E0D8F807148048C601F8C7FC2C387CB635>I<143E A6147EA414FEA21301A313031307A2130F131F133F13FF5A000F90B6FCB8FCA426003FFE C8FCB3A9EE07C0AB011FEC0F8080A26DEC1F0015806DEBC03E6DEBF0FC6DEBFFF86D6C5B 021F5B020313802A4D7ECB34>II121 D E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop 30 33 4050 34 v 680 266 a Fu(Lo)t(op)l(y)45 b(Belief)h (Propagation)g(and)f(Gibbs)f(Measures)p 30 448 4050 9 v 749 797 a Ft(Sekhar)33 b(C.)e(T)-8 b(atik)m(onda)358 897 y Fs(Electrical)26 b(Engineering)g(and)h(Computer)h(Science)573 996 y(Univ)n(ersit)n(y)f(of)h(California,)e(Berk)n(eley)813 1096 y(Berk)n(eley)-7 b(,)26 b(CA,)i(94720)690 1196 y(tatik)n (ond@eecs.b)r(erk)n(eley)-7 b(.edu)2559 797 y Ft(Mic)m(hael)32 b(I.)f(Jordan)2341 897 y Fs(Computer)d(Science)f(and)h(Statistics)2323 996 y(Univ)n(ersit)n(y)f(of)h(California,)e(Berk)n(eley)2574 1096 y(Berk)n(eley)-7 b(,)26 b(CA)i(94720)2512 1196 y(jordan@cs.b)r (erk)n(eley)-7 b(.edu)791 1508 y Fr(Abstract)196 1749 y Fs(W)g(e)19 b(address)f(the)h(question)g(of)g(con)n(v)n(ergence)d(in) k(the)196 1848 y(lo)r(op)n(y)46 b(b)r(elief)i(propagation)d(\(LBP\))i (algorithm.)196 1948 y(Sp)r(eci\014cally)-7 b(,)27 b(w)n(e)f(relate)f (con)n(v)n(ergence)f(of)j(LBP)e(to)196 2048 y(the)d(existence)f(of)g(a) h(w)n(eak)e(limit)i(for)f(a)g(sequence)g(of)196 2147 y(Gibbs)26 b(measures)e(de\014ned)i(on)f(the)h(LBP's)e(asso)r(ci-)196 2247 y(ated)k(computation)g(tree.)38 b(Using)28 b(to)r(ols)g(from)g (the)196 2347 y(theory)34 b(of)h(Gibbs)f(measures)g(w)n(e)g(dev)n(elop) g(easily)196 2446 y(testable)23 b(su\016cien)n(t)g(conditions)f(for)g (con)n(v)n(ergence.)196 2546 y(The)f(failure)f(of)g(con)n(v)n(ergence)f (of)h(LBP)g(implies)h(the)196 2645 y(existence)39 b(of)h(m)n(ultiple)g (phases)f(for)g(the)h(asso)r(ci-)196 2745 y(ated)33 b(Gibbs)h(sp)r (eci\014cation.)53 b(These)33 b(results)g(giv)n(e)196 2845 y(new)j(insigh)n(t)g(in)n(to)f(the)h(mec)n(hanics)g(of)f(the)i (algo-)196 2944 y(rithm.)30 3255 y Fr(1)112 b(In)m(tro)s(duction)30 3458 y Fs(The)58 b(lo)r(op)n(y)e(b)r(elief)i(propagation)e(\(LBP\))h (algorithm)f(is)30 3557 y(an)44 b(algorithm)e(dev)n(elop)r(ed)i(for)f (computing)h(appro)n(ximate)30 3657 y(marginal)24 b(statistics)h(o)n(v) n(er)f(graphs)g(with)i(cycles.)35 b(This)26 b(algo-)30 3757 y(rithm)j(has)f(had)g(notable)h(success,)f(esp)r(ecially)g(for)g (iterativ)n(e)30 3856 y(c)n(hannel)19 b(deco)r(ding)h(of)g(turb)r(o)f (co)r(des)h(and)f(lo)n(w)g(densit)n(y)h(parit)n(y)30 3956 y(c)n(hec)n(k)29 b(co)r(des.)43 b(Ho)n(w)n(ev)n(er,)29 b(the)h(b)r(eha)n(vior)f(of)h(LBP)f(is)h(p)r(o)r(orly)30 4056 y(understo)r(o)r(d.)61 b(In)35 b(particular,)i(it)f(is)f(not)h (alw)n(a)n(ys)e(kno)n(wn)h(if)30 4155 y(this)28 b(algorithm)e(will)i (con)n(v)n(erge.)30 4305 y(Man)n(y)19 b(new)h(metho)r(ds)h(that)f (generalize)e(the)j(basic)e(algorithm)30 4404 y(ha)n(v)n(e)29 b(b)r(een)i(dev)n(elop)r(ed.)44 b(Some)30 b(of)g(these)g(metho)r(ds)h (include)30 4504 y(Kikuc)n(hi)37 b(based)f(metho)r(ds)h([6],)j(the)d (tree)g(reparameteriza-)30 4604 y(tion)44 b(tec)n(hnique)g([4],)k(and) 43 b(the)i(double-lo)r(op)e(sc)n(heme)g([7].)30 4703 y(Also)22 b(it)h(has)f(b)r(een)h(sho)n(wn)f(that)h(the)g(LBP)f (algorithm)f(can)i(b)r(e)30 4803 y(view)n(ed)k(an)h(iterativ)n(e)e (descen)n(t)i(do)n(wn)f(an)h(asso)r(ciated)e(Bethe)30 4902 y(free)h(energy)-7 b(.)36 b([6])30 5052 y(These)k(adv)-5 b(ances)39 b(not)n(withstanding,)k(a)d(complete)h(under-)30 5151 y(standing)29 b(of)h(the)g(con)n(v)n(ergence)e(prop)r(erties)h(of) g(the)i(original)30 5251 y(LBP)f(algorithm)g(is)g(still)h(lac)n(king.) 46 b(This)30 b(pap)r(er)h(presen)n(ts)e(a)30 5351 y(new)k(framew)n(ork) e(for)h(analyzing)g(the)h(LBP)f(algorithm.)52 b(In)30 5450 y(particular)19 b(w)n(e)i(use)f(to)r(ols)h(dev)n(elop)r(ed)f(in)h (the)g(study)g(of)g(Gibbs)30 5550 y(measures)g(to)h(analyze)f(the)h (question)g(of)g(con)n(v)n(ergence)d(in)k(the)2130 1508 y(LBP)33 b(algorithm.)55 b(This)34 b(analysis)f(giv)n(es)g(new)h (insigh)n(t)f(in)n(to)2130 1608 y(the)28 b(mec)n(hanics)f(of)g(LBP)-7 b(.)2130 1757 y(Our)25 b(analysis)f(relies)h(on)g(the)h(computation)f (tree.)36 b(This)25 b(tree)2130 1857 y(represen)n(ts)17 b(an)i(un)n(wrapping)f(of)g(the)i(original)d(graph)h(with)h(re-)2130 1956 y(sp)r(ect)30 b(to)g(the)g(LBP)f(algorithm.)42 b([5])30 b(The)g(initializing)f(mes-)2130 2056 y(sages)k(can)h(b)r(e)i(represen) n(ted)d(b)n(y)h(p)r(oten)n(tials)h(placed)f(at)h(the)2130 2156 y(lea)n(v)n(es)22 b(of)h(the)h(computation)f(tree.)36 b(W)-7 b(e)23 b(can)h(then)g(construct)2130 2255 y(a)33 b(sequence)g(of)g(Gibbs)h(measures)e(de\014ned)i(on)f(the)h(in\014nite) 2130 2355 y(computation)19 b(tree.)34 b(If)20 b(this)g(sequence)g(con)n (v)n(erges)d(then)j(LBP)2130 2454 y(con)n(v)n(erges.)34 b(Our)27 b(con)n(tributions)g(are)g(as)f(follo)n(ws:)2213 2679 y Fq(\017)41 b Fs(First,)25 b(w)n(e)g(relate)f(LBP)g(con)n(v)n (ergence)e(to)j(the)g(existence)2296 2779 y(of)32 b(a)f(w)n(eak)g (limit)i(for)e(the)h(sequence)g(of)g(measures)e(de-)2296 2879 y(\014ned)e(on)f(the)h(corresp)r(onding)e(computation)h(tree.)2213 3063 y Fq(\017)41 b Fs(Second,)31 b(w)n(e)f(relate)g(the)h(set)f(of)h (all)f(LBP)g(\014xed)g(p)r(oin)n(ts)2296 3163 y(to)24 b(the)g(set)g(of)g(all)f(Mark)n(o)n(v)f(c)n(hains)h(de\014ned)i(on)e (the)h(cor-)2296 3262 y(resp)r(onding)j(computation)g(tree.)2213 3447 y Fq(\017)41 b Fs(Third,)25 b(w)n(e)f(sho)n(w)f(that)h(LBP)g(alw)n (a)n(ys)e(con)n(v)n(erges)f(in)k(the)2296 3546 y(case)19 b(when)g(there)g(is)g(a)g(unique)h(Gibbs)f(measure)g(de\014ned)2296 3646 y(on)k(the)h(computation)f(tree.)35 b(\(Con)n(v)n(ersely)22 b(if)i(LBP)e(fails)2296 3746 y(to)37 b(con)n(v)n(erge)e(then)j(there)f (exist)h(m)n(ultiple)g(phases)e(on)2296 3845 y(the)28 b(computation)f(tree.\))2213 4029 y Fq(\017)41 b Fs(Finally)-7 b(,)46 b(w)n(e)c(pro)n(vide)g(an)g(easily)g(testable)g(su\016cien)n(t) 2296 4129 y(condition)36 b(to)f(insure)g(con)n(v)n(ergence)f(of)h(LBP) -7 b(.)35 b(In)h(par-)2296 4229 y(ticular)27 b(if)2697 4421 y(max)2715 4474 y Fp(s)p Fo(2)p Fp(S)2869 4342 y Fn(X)2866 4520 y Fp(A)p Fo(3)p Fp(s)2992 4421 y Fs(\()p Fq(j)p Fm(A)p Fq(j)19 b(\000)f Fs(1\))p Fm(\016)s Fs(\(\010)3440 4433 y Fp(A)3494 4421 y Fs(\))23 b Fm(<)g Fs(2)2296 4695 y(then)c(LBP)f(will)g(con)n(v)n(erge.)32 b(\(Where)19 b Fm(\016)s Fs(\(\010\))g(is)f(a)g(measure)2296 4795 y(of)38 b(the)g(strength)f(of)g(the)h(p)r(oten)n(tial)g(\010)g(and)f (the)h(sum)2296 4832 y Fn(P)2384 4919 y Fp(A)p Fo(3)p Fp(s)2551 4894 y Fs(is)g(o)n(v)n(er)d(all)i(the)h(neigh)n(b)r(ors)e(of) h(no)r(de)h Fm(s)p Fs(.)66 b(The)2296 4994 y(notation)27 b(is)h(de\014ned)g(in)f(the)h(sequel.\))2130 5241 y Fr(2)112 b(Bac)m(kground)34 b(and)h(the)e(LBP)g(Algorithm)2130 5450 y Fs(In)k(this)g(section)g(w)n(e)f(review)g(\014nite)i(Gibbs)f (measures,)h(the)2130 5550 y(LBP)27 b(algorithm,)f(and)i(the)g(asso)r (ciated)e(computation)h(tree.)p eop %%Page: 2 2 2 1 bop 30 83 a Ft(2.1)94 b(Finite)31 b(Gibbs)g(Measures)30 261 y Fs(Let)j Fm(S)k Fs(b)r(e)33 b(a)g(\014nite)h(set)g(of)f(no)r (des.)54 b(Asso)r(ciated)33 b(with)h(eac)n(h)30 361 y(no)r(de)41 b Fm(i)j Fq(2)h Fm(S)h Fs(there)40 b(is)h(a)f(measure)g(space)g(\()p Fq(X)1581 373 y Fp(i)1609 361 y Fm(;)14 b Fq(F)1706 373 y Fp(i)1733 361 y Fs(\).)77 b(W)-7 b(e)30 460 y(assume)27 b(that)h(all)f(the)h Fq(X)814 472 y Fp(i)870 460 y Fs(are)e(\014nite.) 30 610 y(Let)543 709 y(\(\012)p Fm(;)14 b Fq(F)8 b Fs(\))826 685 y Fo(4)824 736 y Fs(=)939 709 y(\()974 631 y Fn(Y)971 809 y Fp(i)p Fo(2)p Fp(S)1097 709 y Fq(X)1156 721 y Fp(i)1184 709 y Fm(;)1224 631 y Fn(Y)1221 809 y Fp(i)p Fo(2)p Fp(S)1347 709 y Fq(F)1407 721 y Fp(i)1434 709 y Fs(\))30 932 y(equal)41 b(the)g(pro)r(duct)g(measure)f(space.)77 b(On)41 b(the)g(measure)30 1031 y(space)27 b(\(\012)p Fm(;)14 b Fq(F)8 b Fs(\))28 b(de\014ne)g(an)g(indep)r(enden)n(t)g(reference)f(measure)30 1131 y Fm(\025)c Fs(=)189 1069 y Fn(Q)268 1156 y Fp(i)p Fo(2)p Fp(S)398 1131 y Fm(\025)446 1143 y Fp(i)501 1131 y Fs(where)k(eac)n(h)g Fm(\025)976 1143 y Fp(i)1031 1131 y Fs(is)h(the)g(uniform)f(measure)f(on)30 1231 y(\()p Fq(X)121 1243 y Fp(i)149 1231 y Fm(;)14 b Fq(F)246 1243 y Fp(i)273 1231 y Fs(\).)30 1380 y(Let)652 1480 y Fl(S)724 1455 y Fo(4)721 1506 y Fs(=)809 1480 y Fq(f)p Fs(\003)22 b Fq(\032)h Fm(S;)14 b Fs(\003)22 b Fq(6)p Fs(=)h Fq(;g)30 1624 y Fs(b)r(e)37 b(the)h(set)f(of)g(all)f(nonempt)n(y)h(subsets)g(of) g Fm(S:)g Fs(F)-7 b(or)36 b Fm(A)j Fq(2)g Fl(S)30 1723 y Fs(let)30 b(\012)212 1735 y Fp(A)295 1723 y Fs(and)g Fq(F)519 1735 y Fp(A)602 1723 y Fs(equal)f(the)h(restriction)f(of)g (\012)h(and)f Fq(F)37 b Fs(to)30 b Fm(A)30 1823 y Fs(resp)r(ectiv)n (ely)-7 b(.)35 b(Similarly)26 b Fm(!)911 1835 y Fp(A)990 1823 y Fs(represen)n(ts)e(the)i(pro)5 b(jection)25 b(of)30 1922 y Fm(!)h Fq(2)d Fs(\012)28 b(to)f(the)h(set)g(\012)708 1934 y Fp(A)762 1922 y Fs(.)30 2072 y(W)-7 b(e)37 b(will)h(no)n(w)e (de\014ne)i(a)e(Gibbs)i(measure)e(on)h(\(\012)p Fm(;)14 b Fq(F)8 b Fs(\).)65 b(T)-7 b(o)30 2172 y(that)28 b(end)g(w)n(e)f (\014rst)g(de\014ne)h(a)f(p)r(oten)n(tial.)30 2351 y Ft(De\014nition)k(2.1)40 b Fk(A)27 b Fs(p)r(oten)n(tial)f Fk(is)h(a)g(family)h Fs(\010)23 b(=)g Fq(f)p Fs(\010)1754 2363 y Fp(A)1807 2351 y Fq(g)1849 2363 y Fp(A)p Fo(2)p Fj(S)30 2450 y Fk(of)31 b(functions)e Fs(\010)548 2462 y Fp(A)625 2450 y Fs(:)24 b(\012)f Fq(!)g Fm(I)-21 b(R)30 b Fk(such)g(that)44 2659 y(\(1\))42 b(F)-6 b(or)30 b(e)l(ach)h Fm(A)23 b Fq(2)g Fl(S)e Fk(we)30 b(have)h Fs(\010)1151 2671 y Fp(A)1235 2659 y Fk(is)f Fq(F)1384 2671 y Fp(A)1438 2659 y Fq(\000)p Fk(me)l(asur)l(able.)44 2821 y(\(2\))42 b(F)-6 b(or)30 b(al)t(l)h Fs(\003)23 b Fq(2)g Fl(S)e Fk(and)30 b Fm(!)c Fq(2)d Fs(\012)30 b Fk(the)g Fs(energy)414 3011 y Fm(H)490 2977 y Fi(\010)483 3032 y(\003)541 3011 y Fs(\()p Fm(!)s Fs(\))687 2987 y Fo(4)684 3038 y Fs(=)912 2933 y Fn(X)771 3115 y Fp(A)p Fo(2)p Fj(S)-10 b Fp(;)24 b(A)p Fo(\\)p Fi(\003)p Fo(6)p Fi(=)p Fo(;)1187 3011 y Fs(\010)1247 3023 y Fp(A)1301 3011 y Fs(\()p Fm(!)s Fs(\))119 b Fk(exists.)30 3287 y Ft(De\014nition)31 b(2.2)40 b Fk(The)h Fs(\014nite)f(Gibbs)f(measure)f Fk(is)j(de\014ne)l(d)30 3387 y(as)599 3534 y Fm(\026)649 3500 y Fi(\010)700 3534 y Fs(\()p Fm(!)s Fs(\))24 b(=)940 3478 y Fm(e)979 3448 y Fo(\000)p Fp(H)1089 3423 y Fh(\010)1085 3465 y Fg(S)1134 3448 y Fi(\()p Fp(!)r Fi(\))1234 3478 y Fm(\025)p Fs(\()p Fm(!)s Fs(\))p 940 3515 461 4 v 1114 3594 a Fm(Z)1177 3565 y Fi(\010)1171 3618 y Fp(S)30 3728 y Fk(wher)l(e)584 3828 y Fm(Z)647 3794 y Fi(\010)641 3848 y Fp(S)722 3828 y Fs(=)820 3749 y Fn(X)809 3927 y Fp(w)r Fo(2)p Fi(\012)965 3828 y Fm(e)1004 3794 y Fo(\000)p Fp(H)1114 3769 y Fh(\010)1110 3810 y Fg(S)1158 3794 y Fi(\()p Fp(!)r Fi(\))1258 3828 y Fm(\025)p Fs(\()p Fm(!)s Fs(\))30 4112 y(where)j Fm(Z)333 4082 y Fi(\010)327 4135 y Fp(S)412 4112 y Fs(is)g(called)h(the)g Fk(p)l(artition)i(function.)30 4299 y Ft(De\014nition)h(2.3)40 b Fk(The)35 b Fs(Mark)n(o)n(v)30 b(graph)i Fk(asso)l(ciate)l(d)j(with)g (a)30 4398 y(Gibbs)29 b(me)l(asur)l(e)g(with)g(p)l(otential)g Fs(\010)f Fk(is)h(an)f(undir)l(e)l(cte)l(d)h(gr)l(aph)30 4498 y Fs(\()p Fm(S)118 4468 y Fi(\010)170 4498 y Fm(;)14 b(E)273 4468 y Fi(\010)324 4498 y Fs(\))30 b Fk(wher)l(e)44 4706 y(\(1\))42 b(the)30 b(vertic)l(es)g(of)h(the)f(gr)l(aph,)h Fm(S)1177 4676 y Fi(\010)1228 4706 y Fk(,)f(ar)l(e)h(the)e(no)l(des)i (in)e Fm(S)44 4869 y Fk(\(2\))42 b Fq(f)p Fm(i;)14 b(j)5 b Fq(g)22 b(2)h Fm(E)551 4839 y Fi(\010)632 4869 y Fk(if)30 b(ther)l(e)f(exists)g(a)h(nonzer)l(o)f(p)l(otential)h Fs(\010)1926 4881 y Fp(A)196 4969 y Fk(with)e Fq(f)p Fm(i;)14 b(j)5 b Fq(g)22 b(2)h Fm(A)28 b Fk(\(ther)l(e)f(ar)l(e)h(no)g (self-lo)l(ops:)39 b(if)28 b Fq(f)p Fm(i;)14 b(j)5 b Fq(g)22 b(2)196 5068 y Fm(E)262 5038 y Fi(\010)343 5068 y Fk(then)30 b Fm(i)23 b Fq(6)p Fs(=)f Fm(j)5 b Fk(.\))30 5277 y Fs(W)-7 b(e)24 b(de\014ne)f(the)g(set)h(of)f(directed)g(edges)f (asso)r(ciated)g(with)i(the)30 5376 y(edge)j(set)h Fm(E)415 5346 y Fi(\010)494 5376 y Fs(to)f(b)r(e)386 5529 y Fm(~)373 5550 y(E)439 5516 y Fi(\010)517 5526 y Fo(4)514 5577 y Fs(=)602 5550 y Fq(f)p Fs(\()p Fm(i;)14 b(j)5 b Fs(\))p Fm(;)41 b Fs(\()p Fm(j;)14 b(i)p Fs(\))51 b(:)g Fq(f)p Fm(i;)14 b(j)5 b Fq(g)21 b(2)j Fm(E)1521 5516 y Fi(\010)1572 5550 y Fq(g)p Fm(:)2130 83 y Fs(It)44 b(will)f(b)r(e)h(our)f(con)n(v)n (en)n(tion)e(that)j Fq(f)p Fm(i;)14 b(j)5 b Fq(g)42 b Fs(represen)n(ts)g(the)2130 183 y Fk(undir)l(e)l(cte)l(d)37 b Fs(edge)f(b)r(et)n(w)n(een)h(no)r(de)g Fm(i)g Fs(and)f(no)r(de)h Fm(j)42 b Fs(whereas)2130 282 y(\()p Fm(i;)14 b(j)5 b Fs(\))28 b(represen)n(ts)e(the)i Fk(dir)l(e)l(cte)l(d)g Fs(edge)f(from)h(no)r(de)f Fm(i)h Fs(to)f(no)r(de)2130 382 y Fm(j)5 b Fs(.)2130 531 y(A)29 b Fk(p)l(airwise)j(p)l(otential)e Fs(is)e(a)g(p)r(oten)n(tial)h(\010)24 b(=)h Fq(f)p Fs(\010)3666 543 y Fp(A)3719 531 y Fq(g)3761 543 y Fp(A)p Fo(2)p Fj(S)3920 531 y Fs(suc)n(h)2130 631 y(that)31 b(if)h Fq(j)p Fm(A)p Fq(j)d Fm(>)f Fs(2)j(then)g(\010)2948 643 y Fp(A)3031 631 y Fs(=)d(0)p Fm(:)j Fs(W)-7 b(e)31 b(limit)h(our)e(discussion)2130 731 y(to)38 b(Gibbs)g(measures)e(based)h(on)h(p)r(oten)n(tials)f (consisting)g(of)2130 830 y(pairwise)21 b(p)r(oten)n(tials.)35 b(It)22 b(is)g(sho)n(wn)g(in)g([5])g(that)g(without)h(loss)2130 930 y(of)37 b(generalit)n(y)e(an)n(y)h(Gibbs)i(Measure)d(can)i(b)r(e)g (represen)n(ted)2130 1029 y(as)k(a)g(Gibbs)g(measure)g(with)h(pairwise) e(p)r(oten)n(tials.)78 b(This)2130 1129 y(new)28 b(represen)n(tation,)f (though,)h(ma)n(y)f(lead)h(to)g(a)g(large)e(state)2130 1229 y(expansion.)2130 1378 y(In)21 b(man)n(y)f(inference)g(problems)g (one)g(often)h(distinguishes)f(b)r(e-)2130 1478 y(t)n(w)n(een)29 b(t)n(w)n(o)f(kinds)h(of)g(no)r(des:)40 b(hidden)30 b(and)f(observ)n (ed.)39 b(F)-7 b(ur-)2130 1577 y(thermore)19 b(eac)n(h)f(observ)n(ed)g (no)r(des)i(is)f(assume)g(to)h(b)r(e)g(indep)r(en-)2130 1677 y(den)n(t)25 b(of)f(all)g(the)h(other)f(no)r(des)h(conditioned)f (on)g(a)g(particular)2130 1777 y(hidden)g(no)r(de.)36 b(In)24 b(this)g(pap)r(er)g(it)g(will)g(b)r(e)g(assumed)g(that)g(the) 2130 1876 y(e\013ects)31 b(of)f(the)h(observ)-5 b(ations)29 b(ha)n(v)n(e)g(b)r(een)i(captured)f(b)n(y)g(the)2130 1976 y(self-p)r(oten)n(tials:)36 b(\010)2751 1991 y Fo(f)p Fp(i)p Fo(g)2847 1976 y Fm(;)42 b(i)22 b Fq(2)i Fm(S:)2130 2197 y Ft(2.2)94 b(Lo)s(op)m(y)33 b(Belief)d(Propagation)i(Algorithm) 2130 2377 y Fs(W)-7 b(e)21 b(no)n(w)f(review)f(the)i(lo)r(op)n(y)f(b)r (elief)h(propagation)d(algorithm.)2130 2477 y(Recall)40 b(w)n(e)g(are)f(in)n(terested)h(in)h(computing)f(the)h(marginal)2130 2577 y(distribution)f(at)f(eac)n(h)g(no)r(de)g(of)h(a)f(\014nite)h (Gibbs)g(measure)2130 2676 y(de\014ned)34 b(b)n(y)g(a)f(pairwise)g(p)r (oten)n(tial.)56 b(The)34 b(LBP)f(algorithm)2130 2776 y(attempts)25 b(to)g(do)f(this)h(b)r(e)g(transmitting)g Fk(messages)g Fs(b)r(et)n(w)n(een)2130 2875 y(the)j(no)r(des)f(and)h (computing)f Fk(b)l(eliefs)i Fs(at)f(eac)n(h)f(no)r(de.)2130 3025 y(W)-7 b(e)20 b(can)g(think)h(of)f(the)g(messages)e(and)i(b)r (eliefs)h(as)e(probabilit)n(y)2130 3124 y(measures.)67 b(Sp)r(eci\014cally)-7 b(,)41 b(the)e Fk(message)g Fs(for)f(the)g (directed)2130 3224 y(edge)27 b(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)2602 3203 y Fm(~)2590 3224 y(E)2656 3194 y Fi(\010)2735 3224 y Fs(at)k(time)h Fm(n)g Fs(is)f(a)h(measure)e(:) 2774 3413 y Fm(m)2847 3379 y Fp(n)2847 3436 y Fi(\()p Fp(i;j)s Fi(\))3000 3413 y Fs(:)d Fq(X)3105 3425 y Fp(j)3164 3413 y Fq(!)g Fs([0)p Fm(;)14 b Fs(1])2130 3602 y(suc)n(h)30 b(that)2503 3540 y Fn(P)2590 3627 y Fp(w)2638 3635 y Fg(j)2669 3627 y Fo(2X)2762 3635 y Fg(j)2811 3602 y Fm(m)2884 3572 y Fp(n)2884 3629 y Fi(\()p Fp(i;j)s Fi(\))3013 3602 y Fs(\()p Fm(!)3097 3614 y Fp(j)3132 3602 y Fs(\))e(=)f(1)p Fm(:)j Fs(Similarly)-7 b(,)31 b(the)g Fk(b)l(elief)2130 3702 y Fs(at)c(no)r(de)h Fm(i)23 b Fq(2)g Fm(S)33 b Fs(at)27 b(time)h Fm(n)g Fs(is)f(a)g(measure:)2839 3891 y Fm(b)2875 3856 y Fp(n)2875 3911 y(i)2943 3891 y Fs(:)c Fq(X)3048 3903 y Fp(i)3099 3891 y Fq(!)g Fs([0)p Fm(;)14 b Fs(1])2130 4080 y(suc)n(h)27 b(that)2497 4017 y Fn(P)2585 4105 y Fp(w)2633 4113 y Fg(i)2659 4105 y Fo(2X)2752 4113 y Fg(i)2796 4080 y Fm(b)2832 4050 y Fp(n)2832 4101 y(i)2877 4080 y Fs(\()p Fm(!)2961 4092 y Fp(i)2988 4080 y Fs(\))c(=)g(1)p Fm(:)2130 4229 y Fs(W)-7 b(e)25 b(de\014ne)h(a)e(generic)g(op)r (eration)g Fm(\021)29 b Fs(that)c(tak)n(es)f(a)h(b)r(ounded,)2130 4329 y(nonnegativ)n(e)46 b(function)j Fm(f)56 b Fs(on)48 b(a)f(\014nite)i(domain)e Fq(X)60 b Fs(and)2130 4428 y(outputs)52 b(its)g Fk(normalization)p Fs(.)112 b(Sp)r(eci\014cally)52 b Fm(\021)66 b Fs(:)e Fm(f)72 b Fq(7!)2130 4466 y Fn(P)2218 4553 y Fp(x)p Fo(2X)2374 4528 y Fm(f)9 b Fs(\()p Fm(x)p Fs(\))p Fm(:)2130 4677 y Fs(Giv)n(en)27 b(a)h(graph)e(\()p Fm(S;)14 b(E)5 b Fs(\))28 b(and)g(an)n(y)f(set)g Fm(A)d Fq(2)f Fl(S)c Fs(let)2267 4866 y Fm(@)5 b(A)2404 4842 y Fo(4)2401 4893 y Fs(=)2489 4866 y Fq(f)p Fm(j)27 b Fq(2)d Fm(S)f Fq(n)18 b Fm(A)51 b Fs(:)f Fq(f)p Fm(i;)14 b(j)5 b Fq(g)22 b(2)h Fm(E)33 b Fs(for)27 b(some)g Fm(i)c Fq(2)g Fm(A)p Fq(g)2130 5055 y Fs(b)r(e)36 b(the)g Fk(b)l(oundary)g Fs(of)f(the)h(set)g Fm(A)f Fs(in)h(the)g(graph.)59 b(W)-7 b(e)36 b(will)2130 5155 y(abuse)25 b(notation)g(and)g(use)h Fm(@)5 b(i)25 b Fs(and)g Fm(@)5 b(i)14 b Fq(n)f Fm(j)31 b Fs(to)25 b(represen)n(t)g Fm(@)5 b Fq(f)p Fm(i)p Fq(g)2130 5255 y Fs(and)27 b Fm(@)5 b Fq(f)p Fm(i)p Fq(g)17 b(n)h(f)p Fm(j)5 b Fq(g)27 b Fs(resp)r(ectiv)n(ely)-7 b(.)2130 5450 y Ft(De\014nition)31 b(2.4)40 b Fk(The)52 b Fs(lo)r(op)n(y)d(b)r (elief)j(propagation)c(algo-)2130 5550 y(rithm)32 b Fk(c)l(onsists)g (of)g(the)g(fol)t(lowing)j(iter)l(ation)d(on)g(messages.)p eop %%Page: 3 3 3 2 bop 30 83 a Fk(F)-6 b(or)30 b(e)l(ach)h Fs(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)655 62 y Fm(~)642 83 y(E)708 53 y Fi(\010)760 83 y Fk(:)261 250 y Fm(m)334 214 y Fp(n)p Fi(+1)334 278 y(\()p Fp(i;j)s Fi(\))464 250 y Fs(\()p Fm(!)548 262 y Fp(j)583 250 y Fs(\))116 394 y Fo(4)113 444 y Fs(=)290 418 y Fm(\021)382 339 y Fn(X)348 517 y Fp(!)390 525 y Fg(i)416 517 y Fo(2X)509 525 y Fg(i)549 418 y Fm(e)588 382 y Fo(\000)640 388 y Fs(\()672 382 y Fi(\010)719 393 y Ff(f)p Fg(i;j)r Ff(g)852 382 y Fi(\()p Fp(!)920 390 y Fg(i)947 382 y Fp(;!)1009 390 y Fg(j)1039 382 y Fi(\)+\010)1163 393 y Ff(f)p Fg(i)p Ff(g)1251 382 y Fi(\()p Fp(!)1319 390 y Fg(i)1345 382 y Fi(\))1371 388 y Fs(\))1472 339 y Fn(Y)1421 521 y Fp(k)q Fo(2)p Fp(@)t(i)p Fo(n)p Fp(j)1644 418 y Fm(m)1717 383 y Fp(n)1717 440 y Fi(\()p Fp(k)q(;i)p Fi(\))1853 418 y Fs(\()p Fm(!)1937 430 y Fp(i)1964 418 y Fs(\))p Fm(:)30 677 y Fk(The)31 b(b)l(eliefs)g(at)f(time)f Fm(n)h Fk(ar)l(e)334 855 y Fm(b)370 821 y Fp(n)370 876 y(i)415 855 y Fs(\()p Fm(!)499 867 y Fp(i)526 855 y Fs(\))614 831 y Fo(4)611 882 y Fs(=)729 855 y Fm(\021)i(e)841 821 y Fo(\000)p Fi(\010)940 832 y Ff(f)p Fg(i)p Ff(g)1028 821 y Fi(\()p Fp(!)1096 829 y Fg(i)1122 821 y Fi(\))1185 776 y Fn(Y)1166 955 y Fp(k)q Fo(2)p Fp(@)t(i)1324 855 y Fm(m)1397 821 y Fp(n)1397 878 y Fi(\()p Fp(k)q(;i)p Fi(\))1532 855 y Fs(\()p Fm(!)1616 867 y Fp(i)1644 855 y Fs(\))30 1111 y Fk(The)f(messages)f(ar)l(e)g (initialize)l(d)i(to)e Fq(f)p Fm(m)1292 1081 y Fi(0)1292 1138 y(\()p Fp(i;j)s Fi(\))1421 1111 y Fs(\()p Fm(!)1505 1123 y Fp(j)1540 1111 y Fs(\))p Fq(g)1614 1139 y Fi(\()p Fp(i;j)s Fi(\))p Fo(2)1795 1124 y Fp(~)1784 1139 y(E)1836 1122 y Fh(\010)1885 1111 y Fk(.)30 1303 y Ft(De\014nition)h(2.5)40 b Fk(The)46 b(LBP)f(algorithm)g(is)g(said)h(to)e Fs(con-)30 1402 y(v)n(erge)68 b Fk(if)j(ther)l(e)g(exists)e(a)i(unique)f(set)f(of) i(messages)30 1502 y Fq(f)p Fm(m)145 1472 y Fo(\003)145 1529 y Fi(\()p Fp(i;j)s Fi(\))274 1502 y Fq(g)316 1530 y Fi(\()p Fp(i;j)s Fi(\))p Fo(2)497 1515 y Fp(~)486 1530 y(E)538 1513 y Fh(\010)620 1502 y Fk(such)34 b(that)g(for)h(e)l(ach)f Fs(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)1598 1481 y Fm(~)1585 1502 y(E)1651 1472 y Fi(\010)1736 1502 y Fk(the)34 b(se-)30 1610 y(quenc)l(e)29 b(of)i(messages)495 1777 y Fs(lim)466 1827 y Fp(n)p Fo(!1)653 1777 y Fq(k)p Fm(m)768 1743 y Fp(n)768 1799 y Fi(\()p Fp(i;j)s Fi(\))916 1777 y Fq(\000)18 b Fm(m)1072 1743 y Fo(\003)1072 1799 y Fi(\()p Fp(i;j)s Fi(\))1202 1777 y Fq(k)1244 1805 y Fk(TV)1392 1777 y Fs(=)23 b(0)p Fm(:)30 1973 y Fk(Wher)l(e)30 b Fq(k)18 b(\001)h(k)436 2001 y Fk(TV)590 1973 y(is)30 b(the)g(total)g(variation)i(norm.)30 2156 y Fs(If)g(the)f(messages)f (con)n(v)n(erge)f(then)i(clearly)f(the)i(b)r(eliefs)g(con-)30 2255 y(v)n(erge.)30 2405 y Ft(LBP)g(on)g(Finite)f(T)-8 b(rees)30 2554 y Fs(F)h(or)24 b(p)r(oten)n(tials)g(with)g(Mark)n(o)n(v) e(graphs)h(that)i(are)e(trees)h(LBP)30 2654 y(\(more)34 b(righ)n(tfully)h(called)f(BP)g(in)h(this)g(case\))f(con)n(v)n(erges)e (to)30 2753 y(the)38 b(true)f(marginals.)64 b(W)-7 b(e)38 b(state)f(this)h(result)f(and)g(giv)n(e)f(a)30 2853 y(represen)n (tation)24 b(of)i(the)g(measure)f Fm(\026)1177 2823 y Fi(\010)1255 2853 y Fs(in)h(terms)f(of)h(the)g(mes-)30 2953 y(sages.)30 3102 y(Recall)34 b(a)f Fk(tr)l(e)l(e)h Fs(is)g(a)f(singly)h(connected,)h(undirected)f(graph)30 3202 y(without)26 b(an)n(y)g(lo)r(ops.)35 b(W)-7 b(e)27 b(sometimes)e(single)h(out)f(one)h(no)r(de)30 3301 y Fm(s)38 b Fq(2)h Fm(S)i Fs(to)c(b)r(e)g(called)g(the)g Fk(r)l(o)l(ot)p Fs(.)64 b(On)37 b(the)g(tree)f(there)h(is)f(a)30 3401 y(natural)k(distance)g(measure)g Fm(d)45 b Fs(:)g Fm(S)32 b Fq(\002)27 b Fm(S)49 b Fq(!)c Fm(I)-21 b(R)1645 3371 y Fi(+)1700 3401 y Fs(,)45 b(where)30 3501 y Fm(d)p Fs(\()p Fm(i;)14 b(j)5 b Fs(\))25 b(is)g(the)h(n)n(um)n(b)r(er)e(of)h (edges)g(on)g(the)g(unique)g(path)g(from)30 3600 y(no)r(de)h Fm(i)g Fs(to)g(no)r(de)g Fm(j)5 b Fs(.)36 b(Let)26 b Fm(L)885 3570 y Fp(s)885 3621 y(n)953 3600 y Fq(\032)d Fm(S)30 b Fs(b)r(e)d(the)f(set)g(of)g(no)r(des)g(that)30 3700 y(are)d(exactly)g(a)g(distance)h Fm(n)f Fs(a)n(w)n(a)n(y)f(from)h (the)h(ro)r(ot)f Fm(s)p Fs(.)36 b(W)-7 b(e)24 b(will)30 3799 y(just)k(write)g Fm(L)464 3811 y Fp(n)536 3799 y Fs(when)g(the)g(ro)r(ot)f Fm(s)g Fs(is)h(ob)n(vious.)30 3949 y(The)h(follo)n(wing)g(result)g(is)g(standard)f(and)h(can)g(b)r(e) h(found)g(in,)30 4048 y(for)d(example,)g([2].)30 4225 y Ft(Prop)s(osition)j(2.1)41 b Fk(L)l(et)27 b Fs(\010)h Fk(b)l(e)g(a)g(p)l(airwise)h(p)l(otential)g(whose)30 4324 y(Markov)i(gr)l(aph)g Fs(\()p Fm(S)644 4294 y Fi(\010)696 4324 y Fm(;)14 b(E)799 4294 y Fi(\010)850 4324 y Fs(\))30 b Fk(is)g(a)h(tr)l(e)l(e.)38 b(Then)44 4527 y(\(1\))k(for)33 b(any)f(set)g(of)g(initial)h(messages)g Fq(f)p Fm(m)1443 4497 y Fi(0)1443 4554 y(\()p Fp(i;j)s Fi(\))1573 4527 y Fq(g)1615 4555 y Fi(\()p Fp(i;j)s Fi(\))1750 4540 y Fp(~)1740 4555 y(E)1792 4539 y Fh(\010)1872 4527 y Fk(the)196 4636 y(LBP)f(algorithm)g(c)l(onver)l(ges)f(to)g(a)h(unique)e(set)h(of)g (mes-)196 4735 y(sages)f Fq(f)p Fm(m)527 4705 y Fo(\003)527 4762 y Fi(\()p Fp(i;j)s Fi(\))657 4735 y Fq(g)699 4763 y Fi(\()p Fp(i;j)s Fi(\))834 4748 y Fp(~)824 4763 y(E)876 4747 y Fh(\010)44 4916 y Fk(\(2\))42 b(for)31 b(any)f(c)l(onne)l(cte)l (d)f(subset)g Fm(A)24 b Fq(\032)e Fm(S)1338 4886 y Fi(\010)1419 4916 y Fk(one)30 b(has)255 5099 y Fm(\026)305 5065 y Fi(\010)357 5099 y Fs(\()p Fm(!)441 5111 y Fp(A)495 5099 y Fs(\))23 b(=)g Fm(\021)720 5020 y Fn(Y)696 5199 y Fp(B)s Fo(\022)p Fp(A)864 5099 y Fm(e)903 5065 y Fo(\000)p Fi(\010)1002 5073 y Fg(B)1051 5065 y Fi(\()p Fp(!)1119 5073 y Fg(A)1166 5065 y Fi(\))1236 5020 y Fn(Y)1210 5199 y Fp(i)p Fo(2)p Fp(@)t(A)1381 5099 y Fm(m)1454 5065 y Fo(\003)1454 5122 y Fi(\()p Fp(i;i)1546 5130 y Fg(A)1594 5122 y Fi(\))1624 5099 y Fs(\()p Fm(!)1708 5111 y Fp(i)1731 5119 y Fg(A)1783 5099 y Fs(\))59 b(\(1\))196 5351 y Fk(wher)l(e)26 b Fm(i)455 5363 y Fp(A)535 5351 y Fk(b)l(e)f(the)h(unique)f(neighb)l(or)i(of)f(no) l(de)g Fm(i)d Fq(2)g Fm(@)5 b(A)26 b Fk(in)196 5450 y(the)34 b(set)e Fm(A)p Fk(.)50 b(Henc)l(e)33 b(the)g(b)l(eliefs)i(c)l(onver)l (ge)f(to)f(the)h(true)196 5550 y(mar)l(ginals.)2130 83 y Fs(Note)22 b(that)g(equation)f(\(1\))h(states)f(that)h(the)g (marginal)e(on)i(an)n(y)2130 183 y(connected)39 b(set)g(of)f(no)r(des)h (in)g(a)g(tree)f(can)h(b)r(e)g(determined)2130 282 y(b)n(y)28 b(the)h(p)r(oten)n(tials)f(de\014ned)g(on)g(the)h(set)f(and)g(the)h (messages)2130 382 y(transmitted)e(across)d(the)j(set's)g(b)r(oundary) -7 b(.)36 b(A)27 b(b)r(elief)g(is)f(just)2130 482 y(a)h(marginal)f(on)i (one)f(no)r(de.)2130 691 y Ft(2.3)94 b(The)33 b(Computation)d(T)-8 b(ree)2130 869 y Fs(W)h(e)30 b(no)n(w)f(sho)n(w)g(that)h Fm(n)f Fs(iterations)g(of)g(the)h(LBP)f(algorithm)2130 969 y(on)38 b(a)g(giv)n(en)f(\014nite,)42 b(pairwise)37 b(p)r(oten)n(tial,)k(Gibbs)d(measure)2130 1068 y(can)e(b)r(e)i (represen)n(ted)d(as)h(an)h(exact)f(BP)g(algorithm)g(on)g(an)2130 1168 y(asso)r(ciated)17 b(Gibbs)i(measure)e(de\014ned)i(on)f(a)g(tree,) i(sp)r(eci\014cally)2130 1267 y(the)28 b Fk(c)l(omputation)i(tr)l(e)l (e.)37 b Fs([5])2130 1446 y Ft(De\014nition)31 b(2.6)40 b Fk(Given)35 b(a)f(p)l(airwise)i(p)l(otential)f Fs(\010)f Fk(and)g(its)2130 1545 y(gr)l(aph)46 b Fs(\()p Fm(S)2459 1515 y Fi(\010)2511 1545 y Fm(;)14 b(E)2614 1515 y Fi(\010)2665 1545 y Fs(\))p Fk(,)50 b(the)45 b(asso)l(ciate)l(d)i Fs(computation)d(tree)g(of)2130 1645 y(depth)23 b Fm(n)f Fs(with)g(ro)r(ot)f Fm(s)i Fq(2)h Fm(S)2984 1615 y Fi(\010)3057 1645 y Fk(,)i(denote)l(d)f Fs(\()3453 1624 y(~)3438 1645 y Fm(S)3494 1615 y Fi(\010)p Fp(;s)3489 1665 y(n)3597 1645 y Fm(;)3653 1624 y Fs(~)3634 1645 y Fm(E)3700 1615 y Fi(\010)p Fp(;s)3695 1665 y(n)3802 1645 y Fs(\))p Fk(,)i(is)e(de-) 2130 1744 y(\014ne)l(d)d(as)g(the)g(tr)l(e)l(e)f(that)h(c)l(onsists)f (of)i(al)t(l)g(length)f Fm(n)g Fk(p)l(aths)g(in)g(the)2130 1844 y(gr)l(aph,)40 b Fs(\()p Fm(S)2478 1814 y Fi(\010)2529 1844 y Fm(;)14 b(E)2632 1814 y Fi(\010)2684 1844 y Fs(\))p Fk(,)38 b(starting)f(at)f Fm(i)3228 1856 y Fi(0)3300 1844 y Fs(=)f Fm(s)p Fk(,)j Fs(\()p Fm(i)3563 1856 y Fi(0)3600 1844 y Fm(;)14 b(i)3666 1856 y Fi(1)3703 1844 y Fm(;)g(i)3769 1856 y Fi(2)3805 1844 y Fm(;)g(:::;)g(i)3977 1856 y Fp(n)4022 1844 y Fs(\))p Fk(,)2130 1944 y(that)22 b(never)h(b)l(acktr)l(ack.)37 b(Sp)l(e)l(ci\014c)l(al)t(ly)24 b(the)f(tr)l(e)l(e)e(c)l(onsists)i(of)g(al)t(l)2130 2043 y(length)30 b Fm(n)g Fk(p)l(aths)g(wher)l(e)g Fq(f)p Fm(i)2973 2055 y Fp(k)3013 2043 y Fm(;)14 b(i)3079 2055 y Fp(k)q Fi(+1)3204 2043 y Fq(g)22 b(2)i Fm(E)3413 2013 y Fi(\010)3494 2043 y Fk(and)30 b Fm(i)3684 2055 y Fp(k)3748 2043 y Fq(6)p Fs(=)22 b Fm(i)3864 2055 y Fp(k)q Fi(+2)3989 2043 y Fk(.)2130 2221 y Fs(Figure)i(one)h(sho)n(ws)f(an)g(example)h(of) f(a)h(computation)g(tree)f(of)2130 2321 y(depth)30 b(three)f(starting)g (at)h(no)r(de)f Fm(a)p Fs(.)43 b(In)29 b(the)h(\014gure)f(w)n(e)g(ha)n (v)n(e)2130 2421 y(lab)r(eled)38 b(eac)n(h)f(no)r(de)i(in)f(the)g (computation)g(tree)g(with)h(the)2130 2520 y(asso)r(ciated)26 b(no)r(de)i(in)g(the)g(original)e(graph.)2899 3462 y Fe(h)3199 3162 y(h)3199 3462 y(h)225 b(h)3799 3762 y(h)-825 b(h)3049 4062 y(h)225 b(h)3349 3762 y(h)2749 4062 y(h)-375 b(h)2599 3762 y(h)3649 4062 y(h)225 b(h)2599 2712 y(h)2299 3012 y(h)2599 3312 y(h)2899 3012 y(h)1248 2982 y gsave 0 0 0 setrgbcolor 1248 2982 a 3197 3425 4 226 v 1248 2982 a grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3047 4025 4 226 v 1248 2982 a grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3347 4025 4 226 v 1248 2982 a grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3078 3283 a Fd(\000)2995 3366 y(\000)2936 3425 y(\000)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3236 3283 a Fd(@)3319 3366 y(@)3378 3425 y(@)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2778 3583 a Fd(\000)2695 3666 y(\000)2636 3725 y(\000)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3536 3583 a Fd(@)3619 3666 y(@)3678 3725 y(@)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3143 3583 a Fd(\012)3088 3666 y(\012)3049 3725 y(\012)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3199 3583 a Fd(J)3254 3666 y(J)3293 3725 y(J)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2543 3883 a Fd(\012)2488 3966 y(\012)2449 4025 y(\012)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2599 3883 a Fd(J)2654 3966 y(J)2693 4025 y(J)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3743 3883 a Fd(\012)3688 3966 y(\012)3649 4025 y(\012)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 3799 3883 a Fd(J)3854 3966 y(J)3893 4025 y(J)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2778 2975 a Fd(@)2695 2892 y(@)2636 2833 y(@)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2636 3275 a Fd(\000)2719 3192 y(\000)2778 3133 y(\000)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2336 2975 a Fd(\000)2419 2892 y(\000)2478 2833 y(\000)1248 2982 y grestore 1248 2982 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2597 3275 4 526 v 1248 2982 a grestore 1248 2982 a 3274 3200 a gsave 0 0 0 setrgbcolor 3274 3200 a Fc(a)3325 3200 y grestore 3325 3200 a 3274 3500 a gsave 0 0 0 setrgbcolor 3274 3500 a Fc(d)3325 3500 y grestore 3325 3500 a 3574 3500 a gsave 0 0 0 setrgbcolor 3574 3500 a Fc(c)3616 3500 y grestore 3616 3500 a 2674 3800 a gsave 0 0 0 setrgbcolor 2674 3800 a Fc(d)2725 3800 y grestore 2725 3800 a 3874 3800 a gsave 0 0 0 setrgbcolor 3874 3800 a Fc(d)3925 3800 y grestore 3925 3800 a 2974 3500 a gsave 0 0 0 setrgbcolor 2974 3500 a Fc(b)3015 3500 y grestore 3015 3500 a 3124 3800 a gsave 0 0 0 setrgbcolor 3124 3800 a Fc(b)3165 3800 y grestore 3165 3800 a 3424 3800 a gsave 0 0 0 setrgbcolor 3424 3800 a Fc(c)3466 3800 y grestore 3466 3800 a 2524 4100 a gsave 0 0 0 setrgbcolor 2524 4100 a Fc(a)2575 4100 y grestore 2575 4100 a 2824 4100 a gsave 0 0 0 setrgbcolor 2824 4100 a Fc(c)2866 4100 y grestore 2866 4100 a 3124 4100 a gsave 0 0 0 setrgbcolor 3124 4100 a Fc(a)3175 4100 y grestore 3175 4100 a 3424 4100 a gsave 0 0 0 setrgbcolor 3424 4100 a Fc(a)3475 4100 y grestore 3475 4100 a 3724 4100 a gsave 0 0 0 setrgbcolor 3724 4100 a Fc(a)3775 4100 y grestore 3775 4100 a 4024 4100 a gsave 0 0 0 setrgbcolor 4024 4100 a Fc(b)4065 4100 y grestore 4065 4100 a 2674 2750 a gsave 0 0 0 setrgbcolor 2674 2750 a Fc(a)2725 2750 y grestore 2725 2750 a 2186 3050 a gsave 0 0 0 setrgbcolor 2186 3050 a Fc(b)2227 3050 y grestore 2227 3050 a 2486 3350 a gsave 0 0 0 setrgbcolor 2486 3350 a Fc(d)2537 3350 y grestore 2537 3350 a 2974 3050 a gsave 0 0 0 setrgbcolor 2974 3050 a Fc(c)3016 3050 y grestore 3016 3050 a 1248 2982 a gsave 0 0 0 setrgbcolor 1248 2982 a 2336 3133 a Fd(@)2419 3216 y(@)2478 3275 y(@)1248 2982 y grestore 1248 2982 a 2336 4328 a Fs(Figure)27 b(1:)36 b(Example)27 b(of)g(a)h(Computation) f(T)-7 b(ree)2130 4517 y(W)g(e)26 b(w)n(an)n(t)f(to)h(construct)f(a)g (Gibbs)h(measure)e(whose)h(Mark)n(o)n(v)2130 4617 y(graph)c(is)i(the)g (computation)f(tree.)35 b(F)-7 b(or)22 b(eac)n(h)f(edge)h(and)h(non-) 2130 4716 y(leaf)37 b(no)r(de)g(w)n(e)g(will)g(place)g(a)g(p)r(oten)n (tial)g(corresp)r(onding)e(to)2130 4816 y(the)28 b(p)r(oten)n(tial)g (on)f(the)h(original)e(graph.)36 b(W)-7 b(e)28 b(need)g(only)f(de-)2130 4916 y(\014ne)e(the)g(set)g(of)g Fk(b)l(oundary)h Fs(self-p)r(oten)n (tials)f(on)f(the)h(lea)n(v)n(es)f(in)2130 5015 y(terms)d(of)h(the)g (initializing)g(messages.)33 b(F)-7 b(or)21 b(eac)n(h)g(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)3975 4994 y Fm(~)3962 5015 y(E)4028 4985 y Fi(\010)2130 5115 y Fs(let)2505 5214 y(\010)2565 5175 y Fp(i)p Fo(!)p Fp(j)2565 5243 y Fo(f)p Fp(i)p Fo(g)2690 5214 y Fs(\()p Fm(!)2774 5226 y Fp(i)2802 5214 y Fs(\))g(=)g Fq(\000)3068 5136 y Fn(X)3024 5318 y Fp(k)q Fo(2)p Fp(@)t(i)p Fo(n)p Fp(j)3246 5214 y Fs(ln)14 b Fm(m)3402 5180 y Fi(0)3402 5237 y(\()p Fp(k)q(;i)p Fi(\))3538 5214 y Fs(\()p Fm(!)3622 5226 y Fp(i)3649 5214 y Fs(\))p Fm(:)2130 5441 y Fs(Note)25 b(that)h(in)f(the)h(case)e (when)i(the)f(initial)h(messages)d(are)h(all)2130 5540 y(set)k(to)f(the)h(ones)f(v)n(ector)f(w)n(e)i(ha)n(v)n(e)e(\010)3312 5501 y Fp(i)p Fo(!)p Fp(j)3312 5569 y Fo(f)p Fp(i)p Fo(g)3460 5540 y Fq(\021)c Fs(0.)p eop %%Page: 4 4 4 3 bop 30 83 a Ft(De\014nition)31 b(2.7)40 b Fk(Given)f Fs(\010)p Fk(,)h(its)e(asso)l(ciate)l(d)i(c)l(omputation)30 183 y(tr)l(e)l(e,)26 b Fs(\()258 162 y(~)244 183 y Fm(S)300 153 y Fi(\010)p Fp(;s)295 203 y(n)403 183 y Fm(;)459 162 y Fs(~)440 183 y Fm(E)506 153 y Fi(\010)p Fp(;s)501 203 y(n)608 183 y Fs(\))p Fk(,)h(and)f(a)g(set)f(of)h(b)l(oundary)g (self-p)l(otentials)30 282 y Fq(f)p Fs(\010)132 242 y Fp(i)p Fo(!)p Fp(j)132 305 y(i)256 282 y Fq(g)298 310 y Fi(\()p Fp(i;j)s Fi(\))p Fo(2)478 295 y Fp(~)468 310 y(E)520 294 y Fh(\010)601 282 y Fk(de\014ne)34 b(the)f(asso)l(ciate)l (d)i Fs(p)r(oten)n(tial)c(for)g(the)30 409 y(computation)24 b(tree)f(of)h(depth)g Fm(n)p Fk(,)j(denote)l(d)1406 388 y Fs(~)1397 409 y(\010)1457 379 y Fp(n;s)1553 409 y Fk(,)h(as)e(fol)t (lows:)44 627 y(\(1\))42 b(L)l(et)f(the)h(map)g Fs(\000)747 597 y Fp(n)836 627 y Fs(:)918 606 y(~)904 627 y Fm(S)960 597 y Fi(\010)p Fp(;s)955 647 y(n)1106 627 y Fq(!)j Fm(S)1290 597 y Fi(\010)1383 627 y Fk(b)l(e)c(the)h(map)g(that)196 726 y(takes)25 b(no)l(de)584 707 y Fs(~)590 726 y Fm(i)f Fk(to)h(its)f(asso)l(ciate)l(d)i(no)l(de)e Fm(i)g Fk(in)h(the)f (original)196 826 y(gr)l(aph.)40 b(\(As)29 b(c)l(onstructe)l(d)g(in)h (de\014nition)g(2.6.\))44 995 y(\(2\))42 b(F)-6 b(or)30 b(e)l(ach)h Fq(f)574 976 y Fs(~)580 995 y Fm(i)o(;)644 976 y Fs(~)645 995 y Fm(j)5 b Fq(g)22 b(2)846 974 y Fs(~)827 995 y Fm(E)893 965 y Fi(\010)p Fp(;s)888 1016 y(n)1025 995 y Fk(let)1151 974 y Fs(~)1142 995 y(\010)1202 955 y Fp(n;s)1202 1032 y Fo(f)1231 1019 y Fi(~)1236 1032 y Fp(i;)1278 1019 y Fi(~)1279 1032 y Fp(j)t Fo(g)1371 995 y Fs(=)h(\010)1519 1019 y Fo(f)p Fi(\000)1594 1002 y Fg(n)1634 1019 y Fi(\()1655 1006 y(~)1660 1019 y Fp(i)q Fi(\))p Fp(;)p Fi(\000)1771 1002 y Fg(n)1811 1019 y Fi(\()1836 1006 y(~)1837 1019 y Fp(j)t Fi(\))p Fo(g)44 1201 y Fk(\(3\))42 b(F)-6 b(or)30 b(e)l(ach)531 1182 y Fs(~)538 1201 y Fm(i)22 b Fq(2)682 1180 y Fs(~)668 1201 y Fm(S)724 1171 y Fi(\010)p Fp(;s)719 1222 y(n)856 1201 y Fk(let)205 1547 y Fs(~)196 1568 y(\010)256 1529 y Fp(n;s)256 1606 y Fo(f)285 1593 y Fi(~)290 1606 y Fp(i)q Fo(g)375 1568 y Fs(=)463 1324 y Fn(8)463 1398 y(>)463 1423 y(>)463 1448 y(>)463 1473 y(<)463 1622 y(>)463 1647 y(>)463 1672 y(>)463 1697 y(:)791 1391 y Fs(\010)851 1415 y Fo(f)p Fi(\000)926 1398 y Fg(n)967 1415 y Fi(\()988 1402 y(~)993 1415 y Fp(i)p Fi(\))p Fo(g)1288 1391 y Fk(if)1362 1372 y Fs(~)1369 1391 y Fm(i)h Fq(2)1513 1370 y Fs(~)1499 1391 y Fm(S)1555 1361 y Fi(\010)p Fp(;s)1550 1412 y(n)1657 1391 y Fq(n)p Fm(L)1756 1361 y Fp(s)1756 1412 y(n)578 1625 y Fs(\010)638 1649 y Fo(f)p Fi(\000)713 1632 y Fg(n)754 1649 y Fi(\()775 1636 y(~)780 1649 y Fp(i)p Fi(\))p Fo(g)886 1625 y Fs(+)18 b(\010)1029 1582 y Fi(\000)1070 1557 y Fg(n)1111 1582 y Fi(\()1132 1569 y(~)1137 1582 y Fp(i)p Fi(\))p Fo(!)p Fi(\000)1293 1557 y Fg(n)1334 1582 y Fi(\()1359 1569 y(~)1360 1582 y Fp(j)t Fi(\))1029 1662 y Fo(f)p Fi(\000)1104 1645 y Fg(n)1145 1662 y Fi(\()1166 1649 y(~)1171 1662 y Fp(i)p Fi(\))p Fo(g)1510 1625 y Fk(if)1584 1606 y Fs(~)1591 1625 y Fm(i)k Fq(2)i Fm(L)1778 1595 y Fp(s)1778 1645 y(n)1852 1625 y Fk(and)722 1751 y(wher)l(e)955 1732 y Fs(~)957 1751 y Fm(j)34 b Fk(is)c(the)g(unique)g(p)l(ar)l(ent)f(of)1864 1732 y Fs(~)1871 1751 y Fm(i)30 1992 y Fs(Let)24 b Fm(\026)232 1947 y Fi(~)225 1962 y(\010)272 1937 y Fg(n;s)364 1992 y Fs(\()7 b(~)-49 b Fm(!)s Fs(\))24 b(b)r(e)g(the)g(measured)f (determined)h(b)n(y)1672 1971 y(~)1662 1992 y(\010)1722 1962 y Fp(n;s)1819 1992 y Fs(.)35 b(By)30 2092 y(construction,)c (running)g(LBP)f(\(in)i(this)f(case)f(BP\))h(to)g(com-)30 2192 y(pute)25 b(the)f(b)r(elief)h(at)f(the)h(ro)r(ot)e(no)r(de,)i Fm(s)p Fs(,)g(of)f(the)g(computation)30 2291 y(tree)e(of)h(depth)g Fm(n)f Fs(is)g(equiv)-5 b(alen)n(t)22 b(to)h(computing)f(the)h(b)r (elief)g(at)30 2391 y(no)r(de)j Fm(s)g Fs(on)g(the)g(original)e(graph)h (after)h Fm(n)g Fs(iterations)f(of)h(LBP)30 2490 y(initialized)i (appropriately)-7 b(.)30 2730 y Fr(3)112 b(Con)m(v)m(ergence)38 b(of)g(LBP)f(and)h(the)f(W)-9 b(eak)198 2846 y(Limit)30 3050 y Fs(A)25 b(sequence)f(of)h(measures)f Fq(f)p Fm(\026)1003 3005 y Fi(~)996 3020 y(\010)1043 2995 y Fg(n;s)1134 3050 y Fq(g)1176 3062 y Fp(n)p Fo(\025)p Fi(1)1331 3050 y Fs(has)g(a)g Fk(we)l(ak)k(limit)e Fs(if)30 3161 y(for)h(eac)n(h)f Fm(N)37 b Fs(there)27 b(exists)g(a)g(measure)f Fm(\026)1330 3173 y Fp(N)1421 3161 y Fs(de\014ned)i(on)1836 3140 y(~)1822 3161 y Fm(S)1878 3121 y Fi(\010)p Fp(;s)1873 3185 y(N)30 3261 y Fs(suc)n(h)f(that)h(for)f(all)h(ev)n(en)n(ts)e Fm(A)e Fq(2)f(F)1126 3274 y Fi(~)1115 3289 y Fp(S)1159 3260 y Fh(\010)p Fg(;s)1156 3308 y(N)1281 3261 y Fs(w)n(e)28 b(ha)n(v)n(e)596 3489 y(lim)483 3543 y Fp(n)p Fo(\025)p Fp(N)s(;n)p Fo(!1)838 3489 y Fm(\026)895 3440 y Fi(~)888 3455 y(\010)935 3430 y Fg(n;s)1027 3489 y Fs(\()p Fm(A)p Fs(\))c(=)e Fm(\026)1314 3501 y Fp(N)1377 3489 y Fs(\()p Fm(A)p Fs(\))p Fm(:)30 3713 y Ft(Prop)s(osition)30 b(3.1)41 b Fk(The)58 b(LBP)g(algorithm)h(c)l(onver)l(ges)f(if)30 3821 y(and)28 b(only)f(if)h(the)g(se)l(quenc)l(e)e(of)i(me)l(asur)l(es) f Fq(f)p Fm(\026)1461 3776 y Fi(~)1454 3791 y(\010)1501 3766 y Fg(n;s)1593 3821 y Fq(g)1635 3833 y Fp(n)p Fo(\025)p Fi(1)1792 3821 y Fk(has)h(a)30 3921 y(we)l(ak)i(limit.)30 4104 y Ft(Pro)s(of:)k Fs(W)-7 b(e)24 b(sk)n(etc)n(h)e(the)i(pro)r(of.) 35 b(F)-7 b(ull)24 b(details)f(can)g(b)r(e)h(found)30 4204 y(in)30 b([3)o(].)42 b(Using)29 b(prop)r(osition)g(2.1)f(and)h (the)h(de\014nition)f(of)h(the)30 4303 y(computation)d(tree)h(w)n(e)f (ha)n(v)n(e)f Fq(8)h Fm(n)c(>)g(N)36 b Fs(and)27 b Fq(8)g Fm(\020)j Fq(2)23 b Fs(\012)1782 4316 y Fi(~)1771 4331 y Fp(S)1815 4303 y Fh(\010)p Fg(;s)1812 4351 y(N)1910 4303 y Fs(:)30 4532 y Fm(\026)87 4483 y Fi(~)80 4498 y(\010)127 4472 y Fg(n;s)219 4532 y Fs(\()p Fm(\020)6 b Fs(\))24 b(=)f Fm(\021)562 4453 y Fn(Y)495 4647 y Fp(B)s Fo(\022)611 4632 y Fi(~)600 4647 y Fp(S)644 4619 y Fh(\010)p Fg(;s)641 4667 y(N)748 4532 y Fm(e)787 4497 y Fo(\000)p Fi(\010)886 4505 y Fg(B)935 4497 y Fi(\()p Fp(\020)t Fi(\))1107 4453 y Fn(Y)1034 4634 y Fi(~)1039 4647 y Fp(i)q Fo(2)p Fp(@)1157 4632 y Fi(~)1147 4647 y Fp(S)1191 4619 y Fh(\010)p Fg(;s)1188 4667 y(N)1295 4532 y Fm(m)1368 4496 y Fp(n)p Fo(\000)p Fp(N)1368 4569 y Fi(\(\003)1439 4552 y Fg(N)1493 4569 y Fi(\()1514 4556 y(~)1519 4569 y Fp(i)p Fi(\))p Fp(;)p Fi(\003)1633 4552 y Fg(N)1687 4569 y Fi(\()1708 4556 y(~)1713 4569 y Fp(i)1745 4589 y Fh(~)1736 4599 y Fg(S)1774 4577 y Fh(\010)p Fg(;s)1772 4621 y(N)1869 4569 y Fi(\)\))1925 4532 y Fs(\()p Fm(\020)6 b Fs(\))30 4848 y(F)-7 b(or)38 b(\014xed)h Fm(N)47 b Fs(the)39 b(b)r(oundary)f Fq(j)p Fm(@)1141 4827 y Fs(~)1127 4848 y Fm(S)1183 4808 y Fi(\010)p Fp(;s)1178 4872 y(N)1285 4848 y Fq(j)h Fs(is)f(\014nite.)71 b(If)39 b(LBP)30 4947 y(con)n(v)n(erges)30 b(then)j(the)g(second)f(factor)f(ab)r(o)n(v)n(e)h (con)n(v)n(erges,)f(as)30 5047 y Fm(n)38 b Fq(!)g(1)p Fs(,)h(to)495 4985 y Fn(Q)568 5061 y Fi(~)573 5074 y Fp(i)597 5075 y Fo(2)p Fp(@)691 5060 y Fi(~)681 5075 y Fp(S)725 5047 y Fh(\010)p Fg(;s)722 5094 y(N)833 5047 y Fm(m)906 5017 y Fo(\003)906 5083 y Fi(\(\003)977 5066 y Fg(N)1031 5083 y Fi(\()1052 5070 y(~)1057 5083 y Fp(i)p Fi(\))p Fp(;)p Fi(\003)1171 5066 y Fg(N)1225 5083 y Fi(\()1246 5070 y(~)1251 5083 y Fp(i)1283 5103 y Fh(~)1274 5113 y Fg(S)1312 5091 y Fh(\010)p Fg(;s)1310 5135 y(N)1407 5083 y Fi(\)\))1463 5047 y Fs(\()p Fm(\020)6 b Fs(\))38 b(and)e(hence)30 5201 y(the)31 b(w)n(eak)f(limit)i(exists.)46 b(A)32 b(similar)e(argumen)n(t)g(pro)n(v)n(es)f(the)30 5301 y(other)e(direction.)36 b Fb(2)30 5450 y Fs(Our)i(goal)f(for)h (the)h(rest)f(of)h(the)f(pap)r(er)h(is)f(to)g(understand)30 5550 y(the)21 b(con)n(v)n(ergence)e(prop)r(erties)g(of)i(the)g (sequence)g(of)f(measures)2130 84 y Fq(f)p Fm(\026)2229 39 y Fi(~)2222 54 y(\010)2269 29 y Fg(n;s)2361 84 y Fq(g)2403 96 y Fp(n)p Fo(\025)p Fi(1)2532 84 y Fs(.)63 b(Ho)n(w)n(ev)n(er,)37 b(instead)f(of)g(w)n(orking)e(with)j(a)f(se-)2130 184 y(quence)31 b(of)h(\014nite)g(trees)f(of)g(increasing)f(depth)i(w)n(e)f (will)h(\014nd)2130 283 y(it)k(easier)e(to)i(study)g(one)f(in\014nite)i (tree)e(and)g(the)h(measures)2130 383 y(de\014ned)28 b(on)f(it.)2130 618 y Fr(4)112 b(Gibbs)37 b(Measures)i(Ov)m(er)f(a)g (Coun)m(table)2298 734 y(Set)f(of)h(Sites)2130 934 y Fs(Constructing)27 b(a)g(Gibbs)g(measure)g(o)n(v)n(er)e(a)i(coun)n (table)g(set)g(of)2130 1034 y(no)r(des)22 b(can)f(b)r(e)i(a)e(tric)n (ky)g(business.)35 b(F)-7 b(or)21 b(example,)i(there)e(can)2130 1134 y(b)r(e)26 b(man)n(y)f(Gibbs)h(measures)e(consisten)n(t)h(with)i (a)e(giv)n(en)g(lo)r(cal)2130 1233 y(sp)r(eci\014cation)30 b(pro)n(vided)f(b)n(y)h(the)h(p)r(oten)n(tials.)45 b(This)30 b(section)2130 1333 y(is)20 b(dev)n(oted)f(to)h(the)g(construction)f (of)g(these)h(Gibbs)g(measures.)2130 1544 y Ft(4.1)94 b(Sp)s(eci\014cations)2130 1722 y Fs(W)-7 b(e)36 b(no)n(w)f(let)h(the)g (set)g(of)f(no)r(des)h Fm(S)k Fs(b)r(e)c(coun)n(tably)f(in\014nite)2130 1822 y(and)27 b(rede\014ne)2586 1990 y Fl(S)14 b Fs(=)23 b Fq(f)p Fs(\003)f Fq(\032)h Fm(S)55 b Fs(:)c(0)22 b Fm(<)h Fq(j)p Fs(\003)p Fq(j)g Fm(<)g Fq(1g)2130 2157 y Fs(to)42 b(b)r(e)h(the)f(set)h(of)f(all)g(nonempt)n(y)-7 b(,)46 b Fk(\014nite)p Fs(,)f(subsets)d(of)g Fm(S)5 b Fs(.)2130 2257 y(A)n(t)36 b(ev)n(ery)f(no)r(de)h Fm(i)g Fq(2)h Fm(S)k Fs(there)35 b(is)h(a)g(\014nite)g(measure)f(space)2130 2357 y(\()p Fq(X)2221 2369 y Fp(i)2249 2357 y Fm(;)14 b Fq(F)2346 2369 y Fp(i)2373 2357 y Fs(\).)42 b(W)-7 b(e)29 b(construct,)g(in)g(the)h(usual)e(w)n(a)n(y)-7 b(,)29 b(the)g(pro)r(duct)2130 2456 y(measure)h(space)g(\(\012)p Fm(;)14 b Fq(F)8 b Fs(\))29 b(=)f(\()3065 2394 y Fn(Q)3143 2481 y Fp(i)p Fo(2)p Fp(S)3273 2456 y Fq(X)3332 2468 y Fp(i)3360 2456 y Fm(;)3397 2394 y Fn(Q)3476 2481 y Fp(i)p Fo(2)p Fp(S)3606 2456 y Fq(F)3666 2468 y Fp(i)3693 2456 y Fs(\).)47 b(W)-7 b(e)31 b(also)2130 2556 y(extend)c(the)g (uniform)g(reference)e(measure)h Fm(\025)d Fs(=)3681 2494 y Fn(Q)3759 2581 y Fp(i)p Fo(2)p Fp(S)3890 2556 y Fm(\025)3938 2568 y Fp(i)3992 2556 y Fs(on)2130 2656 y(\(\012)p Fm(;)14 b Fq(F)8 b Fs(\).)37 b(As)25 b(b)r(efore)h(w)n(e)f (restrict)g(ourselv)n(es)e(to)j(pairwise)e(p)r(o-)2130 2755 y(ten)n(tials.)45 b(W)-7 b(e)30 b(assume)g(that)g(the)h(n)n(um)n (b)r(er)f(of)g(neigh)n(b)r(ors)f(at)2130 2855 y(an)n(y)e(no)r(de)i(is)f (\014nite)g(and)g(hence)g(for)g(an)n(y)f(\003)d Fq(2)g Fl(S)c Fs(the)28 b(energy)2130 2954 y Fm(H)2206 2924 y Fi(\010)2199 2977 y(\003)2257 2954 y Fs(\()p Fm(!)s Fs(\))c(=)2487 2892 y Fn(P)2575 2979 y Fp(A)p Fo(2)p Fj(S)-10 b Fp(;)21 b(A)p Fo(\\)p Fi(\003)p Fo(6)p Fi(=)p Fo(;)2992 2954 y Fs(\010)3052 2966 y Fp(A)3106 2954 y Fs(\()p Fm(!)s Fs(\))28 b(exists.)2130 3104 y(Because)20 b(there)g(are)g(a)g(coun)n(tably)g(in\014nite)i(n)n(um)n(b)r(er)f(of)f (no)r(des)2130 3204 y(w)n(e)i(cannot)f(compute)i(the)f(partition)g (function)g(b)n(y)g(summing)2130 3303 y(o)n(v)n(er)k(all)i(no)r(des.)37 b(But)28 b(w)n(e)f(can)h(discuss)f(the)h(partition)g(func-)2130 3403 y(tion)i(when)g(conditioned)g(on)f(a)h(particular)e(b)r(oundary)-7 b(.)43 b(De-)2130 3502 y(\014ne)33 b(the)g(partition)f(function)h(in)g (\003)e Fq(2)g Fl(S)24 b Fs(for)32 b(the)h(p)r(oten)n(tial)2130 3602 y(\010,)28 b(b)r(oundary)f Fm(!)2667 3617 y Fp(S)s Fo(n)p Fi(\003)2794 3602 y Fs(,)g(and)h(reference)f(measure)f Fm(\025)i Fs(to)g(b)r(e)2500 3796 y Fm(Z)2563 3761 y Fi(\010)2557 3816 y(\003)2615 3796 y Fs(\()p Fm(!)s Fs(\))2760 3771 y Fo(4)2757 3822 y Fs(=)2869 3717 y Fn(X)2845 3895 y Fp(\020)t Fo(2)p Fi(\012)2971 3903 y Fh(\003)3026 3796 y Fm(e)3065 3761 y Fo(\000)p Fp(H)3175 3736 y Fh(\010)3171 3778 y(\003)3220 3761 y Fi(\()p Fp(\020)t(;!)3342 3772 y Fg(S)r Ff(n)p Fh(\003)3451 3761 y Fi(\))3481 3796 y Fm(\025)3529 3808 y Fi(\003)3579 3796 y Fs(\()p Fm(\020)6 b Fs(\))p Fm(:)2130 4049 y Ft(De\014nition)31 b(4.1)40 b Fk(Given)31 b(a)f(p)l(otential)h Fs(\010)p Fk(,)g Fm(!)26 b Fq(2)e Fs(\012)p Fk(,)30 b(and)g Fs(\003)24 b Fq(2)2130 4149 y Fl(S)m Fm(:)g Fk(Then)30 b(the)g(me)l(asur)l(e)2550 4365 y Fm(\015)2598 4331 y Fi(\010)2593 4386 y(\003)2649 4365 y Fs(\()p Fq(\001)g(j)g Fm(!)s Fs(\))2899 4341 y Fo(4)2897 4392 y Fs(=)2994 4309 y Fm(e)3033 4279 y Fo(\000)p Fp(H)3143 4253 y Fh(\010)3139 4295 y(\003)3188 4279 y Fi(\()p Fo(\001)p Fp(;)f(!)3325 4290 y Fg(S)r Ff(n)p Fh(\003)3435 4279 y Fi(\))3465 4309 y Fm(\025)3513 4321 y Fi(\003)3563 4309 y Fs(\()p Fq(\001)p Fs(\))p 2994 4346 657 4 v 3206 4424 a Fm(Z)3269 4396 y Fi(\010)3263 4449 y(\003)3320 4424 y Fs(\()p Fm(!)s Fs(\))2130 4583 y Fk(is)40 b(c)l(al)t(le)l(d)h(the)f Fs(Gibbs)e(distribution)h(in)f (\003)g(with)h(b)r(oundary)2130 4682 y Fm(!)2182 4697 y Fp(S)s Fo(n)p Fi(\003)2340 4682 y Fs(and)30 b(p)r(oten)n(tial)g (\010.)45 b Fk(F)-6 b(urthermor)l(e)33 b Fm(\015)3516 4652 y Fi(\010)3594 4682 y Fs(=)27 b Fq(f)p Fm(\015)3771 4694 y Fi(\003)3820 4682 y Fq(g)3862 4694 y Fi(\003)p Fo(2)p Fj(S)4021 4682 y Fk(is)2130 4782 y(c)l(al)t(le)l(d)k(the)f Fs(Gibbsian)e(sp)r(eci\014cation)f(for)g(\010.)2130 4959 y(Giv)n(en)39 b(a)g(Gibbsian)g(sp)r(eci\014cation,)j(whic)n(h)d(is)g(a) g(lo)r(cal)f(de-)2130 5058 y(scription)g(of)h(a)f(measure,)j(w)n(e)d (can)h(ask)e(ho)n(w)i(man)n(y)f(mea-)2130 5158 y(sures)c(are)f (consisten)n(t)h(with)h(it.)57 b(De\014ne)35 b(the)g(set)f(of)h(Gibbs) 2130 5258 y(measures)26 b(for)h(the)h(p)r(oten)n(tial)g(\010)g(to)f(b)r (e)2139 5425 y Fm(G)p Fs(\()p Fm(\015)2284 5391 y Fi(\010)2335 5425 y Fs(\))2454 5401 y Fo(4)2451 5452 y Fs(=)2598 5425 y Fq(f)p Fm(\026)c Fq(2)g(P)7 b Fs(\(\012)p Fm(;)14 b Fq(F)8 b Fs(\))51 b(:)g Fm(\026)p Fs(\()p Fm(A)28 b Fq(j)g(F)3493 5437 y Fi(\003)3538 5421 y Fg(c)3573 5425 y Fs(\))c(=)e Fm(\015)3764 5391 y Fi(\010)3759 5446 y(\003)3815 5425 y Fs(\()p Fm(A)29 b Fq(j)e(\001)p Fs(\))2709 5550 y Fm(\026)19 b Fq(\000)f Fm(a:s:)55 b Fq(8)p Fm(A)22 b Fq(2)i(F)63 b Fs(and)27 b(\003)c Fq(2)g Fl(S)n Fq(g)o Fm(:)p eop %%Page: 5 5 5 4 bop 30 83 a Fs(The)28 b(follo)n(wing)f(prop)r(osition)g(giv)n(es)f (us)i(an)g(implicit)g(c)n(harac-)30 183 y(terization)f(of)g(the)h (elemen)n(ts)g(in)g Fm(G)p Fs(\()p Fm(\015)1223 153 y Fi(\010)1274 183 y Fs(\).)30 357 y Ft(Prop)s(osition)i(4.1)41 b Fm(\026)j Fq(2)g Fm(G)p Fs(\()p Fm(\015)1048 327 y Fi(\010)1100 357 y Fs(\))d Fk(if)h(and)g(only)g(if)g Fm(\026\015)1820 327 y Fi(\010)1815 380 y(\003)1915 357 y Fs(=)30 457 y Fm(\026;)i Fq(8)p Fs(\003)21 b Fq(2)j Fl(S)30 632 y Ft(Pro)s(of:)36 b Fs(See)28 b([1)o(].)p Fb(2)30 781 y Fs(The)49 b(equations)e Fm(\026\015)712 751 y Fi(\010)707 804 y(\003)821 781 y Fs(=)58 b Fm(\026;)k Fq(8)p Fs(\003)57 b Fq(2)h Fl(S)40 b Fs(are)48 b(called)g(the)30 881 y Fk(DLR)24 b(e)l(quations)e Fs(after)f(Dobrushin,)i(Langford,)f (and)g(Ruelle.)30 980 y(They)27 b(state)h(that)318 1155 y Fm(\026\015)416 1121 y Fi(\010)411 1176 y(\003)467 1155 y Fs(\()p Fq(\001)g(j)g Fm(!)s Fs(\))23 b(=)798 1076 y Fn(X)836 1251 y Fp(!)932 1155 y Fm(\026)p Fs(\()p Fm(!)s Fs(\))p Fm(\015)1149 1121 y Fi(\010)1144 1176 y(\003)1200 1155 y Fs(\()p Fq(\001)28 b(j)g Fm(!)s Fs(\))23 b(=)g Fm(\026)p Fs(\()p Fq(\001)p Fs(\))p Fm(:)30 1388 y Fs(This)h(is)g(a)g(restatemen)n(t)g(of)g(the)h(fact)g(that)f(the)h (iterated)f(con-)30 1488 y(ditional)38 b(exp)r(ectation)f(equals)h(the) g(unconditional)f(exp)r(ec-)30 1587 y(tation.)66 b(The)37 b(DLR)h(equations)e(will)h(pla)n(y)g(a)g(v)n(ery)f(imp)r(or-)30 1687 y(tan)n(t)26 b(role)e(in)i(our)f(subsequen)n(t)g(analysis.)35 b(One)25 b(can)g(think)h(of)30 1787 y Fm(G)p Fs(\()p Fm(\015)175 1756 y Fi(\010)227 1787 y Fs(\))21 b(as)g(the)g(set)h(of)f (all)g(measures)e(lo)r(cally)i(consisten)n(t)g(with)30 1886 y(the)33 b(sp)r(eci\014ed)g(p)r(oten)n(tial)g(\010)p Fm(:)g Fs(Said)f(another)g(w)n(a)n(y)f Fm(G)p Fs(\()p Fm(\015)1807 1856 y Fi(\010)1859 1886 y Fs(\))i(is)30 1986 y(the)39 b(set)g(of)f(all)h(measures)e(preserv)n(ed)g(under)i(a)f (coun)n(table)30 2085 y(n)n(um)n(b)r(er)27 b(of)h(prop)r(er)f (probabilit)n(y)f(k)n(ernels:)36 b Fq(f)p Fm(\015)1517 2055 y Fi(\010)1512 2108 y(\003)1567 2085 y Fs(\()p Fq(\001)29 b(j)e Fm(!)s Fs(\))p Fq(g)1830 2097 y Fi(\003)p Fo(2)p Fj(S)1956 2085 y Fm(:)30 2235 y Fs(F)-7 b(or)27 b(the)h(pairwise)f(p)r (oten)n(tial,)h(\010,)f(one)h(can)f(sho)n(w)g(that)h(eac)n(h)30 2335 y Fm(\026)23 b Fq(2)g Fm(G)p Fs(\()p Fm(\015)326 2304 y Fi(\010)378 2335 y Fs(\))28 b(is)g(a)f Fk(Markov)k(\014eld.)38 b Fs(Sp)r(eci\014cally)30 2497 y Fm(\026)p Fs(\()p Fm(!)164 2509 y Fi(\003)233 2497 y Fq(j)19 b(F)335 2509 y Fi(\003)380 2493 y Fg(c)416 2497 y Fs(\))k(=)g Fm(\026)p Fs(\()p Fm(!)693 2509 y Fi(\003)761 2497 y Fq(j)d(F)864 2509 y Fp(@)t Fi(\003)952 2497 y Fs(\))39 b Fm(\026)r Fq(\000)r Fm(a:s:)f Fq(8)p Fm(!)1408 2509 y Fi(\003)1479 2497 y Fq(2)23 b Fs(\012)1617 2509 y Fi(\003)1706 2497 y Fq(8)p Fs(\003)e Fq(2)j Fl(S)m Fm(:)30 2660 y Fs(This)41 b(is)f(sometimes)g (called)h(the)g Fk(lo)l(c)l(al)h(Markov)i(pr)l(op)l(erty.)30 2760 y Fs(W)-7 b(e)36 b(will)h(discuss)e(the)h Fk(glob)l(al)j(Markov)g (pr)l(op)l(erty)e Fs(when)f(w)n(e)30 2859 y(discuss)25 b(Mark)n(o)n(v)d(c)n(hains)i(on)h(trees)g(in)g(the)g(next)g (subsection.)30 3009 y Ft(Characterization)33 b(of)f Fm(G)p Fs(\()p Fm(\015)1012 2979 y Fi(\010)1064 3009 y Fs(\))30 3158 y(The)c(set)g Fm(G)p Fs(\()p Fm(\015)476 3128 y Fi(\010)527 3158 y Fs(\))h(can)e(either)h(b)r(e)g(empt)n(y)-7 b(,)28 b(con)n(tain)f(one)h(mea-)30 3258 y(sure,)41 b(or)c(con)n(tain)h (an)g(in\014nite)i(n)n(um)n(b)r(er)e(of)g(measures.)69 b(A)30 3357 y(p)r(oten)n(tial)24 b(is)h(said)f(to)g(exhibit)h(a)f Fk(phase)k(tr)l(ansition)c Fs(if)h(the)g(set)30 3457 y Fq(j)p Fm(G)p Fs(\()p Fm(\015)198 3427 y Fi(\010)250 3457 y Fs(\))p Fq(j)j Fm(>)f Fs(1)p Fm(:)k Fs(Phase)e(transitions)h (are)f(a)h(remark)-5 b(able)29 b(phe-)30 3557 y(nomena.)56 b(F)-7 b(or)34 b(a)g(giv)n(en)f(lo)r(cal)h(sp)r(eci\014cation)g(w)n(e)f (can)h(ha)n(v)n(e)30 3656 y(v)n(ery)26 b(di\013eren)n(t)i(global)f(b)r (eha)n(viors.)35 b(F)-7 b(or)27 b(a)h(pro)r(of)f(of)g(the)h(fol-)30 3756 y(lo)n(wing)f(prop)r(osition)f(see)h([1].)30 3931 y Ft(Prop)s(osition)j(4.2)41 b Fk(L)l(et)22 b Fs(\010)g Fk(b)l(e)h(an)g(admissible,)j(p)l(airwise)f(p)l(o-)30 4030 y(tential)h(de\014ne)l(d)g(on)g(the)f(c)l(ountably)h(in\014nite)g (set)f(of)i(no)l(des)f Fm(S)5 b Fk(.)30 4130 y(Ther)l(e)30 b(exists)f(at)g(le)l(ast)g(one)g(Gibbs)h(me)l(asur)l(e)f(for)h(an)f (admis-)30 4230 y(sible)i(p)l(airwise)g(p)l(otential)g Fs(\010)p Fk(.)30 4404 y Fs(W)-7 b(e)25 b(ha)n(v)n(e)f(just)i(sho)n(wn) e(that)h Fm(G)p Fs(\()p Fm(\015)1092 4374 y Fi(\010)1144 4404 y Fs(\))g(is)g(nonempt)n(y)-7 b(.)36 b(W)-7 b(e)26 b(no)n(w)30 4504 y(discuss)d(its)g(structure.)35 b(Clearly)22 b(it)h(is)g(a)g(con)n(v)n(ex)e(set)i(b)r(ecause)30 4604 y(the)k(con)n(v)n(ex)d(com)n(bination)i(of)g(t)n(w)n(o)f(elemen)n(ts)h (in)h Fm(G)p Fs(\()p Fm(\015)1741 4573 y Fi(\010)1792 4604 y Fs(\))g(will)30 4703 y(certainly)35 b(b)r(e)i(a)e(mem)n(b)r(er)h (of)g Fm(G)p Fs(\()p Fm(\015)1156 4673 y Fi(\010)1208 4703 y Fs(\))p Fm(:)g Fs(T)-7 b(o)36 b(pro)n(v)n(e)e(this)j(it)f(is)30 4803 y(enough)29 b(to)g(sho)n(w)f(that)h(the)h(con)n(v)n(ex)e(com)n (bination)g(satis\014es)30 4902 y(the)g(DLR)g(equations.)30 5052 y(F)-7 b(urthermore)35 b(w)n(e)i(can)f(c)n(haracterize)e(the)j (extreme)f(p)r(oin)n(ts)30 5151 y(of)c(the)g(con)n(v)n(ex)f(set)g Fm(G)p Fs(\()p Fm(\015)831 5121 y Fi(\010)883 5151 y Fs(\))p Fm(:)h Fs(Recall)g(an)f(elemen)n(t)h(of)g(a)g(con-)30 5251 y(v)n(ex)j(set)g(is)g Fk(extr)l(eme)g Fs(if)h(it)f(cannot)g(b)r(e) h(represen)n(ted)e(as)h(the)30 5351 y(con)n(v)n(ex)23 b(com)n(bination)g(of)h(other)f(elemen)n(ts)h(in)g(the)h(set.)35 b(Eac)n(h)30 5450 y(extremal)f(elemen)n(t)g(of)h Fm(G)p Fs(\()p Fm(\015)941 5420 y Fi(\010)993 5450 y Fs(\))f(is)h(called)f(a)g Fk(phase.)60 b Fs(De\014ne)30 5550 y(the)28 b Fk(tail)g Fs(sigma)f(\014eld)h(to)f(b)r(e)h Fq(T)1040 5526 y Fo(4)1037 5577 y Fs(=)1124 5550 y Fq(\\)1179 5562 y Fi(\003)p Fo(2)p Fj(S)1306 5550 y Fq(F)1366 5562 y Fi(\003)1411 5546 y Fg(c)1447 5550 y Fm(:)2130 83 y Ft(Prop)s(osition)i(4.3)41 b Fk(L)l(et)d Fm(\026)j Fq(2)f Fm(G)p Fs(\()p Fm(\015)3293 53 y Fi(\010)3345 83 y Fs(\))f Fk(then)g(the)h(fol)t(lowing)2130 183 y(ar)l(e)30 b(e)l(quivalent)2144 407 y(\(1\))42 b Fm(\026)30 b Fk(is)g(extr)l(eme)2144 589 y(\(2\))42 b Fm(\026)30 b Fk(is)g(trivial)h(on)f(the)g(tail)g(sigma)h(\014eld)f Fq(T)2144 771 y Fk(\(3\))42 b(for)31 b(al)t(l)f(cylinder)i(events)d Fm(A)2510 962 y Fs(lim)2506 1016 y Fi(\003)p Fo(2)p Fj(S)2689 962 y Fs(sup)2643 1032 y Fp(B)s Fo(2F)2789 1042 y Fh(\003)2827 1030 y Fg(c)2875 962 y Fq(j)p Fm(\026)p Fs(\()p Fm(A)19 b Fq(\\)g Fm(B)t Fs(\))g Fq(\000)f Fm(\026)p Fs(\()p Fm(A)p Fs(\))p Fm(\026)p Fs(\()p Fm(B)t Fs(\))p Fq(j)24 b Fs(=)f(0)2130 1253 y Ft(Pro)s(of:)36 b Fs(See)28 b(prop)r(ositions)e (7.7)h(and)g(7.9)g(of)h([1)o(].)37 b Fb(2)2130 1402 y Fs(An)25 b(extremal)e(measure)h(is)g(a)g(mixing)g(measure)f(in)i(the)g (sense)2130 1502 y(of)e(p)r(oin)n(t)f(\(3\).)36 b(If)23 b(there)f(is)h(a)f(unique)h(measure)e Fm(G)p Fs(\()p Fm(\015)3752 1472 y Fi(\010)3804 1502 y Fs(\))i(=)g Fq(f)p Fm(\026)p Fq(g)2130 1602 y Fs(then)40 b(that)f Fm(\026)h Fs(is)f(necessarily)e(extremal,)42 b(tail-trivial,)f(and)2130 1701 y(mixing.)2130 1924 y Ft(4.2)94 b(Mark)m(o)m(v)34 b(Fields)c(on)i(T)-8 b(rees:)42 b(Boundary)33 b(La)m(ws,)2347 2023 y(Mark)m(o)m(v)h(Chains,)d(and)h(Limits)2130 2205 y Fs(W)-7 b(e)32 b(ha)n(v)n(e)e(discussed)h(Gibbs)h(measures)f (de\014ned)g(on)h(coun)n(t-)2130 2305 y(able)i(sets)f(of)h(no)r(des.)56 b(W)-7 b(e)35 b(no)n(w)e(restrict)g(our)g(atten)n(tion)h(to)2130 2404 y(Gibbs)23 b(measures)e(de\014ned)h(on)g(in\014nite)h(trees.)35 b(W)-7 b(e)22 b(will)h(sho)n(w)2130 2504 y(that)f(if)h(LBP)e(con)n(v)n (erges)f(then)i(the)h(asso)r(ciated)e(measures)f(on)2130 2604 y(the)31 b(computation)f(tree)f(m)n(ust)i(con)n(v)n(erge)d(to)i (an)g(elemen)n(t)g(of)2130 2703 y Fm(G)p Fs(\()p Fm(\015)2275 2673 y Fi(\010)2327 2703 y Fs(\).)2130 2853 y Ft(Limiting)f(Gibbs)i (Measures)h(on)f(T)-8 b(rees)2130 3002 y Fs(Ho)n(w)35 b(do)f(w)n(e)h(construct)f(an)h(in\014nite)h(v)n(olume)e(Gibbs)i(mea-) 2130 3102 y(sure?)g(So)26 b(far)f(w)n(e)h(only)f(ha)n(v)n(e)g(an)h (implicit)h(c)n(haracterization)2130 3201 y(via)19 b(the)i(DLR)f (equations.)33 b(F)-7 b(or)20 b(Gibbs)g(measures)e(de\014ned)i(on)2130 3301 y(in\014nite)27 b(trees)e(w)n(e)h(will)h(sho)n(w)e(that)h(the)h (measures)e(can)g(arise)2130 3401 y(as)c(the)h(w)n(eak)e(limit)i(of)f (a)g(sequence)g(of)h(Gibbs)f(measures)g(with)2130 3500 y(\014xed)28 b(b)r(oundary)e(conditions.)2130 3650 y(Let)41 b(\010)f(b)r(e)h(a)f(pairwise)f(p)r(oten)n(tial)h(whose)g(Mark)n(o)n(v) e(graph)2130 3749 y(\()p Fm(S)2218 3719 y Fi(\010)2270 3749 y Fm(;)14 b(E)2373 3719 y Fi(\010)2424 3749 y Fs(\))29 b(is)f(a)f(coun)n(tably)h(in\014nite)h(tree.)38 b(Let)28 b Fm(T)3702 3761 y Fp(n)3771 3749 y Fq(\032)23 b Fm(S)3915 3719 y Fi(\010)3995 3749 y Fs(b)r(e)2130 3849 y(the)k(set)f(of)h(no)r (des)f(in)h(the)g(tree)f(that)h(are)f(a)g(distance)g(of)h Fm(n)f Fs(or)2130 3948 y(less)i(from)f(the)i(ro)r(ot.)37 b(Recall)28 b Fm(L)3143 3960 y Fp(n)3212 3948 y Fq(\032)23 b Fm(T)3349 3960 y Fp(n)3422 3948 y Fs(is)28 b(the)g(set)g(of)g(no)r (des)2130 4048 y(that)g(are)e(exactly)h(a)h(distance)f Fm(n)g Fs(a)n(w)n(a)n(y)f(from)h(the)h(ro)r(ot.)2130 4198 y(F)-7 b(rom)39 b(the)g(original)f(p)r(oten)n(tial)h(\010)j(=)g Fq(f)p Fs(\010)3499 4210 y Fp(A)3552 4198 y Fq(g)d Fs(w)n(e)f(will)i (no)n(w)2130 4297 y(de\014ne)34 b(a)f(new)g(sequence)g(of)h(p)r(oten)n (tials.)54 b(F)-7 b(or)33 b(eac)n(h)f Fm(n)h Fq(\025)f Fs(1)2130 4397 y(de\014ne)c(\010)2430 4367 y Fp(T)2469 4375 y Fg(n)2537 4397 y Fs(=)23 b Fq(f)p Fs(\010)2727 4360 y Fp(T)2766 4368 y Fg(n)2727 4421 y Fp(A)2810 4397 y Fq(g)k Fs(b)n(y)2290 4696 y(\010)2350 4659 y Fp(T)2389 4667 y Fg(n)2350 4720 y Fp(A)2457 4696 y Fs(=)2544 4526 y Fn(8)2544 4601 y(<)2544 4750 y(:)2805 4590 y Fs(\010)2865 4602 y Fp(A)2919 4590 y Fm(;)285 b Fs(if)28 b Fm(A)19 b Fq(\\)g Fm(T)3507 4602 y Fp(n)p Fo(\000)p Fi(1)3659 4590 y Fq(6)p Fs(=)k Fq(;)p Fs(;)2660 4701 y(\010)2720 4661 y Fp(bd;n)2720 4725 y(A)2867 4701 y Fs(+)18 b(\010)3010 4713 y Fp(A)3064 4701 y Fm(;)83 b Fs(if)28 b Fm(A)23 b Fq(\032)g Fm(L)3476 4713 y Fp(n)3521 4701 y Fm(;)41 b Fq(j)p Fm(A)p Fq(j)24 b Fs(=)e(1;)2841 4800 y(0)p Fm(;)431 b Fs(otherwise.)2130 5010 y(where)21 b(\010)2424 4980 y Fp(bd;n)2578 4986 y Fo(4)2575 5037 y Fs(=)2663 5010 y Fq(f)p Fs(\010)2765 4970 y Fp(bd;n)2765 5034 y(A)2893 5010 y Fq(g)g Fs(represen)n(ts)f(added)h(self-p)r(oten)n(tials)2130 5125 y(at)h(the)g(lea)n(v)n(es)e(of)i(the)h Fm(T)2871 5137 y Fp(n)2937 5125 y Fs(tree.)35 b(If)22 b(\010)3271 5085 y Fp(bd;n)3271 5149 y(A)3423 5125 y Fs(=)h(0)e(for)h(all)f Fm(A)j Fq(\032)e Fm(L)4035 5137 y Fp(n)2130 5225 y Fs(then)28 b(w)n(e)f(call)g(the)h(b)r(oundary)f(a)g Fk(fr)l(e)l(e)j(b)l(oundary.) 38 b Fs(Note)28 b(that)2130 5333 y Fm(\015)2178 5303 y Fi(\010)2225 5278 y Fg(T)2260 5286 y(n)2173 5356 y Fp(T)2212 5364 y Fg(n)2309 5333 y Fs(\()p Fm(A)37 b Fq(j)h Fm(!)s Fs(\))f(is)g(indep)r(enden)n(t)h(of)f Fm(!)j Fs(for)d Fm(A)i Fq(2)g(F)3786 5345 y Fp(T)3825 5353 y Fg(n)3870 5333 y Fs(.)66 b(F)-7 b(or)2130 5442 y(eac)n(h)33 b(\010)2383 5412 y Fp(T)2422 5420 y Fg(n)2500 5442 y Fs(w)n(e)g(can)h(write)f(the)h (unique)f(Gibbs)h(measure)f(as)2130 5550 y Fm(\026)2180 5520 y Fi(\010)2227 5495 y Fg(T)2262 5503 y(n)2334 5550 y Fs(=)23 b Fm(\025)2470 5562 y Fp(T)2518 5546 y Fg(c)2509 5579 y(n)2554 5550 y Fm(\015)2602 5520 y Fi(\010)2649 5495 y Fg(T)2684 5503 y(n)2597 5573 y Fp(T)2636 5581 y Fg(n)2733 5550 y Fs(.)p eop %%Page: 6 6 6 5 bop 30 84 a Fs(In)49 b(the)g(con)n(text)f(of)h(the)g(computation)f (tree)g Fm(\026)1657 53 y Fi(\010)1704 28 y Fg(T)1739 36 y(n)1837 84 y Fs(rep-)30 183 y(resen)n(ts)38 b(the)h(measure)f(on)h (the)g(in\014nite)g(tree)g(corresp)r(ond-)30 283 y(ing)54 b(to)g Fm(n)g Fs(iterations)f(of)h(LBP)g(when)g(initialized)h(with)30 382 y(the)44 b(self-p)r(oten)n(tials)e(\010)793 352 y Fp(bd;n)922 382 y Fs(.)84 b(W)-7 b(e)44 b(can)f(relate)f(the)i(c)n (hoice)30 482 y(of)50 b(\010)207 452 y Fp(bd;n)385 482 y Fs(to)g(the)g(c)n(hoice)f(of)h(b)r(oundary)f(self-p)r(oten)n(tials,) 30 582 y Fq(f)p Fs(\010)132 537 y Fp(s)163 545 y Fg(i)189 537 y Fo(!)p Fp(s)286 545 y Fg(j)132 591 y Fp(s)163 599 y Fg(i)322 582 y Fq(g)364 610 y Fi(\()p Fp(s)421 618 y Fg(i)447 610 y Fp(;s)498 618 y Fg(j)529 610 y Fi(\))p Fo(2)609 595 y Fp(~)600 610 y(E)656 582 y Fs(,)27 b(in)h(the)g(LBP)f (algorithm.)30 742 y(W)-7 b(e)34 b(are)f(in)n(terested)h(in)g (conditions)f(that)h(insure)g(the)g(mea-)30 841 y(sures,)21 b Fq(f)p Fm(\026)348 811 y Fi(\010)395 786 y Fg(T)430 794 y(n)478 841 y Fq(g)520 853 y Fp(n)p Fo(\025)p Fi(1)650 841 y Fs(,)h(con)n(v)n(erge)17 b(to)j(a)g(limiting)h(measure.)33 b(The)30 941 y(next)27 b(prop)r(osition)f(states)h(that)g(if)h(they)f (con)n(v)n(erge)e(to)h(a)h(lim-)30 1041 y(iting)k(measure)f(then)i (that)f(measure)f(m)n(ust)h(b)r(e)g(an)g(elemen)n(t)30 1140 y(of)e Fm(G)p Fs(\()p Fm(\015)271 1110 y Fi(\010)323 1140 y Fs(\).)41 b(Hence)30 b(examining)e(the)h(structure)g(of)g Fm(G)p Fs(\()p Fm(\015)1811 1110 y Fi(\010)1863 1140 y Fs(\))g(is)30 1240 y(useful)f(for)f(determining)h(con)n(v)n(ergence)d (of)i(LBP)-7 b(.)30 1414 y Ft(Prop)s(osition)30 b(4.4)41 b Fk(Each)36 b(subse)l(quential)g(limit)f(of)i(the)e(se-)30 1522 y(quenc)l(e)29 b(of)i(me)l(asur)l(es)e Fq(f)p Fm(\026)844 1492 y Fi(\010)891 1467 y Fg(T)926 1475 y(n)975 1522 y Fq(g)1017 1534 y Fp(n)p Fo(\025)p Fi(1)1176 1522 y Fk(b)l(elongs)i(to)e Fm(G)p Fs(\()p Fm(\015)1705 1492 y Fi(\010)1757 1522 y Fs(\))p Fk(.)30 1696 y Ft(Pro)s(of:)47 b Fs(W)-7 b(e)34 b(sk)n(etc)n(h)e(the)h(pro)r(of.)53 b(F)-7 b(or)32 b(full)i(details)f(see)f([3].)30 1796 y(Note)h(that)g(for)g(eac)n(h)f(\003)g Fq(2)g Fl(S)25 b Fs(there)32 b(is)h(an)g Fm(n)g Fs(large)f(enough)30 1904 y(suc)n(h)27 b(that)h Fm(\015)445 1874 y Fi(\010)492 1848 y Fg(T)527 1856 y(n)440 1927 y Fi(\003)576 1904 y Fs(\()p Fq(\001)g(j)f Fm(!)s Fs(\))c(=)g Fm(\015)955 1874 y Fi(\010)950 1927 y(\003)1006 1904 y Fs(\()p Fq(\001)28 b(j)g Fm(!)s Fs(\).)30 2053 y(W)-7 b(e)31 b(need)g(to)g(sho)n(w)f(that) h(the)g(subsequen)n(tial)g(limits)g(of)g(the)30 2161 y(sequence)d(of)g(measures)f Fq(f)p Fm(\026)919 2131 y Fi(\010)966 2106 y Fg(T)1001 2114 y(n)1050 2161 y Fq(g)1092 2173 y Fp(n)p Fo(\025)p Fi(1)1250 2161 y Fs(b)r(elong)h(to)g Fm(G)p Fs(\(\010\))p Fm(:)h Fs(Let)30 2280 y Fm(\026)i Fs(b)r(e)h(a)f(subsequen)n(tial)g(limit)h(where)f(lim)1379 2292 y Fp(k)q Fo(!1)1566 2280 y Fm(\026)1616 2250 y Fi(\010)1663 2221 y Fg(T)1698 2229 y(n)1735 2244 y(k)1813 2280 y Fs(=)e Fm(\026:)30 2380 y Fs(W)-7 b(e)29 b(will)f(sho)n(w)g(that)h Fm(\026)f Fs(satis\014es)g(the)h(DLR)f(equations.)39 b(Let)30 2479 y(\003)23 b Fq(2)g Fl(S)c Fs(and)27 b(let)h Fm(A)g Fs(b)r(e)g(a)f(cylinder)h(ev)n(en)n(t.)36 b(Then)30 2579 y Fq(j)p Fm(\026\015)151 2549 y Fi(\010)146 2602 y(\003)202 2579 y Fs(\()p Fm(A)p Fs(\))20 b Fq(\000)e Fm(\026)p Fs(\()p Fm(A)p Fs(\))p Fq(j)113 2764 y Fs(=)110 b(lim)261 2818 y Fp(k)q Fo(!1)444 2764 y Fq(j)p Fm(\025)515 2776 y Fp(T)563 2759 y Fg(c)554 2793 y(n)591 2808 y(k)635 2764 y Fm(\015)683 2729 y Fi(\010)730 2700 y Fg(T)765 2708 y(n)802 2723 y(k)678 2784 y Fp(T)717 2792 y Fg(n)754 2807 y(k)850 2764 y Fs(\()p Fm(\015)930 2729 y Fi(\010)925 2784 y(\003)982 2764 y Fs(\()p Fm(A)p Fs(\)\))19 b Fq(\000)f Fm(\025)1290 2776 y Fp(T)1338 2759 y Fg(c)1329 2793 y(n)1366 2808 y(k)1411 2764 y Fm(\015)1459 2729 y Fi(\010)1506 2700 y Fg(T)1541 2708 y(n)1578 2723 y(k)1454 2784 y Fp(T)1493 2792 y Fg(n)1530 2807 y(k)1626 2764 y Fs(\()p Fm(A)p Fs(\))p Fq(j)113 2951 y Fs(=)110 b(lim)261 3005 y Fp(k)q Fo(!1)444 2951 y Fq(j)p Fm(\025)515 2963 y Fp(T)563 2947 y Fg(c)554 2980 y(n)591 2995 y(k)635 2951 y Fm(\015)683 2917 y Fi(\010)730 2888 y Fg(T)765 2896 y(n)802 2911 y(k)678 2972 y Fp(T)717 2980 y Fg(n)754 2995 y(k)850 2951 y Fs(\()p Fm(\015)930 2917 y Fi(\010)925 2972 y(\003)982 2951 y Fs(\()p Fm(A)p Fs(\)\))19 b Fq(\000)f Fm(\025)1290 2963 y Fp(T)1338 2947 y Fg(c)1329 2980 y(n)1366 2995 y(k)1411 2951 y Fm(\015)1459 2917 y Fi(\010)1506 2888 y Fg(T)1541 2896 y(n)1578 2911 y(k)1454 2972 y Fp(T)1493 2980 y Fg(n)1530 2995 y(k)1626 2951 y Fs(\()p Fm(\015)1706 2917 y Fi(\010)1753 2888 y Fg(T)1788 2896 y(n)1825 2911 y(k)1701 2972 y Fi(\003)1873 2951 y Fs(\()p Fm(A)p Fs(\)\))p Fq(j)113 3100 y Fs(=)83 b(0)30 3262 y(where)27 b(the)h(second)g (equalit)n(y)f(holds)g(for)g Fm(k)k Fs(large)c(enough)g(so)30 3361 y(that)h(\003)23 b Fq(\032)f Fm(T)427 3373 y Fp(n)468 3382 y Fg(k)508 3361 y Fs(.)37 b Fb(2)30 3511 y Ft(Mark)m(o)m(v)c (Chains)f(and)g(Boundary)h(La)m(ws)30 3660 y Fs(W)-7 b(e)35 b(ha)n(v)n(e)e(just)i(sho)n(wn)f(that)h(eac)n(h)e(subsequen)n (tial)h(limit)h(of)30 3768 y(the)19 b(sequence)g(of)f(measures)g Fq(f)p Fm(\026)1025 3738 y Fi(\010)1072 3713 y Fg(T)1107 3721 y(n)1155 3768 y Fq(g)1197 3780 y Fp(n)p Fo(\025)p Fi(1)1346 3768 y Fs(b)r(elongs)g(to)h Fm(G)p Fs(\()p Fm(\015)1873 3738 y Fi(\010)1925 3768 y Fs(\).)30 3868 y(Here)40 b(w)n(e)g(describ)r(e)g(the)g(structure)g(of)g(the)h (subsequen)n(tial)30 3967 y(limits)24 b(in)g(terms)f(of)h(the)g(Mark)n (o)n(v)d(c)n(hains)i(de\014ned)h(in)g Fm(G)p Fs(\()p Fm(\015)1873 3937 y Fi(\010)1925 3967 y Fs(\).)30 4117 y(W)-7 b(e)33 b(are)g(giv)n(en)f(a)h(p)r(oten)n(tial)g(\010)g(with)g(a) g(coun)n(tably)f(in\014nite)30 4216 y(tree)27 b(Mark)n(o)n(v)f(graph)g (\()p Fm(S)822 4186 y Fi(\010)874 4216 y Fm(;)14 b(E)977 4186 y Fi(\010)1028 4216 y Fs(\).)37 b(Let)303 4378 y Fm(S)359 4343 y Fi(\010)354 4400 y(\()p Fp(i;j)s Fi(\))510 4353 y Fo(4)507 4404 y Fs(=)594 4378 y Fq(f)p Fm(k)26 b Fq(2)d Fm(S)56 b Fs(:)50 b Fm(d)p Fs(\()p Fm(k)s(;)14 b(j)5 b Fs(\))24 b(=)f Fm(d)p Fs(\()p Fm(k)s(;)14 b(i)p Fs(\))k(+)g(1)p Fq(g)30 4539 y Fs(b)r(e)29 b(the)h(set)f(of)g(no)r(des) g(in)g(the)g(\\past")f(of)h(the)h(directed)f(edge)30 4639 y(\()p Fm(i;)14 b(j)5 b Fs(\))28 b(including)f(the)h(no)r(de)g Fm(i)p Fs(.)30 4813 y Ft(De\014nition)j(4.2)40 b Fk(A)33 b(me)l(asur)l(e)g Fm(\026)1109 4783 y Fi(\010)1193 4813 y Fk(is)g(a)h Fs(Mark)n(o)n(v)29 b(c)n(hain)j Fk(on)30 4912 y(the)e(tr)l(e)l(e)f(if)314 5074 y Fm(\026)p Fs(\()p Fm(!)448 5086 y Fp(j)513 5074 y Fq(j)h(F)626 5093 y Fp(S)670 5073 y Fh(\010)667 5116 y(\()p Fg(i;j)r Fh(\))788 5074 y Fs(\))23 b(=)g Fm(\026)p Fs(\()p Fm(!)1065 5086 y Fp(j)1129 5074 y Fq(j)30 b(F)1242 5089 y Fo(f)p Fp(i)p Fo(g)1337 5074 y Fq(g)59 b Fm(\026)19 b Fq(\000)f Fm(a:s)30 5276 y Fk(for)31 b(al)t(l)f Fs(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)565 5255 y Fm(~)552 5276 y(E)618 5246 y Fi(\010)699 5276 y Fk(and)30 b Fm(!)912 5288 y Fp(j)970 5276 y Fq(2)24 b(X)1108 5288 y Fp(j)1143 5276 y Fk(.)30 5450 y Fs(One)29 b(can)g(sho)n(w)f(that)h(ev)n(ery)f(Mark)n(o)n(v)f(c)n(hain)i(on)g(the) g(tree)g(is)30 5550 y(a)e(Mark)n(o)n(v)e(\014eld)j(on)g(the)g(tree.)36 b(The)28 b(con)n(v)n(erse)d(though)i(do)r(es)2130 83 y(not)33 b(alw)n(a)n(ys)d(hold)j(\(see)f([1].\))52 b(Measures)31 b(that)i(are)e(Mark)n(o)n(v)2130 183 y(\014elds)23 b(are)g(often)g (called)g Fk(two-side)l(d)i Fs(whereas)d(measures)g(that)2130 282 y(are)27 b(Mark)n(o)n(v)e(c)n(hains)i(are)f(often)i(called)f Fk(one-side)l(d.)2130 465 y Ft(Prop)s(osition)j(4.5)41 b Fk(L)l(et)27 b Fs(\010)h Fk(b)l(e)g(a)g(p)l(airwise)h(p)l(otential)g (whose)2130 565 y(Markov)h(gr)l(aph)f(is)g(a)f(tr)l(e)l(e.)38 b(If)28 b Fm(\026)g Fk(is)h(an)f(extr)l(emal)g(element)g(of)2130 664 y Fm(G)p Fs(\()p Fm(\015)2275 634 y Fi(\010)2327 664 y Fs(\))i Fk(then)f(it)h(is)g(a)g(Markov)i(chain.)2130 847 y Ft(Pro)s(of:)k Fs(See)28 b(theorem)f(12.6)f(in)i([1].)37 b Fb(2)2130 996 y Fs(There)27 b(can)h(exist)f(Mark)n(o)n(v)f(c)n(hains) h(that)h(are)f(not)h(extremal.)2130 1096 y(Th)n(us)k(extremalit)n(y)f (alone)h(is)g(not)g(enough)f(to)h(c)n(haracterize)2130 1196 y(the)39 b(Mark)n(o)n(v)d(c)n(hains)i(in)h Fm(G)p Fs(\()p Fm(\015)3113 1165 y Fi(\010)3165 1196 y Fs(\).)70 b(It)38 b(turns)h(out,)i(though,)2130 1295 y(that)f(w)n(e)f(can)h(c)n (haracterize)d(eac)n(h)i(Mark)n(o)n(v)f(c)n(hain)h(b)n(y)h(the)2130 1395 y(use)35 b(of)g Fk(b)l(oundary)j(laws)p Fs(.)60 b(W)-7 b(e)35 b(will)h(then)f(sho)n(w)g(that)g(these)2130 1494 y(b)r(oundary)27 b(la)n(ws)f(are)h(related)g(to)h(the)g(messages)d (in)j(LBP)-7 b(.)2130 1644 y(First)27 b(de\014ne)h(for)f(eac)n(h)g Fq(f)p Fm(i;)14 b(j)5 b Fq(g)22 b(2)h Fm(E)3241 1614 y Fi(\010)3320 1644 y Fs(a)28 b Fk(tr)l(ansfer)h(matrix)2206 1904 y Fm(Q)2272 1919 y Fo(f)p Fp(i;j)s Fo(g)2418 1904 y Fs(\()p Fm(!)2502 1916 y Fp(i)2529 1904 y Fm(;)14 b(!)2618 1916 y Fp(j)2653 1904 y Fs(\))2711 1880 y Fo(4)2708 1931 y Fs(=)2796 1904 y Fm(e)2835 1840 y Fo(\000)2887 1759 y Fa(\022)2936 1840 y Fi(\010)2983 1851 y Ff(f)p Fg(i;j)r Ff(g)3116 1840 y Fi(\()p Fp(!)3184 1848 y Fg(i)3210 1840 y Fp(;!)3272 1848 y Fg(j)3303 1840 y Fi(\)+)3390 1794 y Fh(\010)3430 1811 y Ff(f)p Fg(i)p Ff(g)3517 1794 y Fh(\()p Fg(!)3576 1807 y(i)3603 1794 y Fh(\))p 3390 1827 236 3 v 3460 1861 a Ff(j)p Fg(@)s(i)p Ff(j)3635 1840 y Fi(+)3696 1794 y Fh(\010)3736 1811 y Ff(f)p Fg(j)r Ff(g)3828 1794 y Fh(\()p Fg(!)3887 1807 y(j)3918 1794 y Fh(\))p 3696 1827 245 3 v 3769 1861 a Ff(j)p Fg(@)s(j)r Ff(j)3951 1759 y Fa(\023)2130 2087 y Fs(W)-7 b(e)28 b(can)f(then)h (write)2285 2270 y Fm(\015)2328 2282 y Fi(\003)2377 2270 y Fs(\()p Fm(!)2461 2282 y Fi(\003)2538 2270 y Fq(j)g Fm(!)s Fs(\))23 b(=)g Fm(Z)2844 2282 y Fi(\003)2893 2270 y Fs(\()p Fm(!)s Fs(\))3012 2235 y Fo(\000)p Fi(1)3221 2191 y Fn(Y)3115 2373 y Fo(f)p Fp(i;j)s Fo(g\\)p Fi(\003)p Fo(6)p Fi(=)p Fo(;)3446 2270 y Fm(Q)3512 2285 y Fo(f)p Fp(i;j)s Fo(g)3658 2270 y Fs(\()p Fm(!)3742 2282 y Fp(i)3770 2270 y Fm(;)14 b(!)3859 2282 y Fp(j)3893 2270 y Fs(\))2130 2549 y(where)27 b(here)g Fm(Z)2607 2561 y Fi(\003)2656 2549 y Fs(\()p Fm(!)s Fs(\))d(=)2886 2487 y Fn(P)2974 2574 y Fp(!)3016 2582 y Fh(\003)3076 2487 y Fn(Q)3154 2574 y Fo(f)p Fp(i;j)s Fo(g\\)p Fi(\003)p Fo(6)p Fi(=)p Fo(;)3489 2549 y Fm(Q)3555 2564 y Fo(f)p Fp(i;j)s Fo(g)3701 2549 y Fs(\()p Fm(!)3785 2561 y Fp(i)3813 2549 y Fm(;)14 b(!)3902 2561 y Fp(j)3936 2549 y Fs(\).)2130 2742 y Ft(De\014nition)31 b(4.3)40 b Fk(A)g(family)h Fq(f)p Fm(l)3170 2757 y Fi(\()p Fp(i;j)s Fi(\))3299 2742 y Fq(g)3341 2770 y Fi(\()p Fp(i;j)s Fi(\))p Fo(2)3521 2755 y Fp(~)3511 2770 y(E)3563 2753 y Fh(\010)3611 2742 y Fk(,)i(wher)l(e)d(e)l(ach)2130 2851 y Fm(l)2155 2866 y Fi(\()p Fp(i;j)s Fi(\))2322 2851 y Fk(is)d(a)h(me)l(asur)l(e)e(on)h Fq(X)3011 2863 y Fp(i)3076 2851 y Fk(is)g(c)l(al)t(le)l(d)i(a)e Fs(b)r(oundary)e(la)n(w)h Fk(if)2130 2969 y(for)31 b(e)l(ach)f Fs(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)2733 2948 y Fm(~)2720 2969 y(E)2786 2939 y Fi(\010)2867 2969 y Fk(we)30 b(have)h Fq(8)p Fm(!)3280 2981 y Fp(i)3330 2969 y Fq(2)23 b(X)3467 2981 y Fp(i)3495 2969 y Fk(:)2196 3168 y Fm(l)2221 3183 y Fi(\()p Fp(i;j)s Fi(\))2351 3168 y Fs(\()p Fm(!)2435 3180 y Fp(i)2463 3168 y Fs(\))g(=)g Fm(\021)2749 3089 y Fn(Y)2664 3271 y Fp(k)q Fo(2)p Fp(@)t(i)p Fo(nf)p Fp(j)s Fo(g)2998 3089 y Fn(X)2955 3267 y Fp(!)2997 3276 y Fg(k)3033 3267 y Fo(2X)3126 3276 y Fg(k)3175 3168 y Fm(Q)3241 3183 y Fo(f)p Fp(k)q(;i)p Fo(g)3393 3168 y Fs(\()p Fm(!)3477 3180 y Fp(k)3518 3168 y Fm(;)14 b(!)3607 3180 y Fp(i)3634 3168 y Fs(\))30 b Fm(l)3721 3183 y Fi(\()p Fp(k)q(;i)p Fi(\))3857 3168 y Fs(\()p Fm(!)3941 3180 y Fp(k)3981 3168 y Fs(\))3974 3364 y(\(2\))2130 3547 y(Note)20 b(the)h(similarit)n(y)e(to)h(the)h (message)e(passing)g(up)r(date)h(rule.)2130 3730 y Ft(Prop)s(osition)30 b(4.6)41 b Fk(The)30 b(fol)t(lowing)j(hold)2144 3946 y(\(a\))42 b(Each)d(b)l(oundary)g(law)g Fq(f)p Fm(l)3103 3961 y Fi(\()p Fp(i;j)s Fi(\))3232 3946 y Fq(g)3274 3973 y Fi(\()p Fp(i;j)s Fi(\))p Fo(2)3454 3958 y Fp(~)3444 3973 y(E)3496 3957 y Fh(\010)3582 3946 y Fk(for)g(the)f(tr)l(ans-)2296 4058 y(fer)55 b(matric)l(es)g Fq(f)p Fm(Q)2916 4073 y Fo(f)p Fp(i;j)s Fo(g)3062 4058 y Fq(g)3104 4075 y Fo(f)p Fp(i;j)s Fo(g2)p Fp(E)3342 4058 y Fh(\010)63 b Fk(de\014nes)54 b(a)h(unique)2296 4167 y(Markov)42 b(chain)e Fm(\026)i Fq(2)f Fm(G)p Fs(\()p Fm(\015)3174 4137 y Fi(\010)3226 4167 y Fs(\))f Fk(via)h(the)f(e)l(quation:)59 b(for)2296 4267 y(e)l(ach)31 b(c)l(onne)l(cte)l(d)e(set)h Fs(\003)2296 4450 y Fm(\026)p Fs(\()p Fm(!)2430 4462 y Fi(\003)p Fo([)p Fp(@)t Fi(\003)2609 4450 y Fs(\))23 b(=)g Fm(\021)2840 4371 y Fn(Y)2810 4550 y Fp(k)q Fo(2)p Fp(@)t Fi(\003)2990 4450 y Fm(l)3015 4465 y Fi(\()p Fp(k)q(;k)3132 4473 y Fh(\003)3174 4465 y Fi(\))3204 4450 y Fs(\()p Fm(!)3288 4462 y Fp(k)3329 4450 y Fs(\))3502 4371 y Fn(Y)3396 4553 y Fo(f)p Fp(i;j)s Fo(g\\)p Fi(\003)p Fo(6)p Fi(=)p Fo(;)3727 4450 y Fm(Q)3793 4465 y Fo(f)p Fp(i;j)s Fo(g)3939 4450 y Fs(\()p Fm(!)4023 4462 y Fp(i)4051 4450 y Fm(;)14 b(!)4140 4462 y Fp(j)4174 4450 y Fs(\))3974 4646 y(\(3\))2148 4812 y Fk(\(b\))42 b(Each)e(Markov)h(chain)f Fm(\026)f Fq(2)h Fm(G)p Fs(\()p Fm(\015)3387 4782 y Fi(\010)3439 4812 y Fs(\))f Fk(admits)h(a)f(r)l(epr)l(e-)2296 4912 y(sentation)31 b(of)i(the)e(form)i(\(3\))e(in)h(terms)f(of)h(a)g(b)l (oundary)2296 5011 y(law)24 b Fq(f)p Fm(l)2505 5026 y Fi(\()p Fp(i;j)s Fi(\))2635 5011 y Fq(g)2677 5039 y Fi(\()p Fp(i;j)s Fi(\))p Fo(2)2857 5024 y Fp(~)2847 5039 y(E)2899 5023 y Fh(\010)2970 5011 y Fk(which)h(is)f(unique)f(up)g(to)h(a)g(p)l (ositive)2296 5120 y(sc)l(aling)31 b(c)l(onstant.)2130 5336 y Ft(Pro)s(of:)36 b Fs(See)28 b(theorem)f(12.12)f(of)h([1].)37 b Fb(2)p eop %%Page: 7 7 7 6 bop 30 83 a Ft(Boundary)33 b(La)m(ws)f(and)h(Messages)30 232 y Fs(Let)41 b(\010)f(b)r(e)h(a)f(pairwise)f(p)r(oten)n(tial)h (whose)g(Mark)n(o)n(v)e(graph)30 332 y(is)e(an)g(in\014nite)h(tree.)62 b(W)-7 b(e)37 b(no)n(w)e(relate)h(b)r(oundary)f(la)n(ws)g(to)30 432 y(messages.)g(Recall)27 b(that)h(for)f(eac)n(h)g(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)1441 411 y Fm(~)1429 432 y(E)1495 402 y Fi(\010)1574 432 y Fs(w)n(e)k(ha)n(v)n(e)306 586 y Fm(m)379 601 y Fi(\()p Fp(i;j)s Fi(\))509 586 y Fs(\()p Fm(!)593 598 y Fp(j)628 586 y Fs(\))159 736 y(=)82 b Fm(\021)364 657 y Fn(X)390 831 y Fp(!)432 839 y Fg(i)498 736 y Fm(e)537 702 y Fo(\000)p Fi(\(\010)662 713 y Ff(f)p Fg(i;j)r Ff(g)795 702 y Fi(\()p Fp(!)863 710 y Fg(i)889 702 y Fp(;!)951 710 y Fg(j)982 702 y Fi(\)+)p Fp(!)1101 713 y Ff(f)p Fg(i)p Ff(g)1188 702 y Fi(\()p Fp(!)1256 710 y Fg(i)1282 702 y Fi(\)\))1403 657 y Fn(Y)1352 839 y Fp(k)q Fo(2)p Fp(@)t(i)p Fo(n)p Fp(j)1574 736 y Fm(m)1647 751 y Fi(\()p Fp(k)q(;j)s Fi(\))1791 736 y Fs(\()p Fm(!)1875 748 y Fp(i)1902 736 y Fs(\))30 987 y(Note)38 b(that)h(equation)f(\(2\)) g(has)g(a)g(pro)r(duct)g(of)g(sums)g(form)30 1087 y(whereas)j(the)h (equation)f(ab)r(o)n(v)n(e)g(has)g(a)h(sum)g(of)f(pro)r(ducts)30 1186 y(from.)c(F)-7 b(or)27 b(eac)n(h)f(\()p Fm(i;)14 b(j)5 b Fs(\))23 b Fq(2)878 1165 y Fm(~)865 1186 y(E)931 1156 y Fi(\010)1010 1186 y Fs(let)469 1357 y(\010)529 1317 y Fp(i)p Fo(!)p Fp(j)529 1385 y Fo(f)p Fp(i)p Fo(g)653 1357 y Fs(\()p Fm(!)737 1369 y Fp(i)765 1357 y Fs(\))g(=)g Fm(\021)1017 1278 y Fn(Y)966 1460 y Fp(k)q Fo(2)p Fp(@)t(i)p Fo(n)p Fp(j)1189 1357 y Fm(m)1262 1372 y Fi(\()p Fp(k)q(;i)p Fi(\))1397 1357 y Fs(\()p Fm(!)1481 1369 y Fp(i)1509 1357 y Fs(\))30 1604 y(and)k(after)h(some)f(algebra)f(w)n(e)h(get)30 1770 y(\010)90 1730 y Fp(i)p Fo(!)p Fp(j)90 1798 y Fo(f)p Fp(i)p Fo(g)215 1770 y Fs(\()p Fm(!)299 1782 y Fp(i)326 1770 y Fs(\))d(=)e Fm(\021)579 1691 y Fn(Y)527 1873 y Fp(k)q Fo(2)p Fp(@)t(i)p Fo(n)p Fp(j)750 1691 y Fn(X)771 1865 y Fp(!)813 1874 y Fg(k)884 1770 y Fm(e)923 1735 y Fo(\000)p Fi(\(\010)1048 1746 y Ff(f)p Fg(k)q(;i)p Ff(g)1186 1735 y Fi(\()p Fp(!)1254 1744 y Fg(k)1290 1735 y Fp(;!)1352 1743 y Fg(i)1378 1735 y Fi(\)+\010)1502 1746 y Ff(f)p Fg(k)q Ff(g)1600 1735 y Fi(\()p Fp(!)1668 1744 y Fg(k)1704 1735 y Fi(\)\))1760 1770 y Fs(\010)1820 1735 y Fp(k)q Fo(!)p Fp(i)1820 1792 y Fo(f)p Fp(k)q Fo(g)1950 1770 y Fs(\()p Fm(!)2034 1782 y Fp(k)2075 1770 y Fs(\))1874 1966 y(\(4\))30 2066 y(whic)n(h)35 b(is)g(in)h(a)f(pro)r(duct)g(of)g (sums)g(form.)60 b(Comparing)34 b(\(4\))30 2166 y(and)27 b(\(2\))h(w)n(e)f(see)h(that)277 2338 y Fm(l)302 2353 y Fi(\()p Fp(i;j)s Fi(\))432 2338 y Fs(\()p Fm(!)516 2350 y Fp(i)543 2338 y Fs(\))83 b(=)g Fm(\021)s(e)889 2298 y Fo(\000)p Fi(\()1010 2276 y Fh(1)p 977 2285 95 3 v 977 2319 a Ff(j)p Fg(@)s(i)p Ff(j)1081 2298 y Fi(+1\))1195 2338 y Fs(\010)1255 2298 y Fp(i)p Fo(!)p Fp(j)1255 2367 y Fo(f)p Fp(i)p Fo(g)1380 2338 y Fs(\()p Fm(!)1464 2350 y Fp(i)1491 2338 y Fs(\))658 2504 y(=)g Fm(\021)s(e)889 2463 y Fo(\000)984 2441 y Fh(1)p 951 2450 V 951 2484 a Ff(j)p Fg(@)s(i)p Ff(j)1055 2463 y Fo(\000)p Fi(1)1209 2425 y Fn(Y)1158 2607 y Fp(k)q Fo(2)p Fp(@)t(i)p Fo(n)p Fp(j)1381 2504 y Fm(m)1454 2519 y Fi(\()p Fp(k)q(;i)p Fi(\))1589 2504 y Fs(\()p Fm(!)1673 2516 y Fp(i)1701 2504 y Fs(\))30 2750 y(Th)n(us)18 b(w)n(e)g(can)h(go)e(from)h(b)r (oundary)g(self-p)r(oten)n(tials)g(and)g(mes-)30 2850 y(sages)26 b(to)i(b)r(oundary)e(la)n(ws)h(and)g(vice-v)n(ersa.)30 3026 y Ft(Prop)s(osition)j(4.7)41 b Fk(Each)36 b(subse)l(quential)g (limit)f(of)i(the)e(se-)30 3139 y(quenc)l(e)60 b(of)h(me)l(asur)l(es)e Fq(f)p Fm(\026)935 3108 y Fi(\010)982 3079 y Fg(T)1017 3087 y(n)1054 3102 y(k)1102 3139 y Fq(g)1144 3151 y Fp(k)q Fo(\025)p Fi(1)1330 3139 y Fk(c)l(orr)l(esp)l(onds)i(to)f(a)30 3238 y(Markov)31 b(chain)g(in)f Fm(G)p Fs(\()p Fm(\015)802 3208 y Fi(\010)854 3238 y Fs(\))p Fk(.)30 3415 y Ft(Pro)s(of:)49 b Fs(W)-7 b(e)34 b(sk)n(etc)n(h)f(the)h(pro)r(of.)54 b(See)34 b([3])g(for)f(full)h(details.)30 3532 y(Let)e Fq(f)p Fm(n)275 3544 y Fp(k)316 3532 y Fq(g)358 3544 y Fp(k)q Fo(\025)p Fi(1)515 3532 y Fs(b)r(e)h(a)e(subsequence)h(for)g (whic)n(h)g Fq(f)p Fm(\026)1646 3501 y Fi(\010)1693 3472 y Fg(T)1728 3480 y(n)1765 3495 y(k)1813 3532 y Fq(g)1855 3544 y Fp(k)q Fo(\025)p Fi(1)30 3631 y Fs(con)n(v)n(erges)26 b(to)j(some)f(measure)g Fm(\026:)h Fs(By)f(prop)r(osition)g(4.4)g(this) 30 3731 y Fm(\026)d Fs(is)f(an)h(elemen)n(t)g(of)f Fm(G)p Fs(\()p Fm(\015)838 3701 y Fi(\010)890 3731 y Fs(\).)36 b(By)25 b(prop)r(osition)f(3.1)f(the)i(mes-)30 3830 y(sages)39 b Fq(f)p Fm(m)371 3793 y Fp(n)412 3802 y Fg(k)371 3859 y Fi(\()p Fp(i;j)s Fi(\))500 3830 y Fq(g)h Fs(con)n(v)n(erge)e(along)i (the)g(subsequence)g Fq(f)p Fm(n)1898 3842 y Fp(k)1938 3830 y Fq(g)30 3944 y Fs(to)h(some)f(\014xed)i(p)r(oin)n(t)f(solution)f Fq(f)p Fm(m)1253 3914 y Fo(\003)1253 3971 y Fi(\()p Fp(i;j)s Fi(\))1383 3944 y Fq(g)p Fs(.)77 b(By)41 b(equation)30 4056 y(\(2\))31 b(and)g(\(4\))g(this)g(\014xed)g(p)r(oin)n(t)g (solution)f(corresp)r(onds)f(to)h(a)30 4155 y(b)r(oundary)h(la)n(w.)50 b(By)32 b(prop)r(osition)f(4.6)g(w)n(e)h(see)g(that)g Fm(\026)g Fs(is)g(a)30 4255 y(Mark)n(o)n(v)25 b(c)n(hain.)37 b Fb(2)30 4404 y Fs(Recall)31 b(that)h(prop)r(osition)f(4.2)f(states)i (that)f(the)h(set)g Fm(G)p Fs(\()p Fm(\015)1896 4374 y Fi(\010)1948 4404 y Fs(\))30 4504 y(is)27 b(nonempt)n(y)g(and)g (hence)h(con)n(tains)e(at)h(least)g(one)g(extremal)30 4604 y(elemen)n(t.)36 b(By)23 b(prop)r(osition)g(4.5)g(this)i(extremal) e(elemen)n(t)h(is)f(a)30 4703 y(Mark)n(o)n(v)30 b(c)n(hain.)52 b(These)32 b(results)g(along)f(with)i(prop)r(ositions)30 4803 y(3.1)d(and)i(4.7)e(giv)n(e)g(us)h(a)g(new)h(w)n(a)n(y)e(to)h(sho) n(w)f(that)i(there)f(al-)30 4902 y(w)n(a)n(ys)19 b(exists)h(at)g(least) g(one)h(solution)e(to)i(the)g(LBP)e(\014xed)i(p)r(oin)n(t)30 5002 y(equations.)30 5151 y(It)30 b(has)e(b)r(een)i(observ)n(ed)e(in)i (practice)e(that)i(LBP)e(sometimes)30 5251 y(oscillates.)63 b(In)37 b(this)h(case)e(LBP)g(is)g(actually)h(jumping)g(b)r(e-)30 5351 y(t)n(w)n(een)27 b(di\013eren)n(t)g(solutions)f(of)h(the)g(LBP)f (\014xed)h(p)r(oin)n(t)g(equa-)30 5450 y(tions)45 b(and)g(hence)h (jumping)g(b)r(et)n(w)n(een)f(di\013eren)n(t)g(Mark)n(o)n(v)30 5550 y(c)n(hains)27 b(de\014ned)h(on)f(the)h(computation)f(tree.)2130 83 y(In)d(summary)-7 b(,)23 b(w)n(e)g(ha)n(v)n(e)g(c)n(haracterized)e (eac)n(h)i(subsequen)n(tial)2130 183 y(limit)29 b(measure)f(corresp)r (onding)f(to)h(the)h(LBP)f(algorithm)g(in)2130 282 y(terms)j(of)h(a)f (Mark)n(o)n(v)f(c)n(hain)h(de\014ned)h(on)f(the)h(computation)2130 382 y(tree.)55 b(W)-7 b(e)35 b(will)f(no)n(w)f(discuss)h(conditions)f (that)h(insure)g(the)2130 482 y(existence)27 b(of)h(a)f(unique)h (limit.)2130 721 y Fr(5)112 b(Unique)38 b(Gibbs)f(Measure)i(Case)2130 925 y Fs(Here)k(w)n(e)f(consider)h(the)g(case)f(of)h(a)g(unique)g (Gibbs)h(mea-)2130 1025 y(sure:)i Fq(j)p Fm(G)p Fs(\()p Fm(\015)2516 995 y Fi(\010)2568 1025 y Fs(\))p Fq(j)31 b Fs(=)g(1.)50 b(Clearly)32 b(there)g(can)g(b)r(e)h(only)f(b)r(e)g(one) 2130 1125 y(subsequen)n(tial)27 b(limit)i(of)f(the)g(sequence)f(of)h (measures)f Fm(\026)3926 1094 y Fi(\010)3973 1102 y Fg(T)4008 1110 y(n)4057 1125 y Fs(.)2130 1224 y(Hence)c(LBP)g(con)n(v)n(erges.)33 b(W)-7 b(e)23 b(can)g(sa)n(y)f(something)h(stronger)2130 1324 y(though:)51 b(LBP)34 b(con)n(v)n(erges)e(uniformly)i(o)n(v)n(er)f (the)i(c)n(hoice)f(of)2130 1423 y(all)27 b(initializing)h(messages.) 2130 1607 y Ft(Prop)s(osition)i(5.1)41 b Fk(If)30 b Fq(j)p Fm(G)p Fs(\()p Fm(\015)3065 1577 y Fi(\010)3117 1607 y Fs(\))p Fq(j)23 b Fs(=)g(1)29 b Fk(then)2340 1791 y Fs(lim)2311 1841 y Fp(n)p Fo(!1)2498 1791 y Fm(\015)2546 1757 y Fi(\010)2541 1812 y Fp(T)2580 1820 y Fg(n)2625 1791 y Fs(\()p Fq(\001)h(j)g Fm(!)s Fs(\))23 b(=)g Fm(\026)3011 1757 y Fi(\010)3062 1791 y Fs(\()p Fq(\001)p Fs(\))30 b Fk(uniformly)h(in)f Fm(!)c Fq(2)d Fs(\012)p Fm(:)2130 2055 y Ft(Pro)s(of:)36 b Fs(See)28 b(prop)r(osition)e(7.11)h(in)h([1)o (].)37 b Fb(2)2130 2247 y Ft(Prop)s(osition)30 b(5.2)41 b Fk(If)22 b Fq(j)p Fm(G)p Fs(\()p Fm(\015)3057 2217 y Fi(\010)3109 2247 y Fs(\))p Fq(j)i Fs(=)e(1)g Fk(then)g(for)h(any)g (cylinder)2130 2347 y(event)30 b Fm(A)g Fk(we)g(have)2717 2531 y Fs(lim)2688 2581 y Fp(n)p Fo(!1)2875 2531 y Fm(\026)2925 2497 y Fi(\010)2972 2472 y Fg(T)3007 2480 y(n)2925 2552 y Fp(T)2964 2560 y Fg(n)3056 2531 y Fs(\()p Fm(A)p Fs(\))24 b(=)f Fm(\026)3344 2497 y Fi(\010)3395 2531 y Fs(\()p Fm(A)p Fs(\))2130 2740 y Fk(uniformly)31 b(over)f(the)g(b)l(oundary)h (self-p)l(otentials.)2130 2933 y Ft(Pro)s(of:)49 b Fs(W)-7 b(e)34 b(sk)n(etc)n(h)f(the)h(pro)r(of.)54 b(See)34 b([3])g(for)f(full) h(details.)2130 3032 y(Let)25 b Fq(f)p Fs(\010)2378 3002 y Fp(bd;n)2506 3032 y Fq(g)2548 3044 y Fp(n)p Fo(\025)p Fi(1)2702 3032 y Fs(b)r(e)g(an)n(y)f(set)h(of)g(b)r(oundary)f(self-p)r (oten)n(tials.)2130 3132 y(Let)42 b Fm(A)g Fs(b)r(e)g Fq(F)2584 3144 y Fi(\003)2629 3152 y Fh(1)2665 3132 y Fs(-measurable)e(and)h(c)n(ho)r(ose)g Fm(\017)46 b(>)g Fs(0)p Fm(:)41 b Fs(Then)2130 3231 y(b)n(y)35 b(prop)r(osition)f(5.1)g (there)h(exists)g(a)g(\003)3430 3243 y Fi(2)3503 3231 y Fq(\033)g Fs(\003)3661 3243 y Fi(1)3733 3231 y Fs(suc)n(h)g(that)2130 3331 y Fq(j)p Fm(\015)2201 3301 y Fi(\010)2196 3354 y(\003)2241 3362 y Fh(2)2278 3331 y Fs(\()p Fm(A)28 b Fq(j)g Fm(!)s Fs(\))18 b Fq(\000)g Fm(\026)2689 3301 y Fi(\010)2741 3331 y Fs(\()p Fm(A)p Fs(\))p Fq(j)24 b(\024)f Fm(\017:)k Fs(No)n(w)g(for)g Fm(T)3451 3343 y Fp(n)3519 3331 y Fq(\033)c Fs(\003)3665 3343 y Fi(2)3729 3331 y Fs(w)n(e)k(ha)n(v)n(e)2130 3543 y Fq(j)p Fm(\026)2203 3509 y Fi(\010)2250 3484 y Fg(T)2285 3492 y(n)2203 3564 y Fp(T)2242 3572 y Fg(n)2334 3543 y Fs(\()p Fm(A)p Fs(\))19 b Fq(\000)f Fm(\026)2612 3509 y Fi(\010)2664 3543 y Fs(\()p Fm(A)p Fs(\))p Fq(j)84 b Fs(=)e Fq(j)p Fm(\026)3117 3498 y Fi(\010)3164 3506 y Fg(T)3199 3514 y(n)3117 3567 y Fp(T)3156 3575 y Fg(n)3248 3543 y Fm(\015)3296 3498 y Fi(\010)3343 3506 y Fg(T)3378 3514 y(n)3291 3567 y Fi(\003)3336 3575 y Fh(2)3427 3543 y Fs(\()p Fm(A)28 b Fq(j)g Fm(!)s Fs(\))18 b Fq(\000)g Fm(\026)3838 3509 y Fi(\010)3890 3543 y Fs(\()p Fm(A)p Fs(\))p Fq(j)2897 3694 y Fs(=)82 b Fq(j)p Fm(\026)3117 3649 y Fi(\010)3164 3657 y Fg(T)3199 3665 y(n)3117 3718 y Fp(T)3156 3726 y Fg(n)3248 3694 y Fm(\015)3296 3660 y Fi(\010)3291 3714 y(\003)3336 3722 y Fh(2)3373 3694 y Fs(\()p Fm(A)29 b Fq(j)e Fm(!)s Fs(\))19 b Fq(\000)f Fm(\026)3785 3660 y Fi(\010)3836 3694 y Fs(\()p Fm(A)p Fs(\))p Fq(j)2897 3845 y Fs(=)82 b Fq(j)p Fm(\026)3117 3800 y Fi(\010)3164 3808 y Fg(T)3199 3816 y(n)3117 3869 y Fp(T)3156 3877 y Fg(n)3262 3778 y Fn(\000)3300 3845 y Fm(\015)3348 3811 y Fi(\010)3343 3865 y(\003)3388 3873 y Fh(2)3425 3845 y Fs(\()p Fm(A)29 b Fq(j)e Fm(!)s Fs(\))19 b Fq(\000)f Fm(\026)3837 3811 y Fi(\010)3888 3845 y Fs(\()p Fm(A)p Fs(\))4014 3778 y Fn(\001)4067 3845 y Fq(j)2897 3996 y(\024)82 b(j)p Fm(\026)3117 3950 y Fi(\010)3164 3958 y Fg(T)3199 3966 y(n)3117 4020 y Fp(T)3156 4028 y Fg(n)3248 3996 y Fm(\017)p Fq(j)2897 4120 y Fs(=)g Fm(\017)2130 4305 y Fs(where)50 b(the)h(\014rst)f(equalit)n(y)g(holds)g (via)g(the)h(DLR)g(equa-)2130 4404 y(tion.)37 b(Th)n(us)27 b(the)h(con)n(v)n(ergence)d(rate)i(is)h(indep)r(enden)n(t)g(of)g(the) 2130 4504 y(b)r(oundary)f(self-p)r(oten)n(tials)g(used.)37 b Fb(2)2130 4653 y Fs(In)k(summary)f(if)i Fq(j)p Fm(G)p Fs(\(\010\))p Fq(j)47 b Fs(=)e(1)40 b(then)i(LBP)e(will)h(con)n(v)n (erge)2130 4753 y(uniformly)30 b(o)n(v)n(er)e(the)i(b)r(oundary)f (self-p)r(oten)n(tials.)43 b(Next)30 b(w)n(e)2130 4853 y(presen)n(t)21 b(Dobrushin's)g(su\016cien)n(t)g(condition)g(for)g (uniqueness)2130 4952 y(of)28 b(the)g(limiting)g(Gibbs)f(measure.)2130 5102 y Ft(Dobrushin's)k(Condition)2130 5251 y Fs(A)25 b(Gibbs)g(p)r(oten)n(tial)g(can)f(lead)g(to)h(man)n(y)f(di\013eren)n(t) h(phases)f(if)2130 5351 y(no)r(des)32 b(that)h(are)f(far)g(apart)g (from)g(eac)n(h)g(other)g(do)g(not)h(mix)2130 5450 y(fast)27 b(enough.)36 b(Dobrushin)28 b(prop)r(osed)e(the)h(follo)n(wing)g (condi-)2130 5550 y(tion)h(that)g(insures)e(fast)i(mixing)f(and)h (hence)g(uniqueness.)p eop %%Page: 8 8 8 7 bop 30 83 a Ft(Prop)s(osition)30 b(5.3)41 b Fk(L)l(et)29 b Fs(\010)h Fk(b)l(e)g(a)g(p)l(airwise)h(p)l(otential.)40 b(If)532 264 y Fs(sup)539 333 y Fp(i)p Fo(2)p Fp(S)671 185 y Fn(X)672 363 y Fp(A)p Fo(3)p Fp(i)791 264 y Fs(\()p Fq(j)p Fm(A)p Fq(j)19 b(\000)f Fs(1\))p Fm(\016)s Fs(\(\010)1239 276 y Fp(A)1293 264 y Fs(\))24 b Fm(<)e Fs(2)396 b(\(5\))30 526 y Fk(then)24 b Fq(j)p Fm(G)p Fs(\()p Fm(\015)377 496 y Fi(\010)429 526 y Fs(\))p Fq(j)f Fs(=)g(1)p Fk(.)36 b(Wher)l(e)25 b Fm(\016)s Fs(\()p Fm(f)9 b Fs(\))1135 502 y Fo(4)1132 553 y Fs(=)1219 526 y(sup)1344 546 y Fp(x)1400 526 y Fm(f)g Fs(\()p Fm(x)p Fs(\))d Fq(\000)g Fs(inf)1740 538 y Fp(x)1795 526 y Fm(f)j Fs(\()p Fm(x)p Fs(\))p Fm(:)30 703 y Ft(Pro)s(of:)36 b Fs(See)28 b(prop)r(osition)e (8.8)h(in)h([1].)37 b Fb(2)30 852 y Fs(This)22 b(prop)r(osition)g (states)g(that)g(the)h("in\015uence")f(no)r(de)h Fm(i)f Fs(has)30 952 y(on)34 b(the)g(rest)f(of)h(the)g(no)r(des)g(dep)r(ends)g (on)f(t)n(w)n(o)g(things:)50 b(the)30 1052 y(n)n(um)n(b)r(er)23 b(of)h(neigh)n(b)r(ors)e(it)i(has)f(and)h(the)g(strength)f(of)g(the)h (p)r(o-)30 1151 y(ten)n(tials,)h(measured)f(b)n(y)g Fm(\016)s Fs(\(\010\),)i(it)f(tak)n(es)e(part)h(in.)36 b(Note)25 b(that)30 1251 y(the)35 b(self-p)r(oten)n(tials)f(do)g(not)h(pla)n(y)e (a)i(part)f(in)g(Dobrushin's)30 1351 y(condition.)30 1500 y(Let)25 b(us)g(return)f(to)h(the)g(issue)f(of)h(LBP)-7 b(.)24 b(Let)h(\010)g(b)r(e)g(the)g(p)r(oten-)30 1600 y(tial)f(for)f(the)h(\014nite)h(Gibbs)f(measure)e(that)j(w)n(e)e(wish)h (to)f(apply)30 1699 y(LBP)28 b(to.)41 b(Let)523 1678 y(~)514 1699 y(\010)29 b(b)r(e)g(the)g(corresp)r(onding)e(p)r(oten)n (tial)i(on)g(the)30 1799 y(computation)k(tree.)55 b(The)34 b(lo)r(cal)f(top)r(ology)f(of)h(the)h(compu-)30 1899 y(tation)26 b(tree)f(lo)r(oks)g(lik)n(e)h(the)g(lo)r(cal)f(top)r(ology) g(of)g(the)i(original)30 1998 y(graph.)36 b(Hence)28 b(to)f(sho)n(w)g Fq(j)p Fm(G)p Fs(\()981 1977 y(~)972 1998 y(\010\))p Fq(j)d Fs(=)e(1)28 b(w)n(e)f(need)g(to)h(sho)n(w)65 2184 y(sup)44 2256 y Fi(~)49 2269 y Fp(i)q Fo(2)p Fp(S)168 2242 y Fh(~)162 2252 y(\010)219 2105 y Fn(X)220 2296 y Fp(A)p Fo(3)310 2283 y Fi(~)315 2296 y Fp(i)339 2184 y Fs(\()p Fq(j)p Fm(A)p Fq(j)19 b(\000)f Fs(1\))p Fm(\016)s Fs(\()736 2163 y(~)727 2184 y(\010)787 2196 y Fp(A)841 2184 y Fs(\))24 b(=)f(max)984 2242 y Fp(i)p Fo(2)p Fp(S)1096 2226 y Fh(\010)1154 2105 y Fn(X)1155 2283 y Fp(A)p Fo(3)p Fp(i)1274 2184 y Fs(\()p Fq(j)p Fm(A)p Fq(j)c(\000)f Fs(1\))p Fm(\016)s Fs(\(\010)1722 2196 y Fp(A)1776 2184 y Fs(\))24 b Fm(<)e Fs(2)30 2443 y(Note)e(that)g(the)g(maxim)n(um)f (condition)h(is)f(v)n(ery)g(easy)f(to)i(c)n(hec)n(k)30 2543 y(on)27 b(\014nite)h(graphs.)30 2692 y Ft(Rate)k(of)f(Con)m(v)m (ergence)30 2842 y Fs(Here)25 b(w)n(e)g(giv)n(e)f(a)h(condition)g(on)h (the)f(rate)g(of)g(con)n(v)n(ergence)e(of)30 2941 y(LBP)-7 b(.)27 b(Let)h Fm(c)p Fs(\(\010\))23 b(=)g(max)815 2958 y Fp(s)p Fo(2)p Fp(S)935 2941 y Fh(\010)997 2879 y Fn(P)1085 2966 y Fp(A)p Fo(3)p Fp(s)1229 2941 y Fm(e)1268 2911 y Fi(2)1305 2941 y Fs(\()p Fq(j)p Fm(A)p Fq(j)c(\000)f Fs(1\))p Fm(\016)s Fs(\(\010)1753 2953 y Fp(A)1807 2941 y Fs(\).)30 3119 y Ft(Prop)s(osition)30 b(5.4)41 b Fk(If)30 b Fm(c)p Fs(\(\010\))23 b Fm(<)g Fs(2)29 b Fk(then)492 3304 y Fq(j)p Fm(\026)565 3270 y Fi(\010)612 3245 y Fg(T)647 3253 y(n)565 3325 y Fp(T)604 3333 y Fg(n)696 3304 y Fs(\()p Fm(!)780 3316 y Fp(s)816 3304 y Fs(\))18 b Fq(\000)g Fm(\026)999 3270 y Fi(\010)1051 3304 y Fs(\()p Fm(!)1135 3316 y Fp(s)1170 3304 y Fs(\))p Fq(j)24 b(\024)e Fm(k)s(e)1421 3270 y Fo(\000)p Fp(n)30 3473 y Fk(wher)l(e)39 b Fm(s)f Fk(is)h(the)f(r)l(o)l(ot)g(no)l(de)h(and)g Fm(k)i Fs(=)d(\(1)25 b Fq(\000)f Fm(c)p Fs(\(\010\)\))1712 3443 y Fo(\000)p Fi(1)1840 3473 y Fk(is)39 b(a)30 3573 y(c)l(onstant.)30 3750 y Ft(Pro)s(of:)j Fs(See)31 b(theorem)f(8.23,)g(remark)f(8.26,)h (and)h(corollary)30 3850 y(8.32)26 b(of)i([1)o(].)37 b Fb(2)30 4085 y Fr(6)112 b(Conclusions)30 4285 y Fs(In)22 b(this)g(pap)r(er)g(w)n(e)f(ha)n(v)n(e)g(in)n(tro)r(duced)h(to)r(ols)f (from)h(the)g(theory)30 4385 y(of)k(Gibbs)h(measures)e(to)h(analyze)g (the)g(con)n(v)n(ergence)e(prop)r(er-)30 4485 y(ties)37 b(of)g(the)h(LBP)e(algorithm.)65 b(In)37 b(particular)f(w)n(e)h (related)30 4584 y(the)g(problem)f(of)g(con)n(v)n(ergence)e(of)j(LBP)e (to)i(the)f(existence)30 4684 y(of)31 b(a)g(w)n(eak)g(limit)h(for)f(a)f (sequence)h(of)h(Gibbs)f(measures)f(de-)30 4784 y(\014ned)38 b(the)g(corresp)r(onding)e(computation)h(tree.)67 b(W)-7 b(e)38 b(ha)n(v)n(e)30 4883 y(in)n(tro)r(duced)30 b(a)f(condition)g (that)h(insures)f(the)i(uniqueness)e(of)30 4983 y(the)22 b(Gibbs)h(measure)d(de\014ned)j(on)e(the)i(in\014nite)f(computation)30 5082 y(tree.)37 b(Hence)27 b(this)h(condition)g(insures)e(LBP)h(con)n (v)n(erges.)30 5283 y Ft(Ac)m(kno)m(wledgmen)m(ts)30 5450 y Fs(The)e(authors)e(w)n(ould)i(lik)n(e)f(to)g(thank)h(Sanjo)n(y)f (Mitter,)i(Kevin)30 5550 y(Murph)n(y)-7 b(,)22 b(and)f(Mark)e(P)n (askin)h(for)g(man)n(y)g(helpful)i(discussion.)2130 83 y(This)51 b(w)n(ork)e(w)n(as)h(supp)r(orted)h(b)n(y)f(the)i(DoD)f (Multidisci-)2130 183 y(plinary)45 b(Univ)n(ersit)n(y)f(Researc)n(h)g (Initiativ)n(e)i(\(MURI\))g(pro-)2130 282 y(gram)41 b(administered)g(b) n(y)h(the)g(O\016ce)g(of)f(Na)n(v)-5 b(al)42 b(Researc)n(h)2130 382 y(under)27 b(Gran)n(t)g(N00014-00-1-0637.)2130 619 y Fr(References)2130 806 y Fs([1])83 b(H.)24 b(O.)g(Georgii,)g Fk(Gibbs)k(Me)l(asur)l(es)f(and)g(Phase)h(T)-6 b(r)l(ansi-)2301 906 y(tions)p Fs(.)27 b(Berlin,)h(W)-7 b(alter)27 b(de)h(Gruyter)f(and) g(Co.,)g(1988.)2130 1072 y([2])83 b(F.)20 b(Jensen,)h Fk(A)n(n)h(Intr)l(o)l(duction)h(to)g(Bayesian)h(Networks.)2301 1171 y Fs(UCL)j(Press,)g(London,)g(1996.)2130 1337 y([3])83 b(S.)43 b(T)-7 b(atik)n(onda)41 b(and)i(M.)g(Jordan,)i(\\)d(Conditions) h(for)2301 1437 y(Con)n(v)n(ergence)23 b(in)j(the)g(Lo)r(op)n(y)e (Belief)i(Propagation)d(Al-)2301 1536 y(gorithm.")j(Berk)n(eley)g(w)n (orking)g(pap)r(er,)h(2002.)2130 1703 y([4])83 b(M.)53 b(W)-7 b(ain)n(wrigh)n(t,)59 b(T.)54 b(Jaakk)n(ola)c(and)j(A.)h (Willsky)-7 b(,)2301 1802 y(\\T)g(ree-Based)65 b(Reparameterization)g (for)i(Appro)n(xi-)2301 1902 y(mate)28 b(Estimation)g(on)h(Lo)r(op)n(y) e(graphs.")g(Adv)-5 b(ances)29 b(in)2301 2001 y(Neural)d(Information)h (Pro)r(cessing)e(Systems)i(14,)f(2002.)2130 2167 y([5])83 b(Y.)21 b(W)-7 b(eiss,)23 b(\\Correctness)c(of)i(Lo)r(cal)f(Probabilit) n(y)g(Prop-)2301 2267 y(agation)j(in)h(Graphical)g(Mo)r(dels)g(with)h (Lo)r(ops.")e Fk(Neur)l(al)2301 2367 y(Computation)p Fs(,)28 b(12:1-41,)d(2000.)2130 2533 y([6])83 b(J.)36 b(Y)-7 b(edidia,)38 b(W.)f(F)-7 b(reeman.)36 b(Y.)g(W)-7 b(eiss,)39 b(\\Bethe)c(F)-7 b(ree)2301 2632 y(Energy)g(,)20 b(Kikuc)n(hi)g(Appro)n(ximations)e(and)i(Belief)h(Prop-)2301 2732 y(agation)35 b(Algorithms.")i(Adv)-5 b(ances)37 b(in)g(Neural)g(Infor-)2301 2832 y(mation)27 b(Pro)r(cessing)f(Systems) h(13,)g(2000.)2130 2998 y([7])83 b(A.)41 b(Y)-7 b(uille,)45 b(\\A)c(Double-Lo)r(op)f(Algorithm)h(to)g(Mini-)2301 3097 y(mize)24 b(the)i(Bethe)e(and)h(Kikuc)n(hi)f(F)-7 b(ree)24 b(Energies.")f Fk(Neu-)2301 3197 y(r)l(al)30 b(Computation)p Fs(,)e(to)g(app)r(ear,)f(2001.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF