A continuity theory for lossless source coding over networks
WeiHsin Gu, Michelle Effros, Mayank Bakshi · 2008
A continuity theory of lossless source coding over networks is established and its implications are investigated. In the given model, source and side-information random variables X and Y have finite alphabets, and the input sequences are drawn i.i.d. according to a generic distribution PX,Yon (X,Y). We consider traditional source coding, where all demands equal source random variables. We define a family of lossless source coding problems that includes prior example network source coding problems as special cases. We show that the lossless rate region RL(PX,Y) is inner semi-continuous in PX,Y. We further show that for a special type of networks called super-source networks, where there is a super source node v*that has access to (X,Y) and any other node with access to some source random variable Xiis directly connected to v*, RL(PX,Y) is also outer semi-continuous in PX,Y. Based on the continuity of super-source networks with respect to PX,Y, we conjecture that RL(PX,Y) is also outer semi-continuous and therefore continuous in PX,Yfor general networks.