Let G Be A Connected Undirected Graph With N Nodes And L Links For Each I 1

Let G be a connected undirected graph with N nodes and L links. For each i ∈ {1, . . . , N} define di as the degree of nodei, being the number of links it is attached to. We take a random walk over the graph according to the following CTMC: Whenwe visit a new node i, we stay there for an independent and exponentially distributed time with rate vi. We then choose tovisit a new node j independently and uniformly over all neighboring nodes.a) Make a guess about the steady state distribution for each state i ∈ {1, . . . , N} in terms of di and vi.b) Verify your guess with the detail equations.c) For the same graph, consider a discrete time Markov chain (DTMC) where, every slot t, we move to a new nodeindependently and uniformly over all neighboring nodes. Show that the discrete time detail equations πiPij = πjPji aresatisfied for a particular guess probably mass function πi for i ∈ {1, . . . , N}.d) Consider the following modification to the DTMC in part (c): We transition according to the same DTMC. However,we stay in each state i for an independent random amount of time that has a general distribution with mean E [Ti]. It canbe shown that the fraction of time in each state i is proportional to πiE [Ti], where πiis the steady state distribution of thediscrete time chain. Verify this is true for the special case when Tiis exponentially distributed with rate µi. It follows that thesteady state results for the CTMC in part (b) are the same even if the time in each state is not exponentially distributed

Leave a Reply

Your email address will not be published. Required fields are marked *