How do I tune the probabilities in a Markov chain based load test to produce specific hit rates?

Question

I am writing a load test for a web application. I have a few month's worth of access logs that tell me relative hit rates of various URLs. However, the access logs do not contain enough information to tell me where a user is likely to click next. In other words, the access logs cannot help me deduce whether, given that a user is currently on page A, they are more likely to go to page B or page C.

I know which page transitions are possible, i.e. you can navigate directly from page A to page B, but not from page A to page D. I can use that information to construct a graph. If I weight the edges of the graph subject to certain constraints (e.g. the sum of the weights of all edges out of a node must equal 1), I will have a Markov chain. I would like to use the Markov chain to model variability in user behavior, but it is not obvious how to assign the weights.

If I know the relative hit rates that I want to achieve, and I know the Markov's chain's structure but not its weights, what techniques are available for assigning the weights?

Answer 1

This is a pretty interesting problem, actually :)

You could try using a Markov Chain Monte Carlo approach. I haven't worked with these types of models myself, but the idea is that you start with a given long-run distribution and use Monte Carlo modelling to develop the actual Markov chain. I know this is a pretty well-used technique for simulation calculations. If you don't know much about Monte Carlo methods, don't worry, the basic ideas are quite simple (and powerful).

You could also try a PageRank algorithm approach. The idea would be to construct your page links and initially assign equal weights based on the link structure (ie the user is equally likely to visit any possible linked page from the current page) and then assign a small chance that the user will visit any page uniformly randomly (they "surf" somehow to a random page uniformly at random). This can help develop a Markov chain with some realistic aspects of your system, such as that pages with more links are visited more often, but it's possible that every page can be visited at some point. The nice thing about models generated using a PageRank algorithm is that they lend themselves well to analysis, both computationally and analytically. (EDIT: I guess this method might not be exactly what you're looking for, since you already have the hit rates determined. But it might be helpful if you want to generate realistic "general" data for your hit rates.)

Hope this helps out.