For references, refer to https://github.com/cheuktingli/psitip#references
%matplotlib inline
from psitip import *
PsiOpts.setting(
solver = "ortools.GLOP", # Set linear programming solver
str_style = "std", # Conventional notations in output
proof_note_color = "blue", # Reasons in proofs are blue
solve_display_reg = True, # Display claims in solve commands
random_seed = 4321 # Random seed for example searching
)
X, Y, Z, W, U, V, M, S = rv("X, Y, Z, W, U, V, M, S") # Declare random variables
H(X+Y) - H(X) - H(Y) # Simplify H(X,Y) - H(X) - H(Y)
bool(H(X) + I(Y & Z | X) >= I(Y & Z)) # Check H(X) + I(Y;Z|X) >= I(Y;Z)
True
# Prove an implication
(markov(X+W, Y, Z) >> (I(X & W | Y) / 2 <= H(X | Z))).solve(full=True)
# Information diagram that shows the above implication
(markov(X+W, Y, Z) >> (I(X & W | Y) / 2 <= H(X | Z))).venn()
# Disprove an implication by a counterexample
(markov(X+W, Y, Z) >> (I(X & W | Y) * 3 / 2 <= H(X | Z))).solve(full=True)
# The condition "there exists Y independent of X such that
# X-Y-Z forms a Markov chain" can be simplified to "X,Z independent"
(markov(X, Y, Z) & indep(X, Y)).exists(Y).simplified()
A, B, C = rv("A, B, C", alg="abelian") # Abelian-group-valued RVs
# Entropy of sum (or product) is submodular [Madiman 2008]
(indep(A, B, C) >> (H(A*B*C) + H(B) <= H(A*B) + H(B*C))).solve(full=True)
# Entropy form of Ruzsa triangle inequality [Ruzsa 1996], [Tao 2010]
(indep(A, B, C) >> (H(A/C) <= H(A/B) + H(B/C) - H(B))).solve(full=True)
# Define Gács-Körner common information [Gács-Körner 1973]
gkci = ((H(V|X) == 0) & (H(V|Y) == 0)).maximum(H(V), V)
# Define Wyner's common information [Wyner 1975]
wci = markov(X, U, Y).minimum(I(U & X+Y), U)
# Define common entropy [Kumar-Li-El Gamal 2014]
eci = markov(X, U, Y).minimum(H(U), U)
(gkci <= I(X & Y)).solve() # Gács-Körner <= I(X;Y)
(I(X & Y) <= wci).solve() # I(X;Y) <= Wyner
(wci <= emin(H(X), H(Y))).solve() # Wyner <= min(H(X),H(Y))
(gkci <= wci).solve(full=True) # Output proof of Gács-Körner <= Wyner
# Automatically discover inequalities among quantities
universe().discover([X, Y, gkci, wci, eci])
X, Y, Z = rv("X, Y, Z")
M1, M2 = rv_array("M", 1, 3)
R1, R2 = real_array("R", 1, 3)
model = CodingModel()
model.add_node(M1+M2, X, label="Enc") # Encoder maps M1,M2 to X
model.add_edge(X, Y) # Channel X -> Y -> Z
model.add_edge(Y, Z)
model.add_node(Y, M1, label="Dec 1") # Decoder1 maps Y to M1
model.add_node(Z, M2, label="Dec 2") # Decoder2 maps Z to M2
model.set_rate(M1, R1) # Rate of M1 is R1
model.set_rate(M2, R2) # Rate of M2 is R2
model.graph() # Draw diagram
# Inner bound via [Lee-Chung 2015], give superposition region [Bergmans 1973], [Gallager 1974]
r = model.get_inner(is_proof=True) # Display codebook, encoding and decoding info
r.display(note=True)
# Automatic outer bound with 1 auxiliary, gives superposition region
model.get_outer(1)
# Converse proof, print auxiliary random variables
(model.get_outer() >> r).solve(display_reg=False)
# Output the converse proof
(model.get_outer(is_proof = True) >> r).proof()
r.maximum(R1 + R2, [R1, R2]) # Max sum rate
r.maximum(emin(R1, R2), [R1, R2]) # Max symmetric rate
r.exists(R1) # Eliminate R1, same as r.projected(R2)
# Eliminate Z, i.e., taking union of the region over all choices of Z
# The program correctly deduces that it suffices to consider Z = Y
r.exists(Z).simplified()
# Zhang-Yeung inequality [Zhang-Yeung 1998] cannot be proved by Shannon-type inequalities
(2*I(Z&W) <= I(X&Y) + I(X & Z+W) + 3*I(Z&W | X) + I(Z&W | Y)).solve()
# Using copy lemma [Zhang-Yeung 1998], [Dougherty-Freiling-Zeger 2011]
# You may use the built-in "with copylem().assumed():" instead of the below
with eqdist([X, Y, U], [X, Y, Z]).exists(U).forall(X+Y+Z).assumed():
# Prove Zhang-Yeung inequality, and print how the copy lemma is used
display((2*I(Z&W) <= I(X&Y) + I(X & Z+W) + 3*I(Z&W | X) + I(Z&W | Y)).solve())
# State the copy lemma
r = eqdist([X, Y, U], [X, Y, Z]).exists(U)
# Automatically discover non-Shannon-type inequalities using copy lemma
r.discover([X, Y, Z, W]).simplified()
Refer to https://github.com/cheuktingli/psitip#references
Madiman, Mokshay. "On the entropy of sums." 2008 IEEE Information Theory Workshop. IEEE, 2008.
Ruzsa, Imre Z. "Sums of finite sets." Number Theory: New York Seminar 1991-1995. Springer, New York, NY, 1996.
Tao, Terence. "Sumset and inverse sumset theory for Shannon entropy." Combinatorics, Probability and Computing 19.4 (2010): 603-639.
Peter Gacs and Janos Korner. Common information is far less than mutual information.Problems of Control and Information Theory, 2(2):149-162, 1973.
A. D. Wyner. The common information of two dependent random variables. IEEE Trans. Info. Theory, 21(2):163-179, 1975.
G. R. Kumar, C. T. Li, and A. El Gamal, "Exact common information," in Proc. IEEE Symp. Info. Theory. IEEE, 2014, pp. 161-165.
Si-Hyeon Lee and Sae-Young Chung, "A unified approach for network information theory," 2015 IEEE International Symposium on Information Theory (ISIT), IEEE, 2015.
Bergmans, P. "Random coding theorem for broadcast channels with degraded components." IEEE Transactions on Information Theory 19.2 (1973): 197-207.
Gallager, Robert G. "Capacity and coding for degraded broadcast channels." Problemy Peredachi Informatsii 10.3 (1974): 3-14.
Z. Zhang and R. W. Yeung, "On characterization of entropy function via information inequalities," IEEE Trans. Inform. Theory, vol. 44, pp. 1440-1452, Jul 1998.
Randall Dougherty, Chris Freiling, and Kenneth Zeger. "Non-Shannon information inequalities in four random variables." arXiv preprint arXiv:1104.3602 (2011).