# WUSTL ESE 523 - ESE523Lect72013(1) (24 pages)

Previewing pages 1, 2, 23, 24 of 24 page document
View Full Document

## ESE523Lect72013(1)

Previewing pages 1, 2, 23, 24 of actual document.

View Full Document
View Full Document

## ESE523Lect72013(1)

76 views

Pages:
24
School:
Washington University in St. Louis
Course:
Ese 523 - Information Theory

Unformatted text preview:

ESE 523 Information Theory Lecture 7 Joseph A O Sullivan Samuel C Sachs Professor Electrical and Systems Engineering Washington University 2120E Green Hall 211 Urbauer Hall 314 935 4173 jao wustl edu 9 25 2013 J A O Sullivan ESE 523 Lecture 7 1 Graphs and entropy Random walks on undirected graphs Random walks on directed graphs Maximum entropy distributions on graphs 3 9 25 2013 J A O Sullivan ESE 523 Lecture 7 Random Walks on Undirected Graphs Assume positive weights are assigned to each edge Assume that a random walk takes place on the graph with one step at each time Assume that the probability that an edge is used given that the walk is at a node on that edge equals the weight of that edge divided by the sum of the weights of all edges attached to that node Find the entropy rate of the resulting random process Comment this is a time invariant Markov chain Comment the Markov chain is reversible the weight matrix is symmetric so backward probabilities are the same as forward Pij Wij W ik k W W ij i j j i 2W Wik i k 4 9 25 2013 J A O Sullivan ESE 523 Lecture 7 Random Walks on Undirected Graphs i W ik k 2W Wi 2W Wij The stationary distribution is Wi Wij i P i i ij i 2W W 2W easily found i Special case all weights equal Wj i i Pij 2W 1 entropy of edge fraction minus the entropy of the node H X P log P i ij ij i j fraction Adjacency matrix 0 1 A 1 0 1 9 25 2013 1 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 J A O Sullivan ESE 523 Lecture 7 H X i j Wij H X H 2W Wij 1 Eij Wij 2W log Wij Wi Wi H 2W 5 Undirected Graphs Adjacency Matrix Maximum Entropy Walk Compute the adjacency matrix A ones if an edge exists here A is symmetric If the adjacency matrix raised to a power k is strictly positive then the resulting Markov chain is strongly connected irreducible and aperiodic Comment the adjacency matrix computes combinatorics how many sequences walks exist A Aij Aij 1 Wij 0 Otherwise Aij 0 N ij k A k ij 1 log N ij k log max k k max largest eigenvalue of A of length k starting at

View Full Document

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...