Jim Reeds

Center for Communications Research

Abstract: Let Mn be the number of lattice paths in Z2/n connecting the origin with (1,a) (to within 1/n roundoff error at the end) that never cross above the barrier curve y(x). If y(0)=0, y(1)=a, and y is convex, then
Lim n Æ • 1/n log Mn = Ú01 (1+y’(x)) H(1/(1+y’(x))) dx,
where H(p) = –(p log p + (1–p) log (1–p)) is the usual entropy function; a slightly more complicated formula holds for non-convex barrier functions.