$(4)$ A weighted graph is an undirected graph where each edge is given a positive weight.

See example below.

The weight of each node is defined to be the sum of the weights of the edges

touching that node. In the example, node $1$ has weight $6.$

We can define a Markov matrix $P$ associated with this weighted graph. Entry

$P(i,j)$ is defined to be $0$ if there is no edge between nodes i and $j$ in the graph. If

there is an edge between i and $j,$ then $P(i,j)$ equals the weight of that edge divided

by the weight of node $j.$ In the example, we have $P(2,1)=\frac{3}{6},P(4,1)=\frac{2}{6}$ and

$P(5,1)=\frac{1}{6}.$ The idea is that from node $j,$ the next destination is chosen with

probabilities proportional to the weights on the edges emanating from $j.$ If all the

edge weights are $1,$ we obtain the simple random walk on the graph.

$($a$)$ Write down the Markov matrix $P$ associated with the weighted graph above.

$($b$)$ Verify for this specific $P$ that the vector $w=(w_1,$dots,$w_5{)}^{TT},$ where $w_i$ is the

weight of node $i,$ satisfies $Pw=w.$

$($c$)$ Consider a general graph with nodes $1,2,$dots,$n$ and edge weights $w_{ij}0.($If

$w_{ij}=0,$ that means the nodes i and $j$ are not connected by an edge.$)$ Since the

graph is undirected, we have $w_{ij}=w_{ji}$ for all $i,j.$ The weight of each node $j$ is

$w_j={\displaystyle \underset{i=1}{\overset{n}{}}}{w}_{ij},$

and we have $P(i,j)=\frac{w_{ij}}{w_j}.$ Show that the vector $w=(w_1,$dots,$w_n{)}^{TT}$ satisfies

the detailed balance property $($see Problem $3).$ It follows from Problem $3($d$)$

that $Pw=w.$