library(markovchain)
weatherStates <- c("sunny", "cloudy", "rain")
byRow <- TRUE
weatherMatrix <- matrix(data = c(0.7, 0.2, 0.1, 0.3, 0.4, 0.3, 0.2, 0.45, 0.35),
byrow = byRow, nrow = 3, dimnames = list(weatherStates, weatherStates))
mcWeather <- new("markovchain", states = weatherStates, byrow = byRow, transitionMatrix = weatherMatrix,
name = "Weather")
show(mcWeather)
## Weather
## A 3 - dimensional discrete Markov Chain with following states
## sunny cloudy rain
## The transition matrix (by rows) is defined as follows
## sunny cloudy rain
## sunny 0.7 0.20 0.10
## cloudy 0.3 0.40 0.30
## rain 0.2 0.45 0.35
initialState <- c(0, 1, 0)
after2Days <- initialState * (mcWeather * mcWeather)
after7Days <- initialState * (mcWeather^7)
after2Days
## sunny cloudy rain
## [1,] 0.39 0.355 0.255
library(igraph)
mcIgraph <- as(mcWeather, "igraph")
plot(mcIgraph)
steadyStates(mcWeather)
## sunny cloudy rain
## [1,] 0.4636 0.3182 0.2182
Commençons par définir notre chaîne de Markov.
N = 8
a = 0.3
b = (1 - a)/(N - 1)
trans = seq(from = 0, to = 0, length.out = N * N)
trans[1] = a
for (i in 2:N) {
trans[i + N * (i - 1)] = (i - 1) * b
trans[1 + N * (i - 1)] = a
trans[i + N * (i - 2)] = (N - i + 1) * b
}
States <- as.character(1:N)
byRow <- TRUE
MTFMatrix <- matrix(data = trans, byrow = byRow, nrow = N, dimnames = list(States,
States))
mcMTF <- new("markovchain", states = States, byrow = byRow, transitionMatrix = MTFMatrix,
name = "Move to front")
show(mcMTF)
## Move to front
## A 8 - dimensional discrete Markov Chain with following states
## 1 2 3 4 5 6 7 8
## The transition matrix (by rows) is defined as follows
## 1 2 3 4 5 6 7 8
## 1 0.3 0.7 0.0 0.0 0.0 0.0 0.0 0.0
## 2 0.3 0.1 0.6 0.0 0.0 0.0 0.0 0.0
## 3 0.3 0.0 0.2 0.5 0.0 0.0 0.0 0.0
## 4 0.3 0.0 0.0 0.3 0.4 0.0 0.0 0.0
## 5 0.3 0.0 0.0 0.0 0.4 0.3 0.0 0.0
## 6 0.3 0.0 0.0 0.0 0.0 0.5 0.2 0.0
## 7 0.3 0.0 0.0 0.0 0.0 0.0 0.6 0.1
## 8 0.3 0.0 0.0 0.0 0.0 0.0 0.0 0.7
À quoi cette chaîne ressemble-t-elle ?
mcIgraph <- as(mcMTF, "igraph")
plot(mcMTF)
## Loading required package: Matrix
Et le régime permanent ?
ssMTF = steadyStates(mcMTF)
ssMTF
## 1 2 3 4 5 6 7 8
## [1,] 0.3 0.2333 0.175 0.125 0.08333 0.05 0.025 0.008333
Commençons par définir notre chaîne de Markov.
trans = seq(from = 0, to = 0, length.out = N * N)
trans[1] = a + (N - 2) * b
for (i in 2:N) {
trans[i + N * (i - 1)] = (N - 2) * b
trans[i - 1 + N * (i - 1)] = a
trans[i + N * (i - 2)] = b
}
trans[N * N] = (N - 1) * b
States <- as.character(1:N)
byRow <- TRUE
MAMatrix <- matrix(data = trans, byrow = byRow, nrow = N, dimnames = list(States,
States))
mcMA <- new("markovchain", states = States, byrow = byRow, transitionMatrix = MAMatrix,
name = "Move Ahead")
show(mcMA)
## Move Ahead
## A 8 - dimensional discrete Markov Chain with following states
## 1 2 3 4 5 6 7 8
## The transition matrix (by rows) is defined as follows
## 1 2 3 4 5 6 7 8
## 1 0.9 0.1 0.0 0.0 0.0 0.0 0.0 0.0
## 2 0.3 0.6 0.1 0.0 0.0 0.0 0.0 0.0
## 3 0.0 0.3 0.6 0.1 0.0 0.0 0.0 0.0
## 4 0.0 0.0 0.3 0.6 0.1 0.0 0.0 0.0
## 5 0.0 0.0 0.0 0.3 0.6 0.1 0.0 0.0
## 6 0.0 0.0 0.0 0.0 0.3 0.6 0.1 0.0
## 7 0.0 0.0 0.0 0.0 0.0 0.3 0.6 0.1
## 8 0.0 0.0 0.0 0.0 0.0 0.0 0.3 0.7
À quoi cette chaîne ressemble-t-elle ?
mcIgraph <- as(mcMA, "igraph")
plot(mcMA)
Et le régime permanent ?
ssMA = steadyStates(mcMA)
ssMA
## 1 2 3 4 5 6 7 8
## [1,] 0.6668 0.2223 0.07409 0.0247 0.008232 0.002744 0.0009146 0.0003049
Pour chacune des deux stratégies, la probabilité d'avoir un défaut de page de la page \( A \) quand le cache peut contenir \( M \) pages s'écrit \( p(M)=\sum_{i>M} \pi_i \).
Donc pour MTF on a:
1 - cumsum(ssMTF)
## [1] 0.700000 0.466667 0.291667 0.166667 0.083333 0.033333 0.008333 0.000000
Et pour MA, on a:
1 - cumsum(ssMA)
## [1] 0.3332317 0.1109756 0.0368902 0.0121951 0.0039634 0.0012195 0.0003049
## [8] 0.0000000
La probabilité d'avoir un défaut de la page A est donc bien plus faible avec MA qu'avec MTF, quelle que soit la taille du cache.
Mais ce qui nous intéresse, c'est la probabilité de défaut de cache d'une page quelconque.
Après un peu de travail, on peut montrer que \( p_g(M) = 1-Mb-(a-b)\sum_{i=1}^M \pi_i \)
Donc pour MTF on a:
1 - (1:N) * b - (a - b) * cumsum(ssMTF)
## [1] 8.400e-01 6.933e-01 5.583e-01 4.333e-01 3.167e-01 2.067e-01 1.017e-01
## [8] 5.551e-17
Et pour MA, on a:
1 - (1:N) * b - (a - b) * cumsum(ssMA)
## [1] 7.666e-01 6.222e-01 5.074e-01 4.024e-01 3.008e-01 2.002e-01 1.001e-01
## [8] 5.551e-17
Une fois encore, les probabilités de défaut de pages sont plus faibles pour MA que pour MTF. D'autre part, la probabilité d'avoir un défaut de cache ne diminue pas très rapidement avec la taille du cache.
Ceci dit, on a un modèle franchement naïf. Il serait probablement plus intéressant de considérer qu'on a plusieurs pages populaires comme la page A, et éventuellement que la popularité de ces pages est décroissante.
D'autre part, cette analyse se base sur la stationnarité et donc sur le fait que l'on a bien convergé vers l'état stationnaire. Le temps de convergence est lié à la valeur de la seconde plus grande valeur propre. Pour MTF, on a:
eigen(mcMTF@transitionMatrix, only.values = T)$values
## [1] 1.000e+00 6.000e-01 5.000e-01 4.000e-01 3.000e-01 2.000e-01 1.000e-01
## [8] 1.805e-15
eigen(mcMA@transitionMatrix, only.values = T)$values
## [1] 1.0000 0.9200 0.8449 0.7326 0.6000 0.4674 0.3551 0.2800
Donc avec MTF, le temps de convergence vers l'état stationnaire est en \( 0.6^n \) alors qu'avec MA, le temps de convergence vers l'état stationnaire est en \( 0.92^n \), soit bien plus lentement. Moralité, si MA est plus efficace du point de vue des défauts de cache, il est moins clair qu'il ait le temps d'atteindre le régime permanent. Si les fréquences d'accès au page ne sont pas assez stables dans le temps, il n'est donc pas si clair que MA soit plus efficace que MTF…