Suppose we have a machine which switches between four different tasks 1, 2, 3, 4 as follows: all tasks are repeated with chance 0.5; after task 1 it switches to task 2 with chance 0.3 and to task 4 with chance 0.2; after task 2 it switches to task 4 with chance 0.5; after task 3 it switches to task 4 with chance 0.5; after task 4 it switches to task 1 with chance 0.5.

(a) Determine the communicating classes of the process recording the task # the machine is in, and prove which states are transient and which are recurrent.

(b) If there is a cost associated to switching tasks whose value is r(i, j) = i + j for any i 6= j {1, 2, 3, 4} and r(i, i) = i for any i {1, 2, 3, 4}, calculate the long run cost of switching tasks starting from any recurrent state, and calculate the expected cost of repeating a task for any transient state.