Mean-field drift of the RANDOM(m) multi-list cache. More...

#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for cache_rrm_meanfield_ode.h:

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
std::vector< T >	line::cache::cache_rrm_meanfield_ode (const std::vector< T > &x, const std::vector< T > &lambda, const std::vector< int > &m)
	Mean-field drift of the RANDOM(m) multi-list cache.

Detailed Description

Mean-field drift of the RANDOM(m) multi-list cache.

Templated port of matlab/src/api/cache/cache_rrm_meanfield_ode.m, cross-checked against jar/src/main/java/jline/api/cache/ Cache_rrm_meanfield_ode.java.

The state x(k,s) is the probability that item k occupies list s, with s = 0 meaning "not cached". A request for item k while it is in list s promotes it to list s+1 and demotes a uniformly chosen occupant of list s+1; hence the drift

dx(k,s)/dt = lambda(k) x(k,s-1)

sum_j lambda(j)/m(s) x(j,s-1) x(k,s)
sum_j lambda(j)/m(s+1) x(j,s) x(k,s+1) - lambda(k) x(k,s)

for 1 <= s < h, without the last two terms at s = h (an item already in the top list stays there), and dx(k,0)/dt = -sum_{s>=1} dx(k,s)/dt so that each item's occupancies stay on the simplex.

Bilinear in x with rational coefficients, so the drift is a field expression: no transcendental requirement, and the exact instantiation evaluates it without rounding. Note this is the right-hand side only. The steady state (matlab's cache_rrm_meanfield script) needs a stiff ODE integrator, which is out of scope for this header.

The state vector is flat in MATLAB's column-major reshape order: x[k + s*n] is x(k,s), k = 0..n-1 the item and s = 0..h the level.

Definition in file cache_rrm_meanfield_ode.h.

Namespaces

Functions

Detailed Description