Markov Chains (Project-3)

Problem Description

• A computer is shared by 2 users who send tasks to a computer remotely and work independently.

• At any minute, any connected user may disconnect with probability 0.5, and any disconnected user may connect with a new task with probability 0.2.

• Let X(t) be the number of concurrent users at time t (in minutes).

• This is a markov chain with 3 states: 0, 1, and 2.

• The probability transition matrix can be calculated and it is:

##      [,1] [,2] [,3]
## [1,] 0.64 0.32 0.04
## [2,] 0.40 0.50 0.10
## [3,] 0.25 0.50 0.25

• Generate 10,000 transitions of the Markov chain. What percent of times do you find your generated Markov chain in each of its 3 states?

Steady-state distribution

The steady-state distribution tells us that, over a long-period of time:

• about 51.02% of the minutes, there will be 0 users connected
  
• about 40.82% of the minutes there will be 1 user connected
• and about 8.16% of the minutes there will be 2 users connected

If h is small, these probabilities would be impacted by the initial state (# of users), but as h increases (in this case, the # of minutes increases), the probabilities will tend towards a limit shown below.

##           [,1]      [,2]       [,3]
## [1,] 0.5102041 0.4081633 0.08163265
## [2,] 0.5102041 0.4081633 0.08163265
## [3,] 0.5102041 0.4081633 0.08163265

First 50 transitions

As seen above, the initial state (initial # of users) won’t impact the probabilities in the long-run. So, in this case, I will assume both users are connected a t = 0 minutes, although there could be just as easily 0 or 1 users connected at t = 0 minutes.

Shown below are the first 50 transitions. At t = 0, both users are connected. After 1 minute, there is only 1 user, after 2 minutes, there are 0 users connected, …

After 10,000 transitions, we see that:

• 50.75% of the minutes has 0 users connected
• 41.19% of the minutes has 1 user connected
• and 8.06% of the minutes has 2 users connected

##  [1] 1 0 0 1 2 1 0 1 0 0 1 1 0 0 0 1 1 1 1 2 0 1 0 2 2 2 2 2 1 1 2 0 1 0 0 0 1 1
## [39] 1 1 1 1 1 1 1 1 1 1 1 0

##    0    1    2 
## 5075 4119  806

Discussion

From above, we can see that the theoretical and experimental # of users are very close, as we would expect. Over the long-run (in this case, 10,000 transitions or minutes), there will be 0 users connected about 51% of the time, 1 user connected 41% of the time, and both users connected 8% of the time.

This experiment demonstrates the practicality of markov chains and transition probability matrices to determine long-term probabilities.

This makes me want to study and implement markov chains with stocks, where long-term probabilities can result in large monetary gains.

Code

# probability transition matrix
P = matrix(c(0.64, 0.40, 0.25, 0.32, 0.50, 0.50, 0.04, 0.10, 0.25), nrow = 3)
P

# steady state distribution, taking the h = 60-step transition probability matrix
# no matter the initial # of users, after 1 hour the probability there are 0 users connected is 51%, 1 user is 41%, and 2 users is 8%.
h <- 60
P.new = P
for (k in 2:h){
  P.new = P.new %*% P
}
P.new

# generating 10,000 transitions
set.seed(123)
states <- c(0, 1, 2)
current_state <- 2
t <- 10000
transitions <- c()

for (i in 1:t){
  # probabilities correspond to row in the probability transition matrix
  # +1 because state 0 corresponds with row 1, state 1 with row 2, state 2 with row 3.
  p = c(P[current_state + 1, ])
  current_state = sample(states, 1, prob = p)
  transitions[i] = current_state
}

# # of times in each state
summary(as.factor(transitions))