3. 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 >> 1 there are members ₁, ₂, ..., an such that Members i and a₁ are friends,

Members a₁ and a₂ are friends, Members a2 and a3 are friends, and so on, and Members an, and j are friends.

Consider a network of m members. For 1 ≤ i ≤ m let f; be the number of friends of Member i, and assume that fa fb for some members a and b. Also

assume that every member is linked to every other member.

Let X0, X₁, X₂, ... 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's friends.

• If the selected friend is Member j, then:

▪ If fj < fi, move to j.

▪ If f; > fi, toss a coin that lands heads with chance filf;. If it lands heads, move to j. If it lands tails, stay at i.

a) For states i # j, find the one-step transition probability P(i, j) = P(X₁ =j | Xo = 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