$2.$ Social Network

A social network consists of a finite set of members. Members $i$ and $j$ are said to be $*$linked$*$ if either they are friends or they are $*$friends of friends$*$ which is shown in an example and then formally defined below.

As an example, here is a social network that has five members A$,$ B$,$ C$,$ D$,$ and E$.$ Friends are any two members that are connected by one line segment. For example, A and B are friends, and C and E are friends. Member A has $3$ friends; B$,$ C and D have one friend each; and E has two friends. Members B and C aren't friends but they are linked by the sequence of friends BAEC.

$$

Formally, Members $i$ and $j$ are linked if either they are friends or for some $n $\backslash$ge $1$$ there are members $a$\_1,$ a$\_2,\backslash$ldots$,$ a$\_$n$ such that Members $i$ and $a$\_1$$ are friends, Members $a$\_1$$ and $a$\_2$$ are friends, Members $a$\_2$$ and $a$\_3$$ are friends, and so on$,$ and Members $a$\_$n$ and $j$ are friends.

Consider a network of $m$ members. For $$1\backslash$le i $\backslash$le m$ let $f$\_$i$ be the number of friends of Member $i$$,$ and assume that $f$\_$a

e f$\_$b$ for some members $a$ and $b$$.$ Also assume that every member is linked to every other member.

Let $X$\_0,$ X$\_1,$ X$\_2,\backslash$ldots$ be a Markov Chain on the set of members, with transitions based on the following proposal scheme. Given that the chain is at Member $i$:

$-$ Select a friend uniformly at random from all of Member $i$$\text{'}$s friends.

$-$ If the selected friend is Member $j$$,$ then:

$-$ If $f$\_$j $\backslash$le f$\_$i$$,$ move to $j$$.$

$-$ If $f$\_$j $>$ f$\_$i$$,$ toss a coin that lands heads with chance $f$\_$i $/$ f$\_$j$$.$ If it lands heads, move to $j$$.$ If it lands tails, stay at $i$$.$

$**$a$)**$ For states $i

e j$$,$ find the one$-$step transition probability $P$($i$,$ j$)=$ P$($X$\_1=$ j $\backslash$mid X$\_0=$i$)$$$.$

$**$b$)**$ Briefly explain why the chain has a steady state distribution, and find that distribution. Identify it as one of the famous ones and provide its name and parameters.