Problem $3(20$ points$)$: Computational Aspects The National Intelligence Agency $($ANI$)$ is tracking a

group suspected of involvement in serious crimes. To catch the group, the ANI has decided to create different

security zones for constant monitoring. described through the following network:

The agency knows that each day the group moves from one zone to another as follows: it uniformly

randomly selects one of the neighboring zones in the network $($i$.$e$.,$ a zone with which it has a connection$)$

and moves to that zone. For example, if the group is in zone $a,$ it can move to zone $g$ or $b$ with a probability

of $\frac{1}{2}$ for each case. To better understand the dynamics of the group, the ANI has contacted you as an

expert in stochastic modeling. Let $(x_t{)}_{\text{t}\text{i}\text{n}\text{N}}$ be the process that describes the zone of the network where the

group is located during day $t.$

$($a$)$ Argue why the process $(x_t{)}_{\text{t}\text{i}\text{n}\text{N}}$ is a Markov Chain.

$($b$)$ Write the transition matrix of the chain and draw the transition graph.

$($c$)$ How many communication classes does this chain have? Is it irreducible and aperiodic?

$($d$)$ Write the system of equations that determines the stationary distribution of the chain.

$($e$)$ Briefly argue why the chain has a unique stationary distribution.

$($f$)$ For each zone $v$ of the network, let $d(v)$ be the number of neighboring zones, and let $m$ be the total

number of connections in the network. For the ANI network, the total number of connections is $m=10,$

and for example, the number of neighboring zones of $a$ is $d(a)=2.$ For each zone $v,$ let $(v)=\frac{d(v)}{2m}.$

Verify that $$ is a stationary distribution of the chain. Using the previous part, conclude that it is the

unique stationary distribution.

$($g$)$ Calculate the return times $E_v({}_v)$ for each zone $v$ of the network.

$($h$)$ In the stationary state, which node is visited most frequently by the chain?

$($i$)$ Suppose that the ANI is certain that the group was in zone $a$ at the start of the process. Compute

the probability distribution ${}_t$ over the zones of the network after $t=3,t=10,$ and $t=30$ days. How

different are these vectors? How do they compare to the stationary distribution? Comment.

$($j$)$ Now suppose that the group was initially in zone $a.$ Compute the probability that the criminal group

visits zone $d$ for the first time after three days. Also, compute the probability of visiting zone $d$ for the

first time after four days.