Model selection: History-dependent stochastic processes and Markov chains

Website TUEindhoven TU Eindhoven, Dept. of Mathematics & Computer SCience

Eindhoven University of Technology (TU/e) is a research university specializing in engineering science & technology.

BSc project

Model selection: History-dependent stochastic processes and Markov chains

Many cutting-edge applications rely on fitting models to large amounts of data. The data is typically generated by a dynamical process according to some hidden, unknown law, think for instance of the positions and velocities of soccer players during a game. One way to make predictions on the development of the game is to fit a stochastic model to the position and velocity data. Almost always, the fitted model, e.g. a Markov model, is an oversimplification of the true process. The true underlying process of a soccer game is clearly not a Markov process. In such a case, where there is a clear mismatch between models, what does the fitted model still have to say about the true system? Is it even still valuable?

We aim to analyze the effects of model selection in abstract time-dependent systems. Specifically, we will investigate what happens when we model a history-dependent stochastic process \(\{ X_t \}_{t \geq 0}\) naively by a Markov chain \(\{ Y_t \}_{t \geq 0}\). Here we assume that both processes live on the same state space of size \(n\). We wonder how good of a model a Markov chain can be if e.g.
P( X_{t+1} = x_{t+1} | X_t = x_t, X_{t-1} = x_{t-1}, …, X_0 = x_0 )
= P( X_{t+1} = x_{t+1} | X_t = x_t, X_{t-h_n} = x_{t-h_n} )
= Q_{x_{t-h_n},x_t,x_{t+1}},
$$ where \(h_n\) may either be constant or a function of \(n\). Recall that Markov chains are fundamental models for time-dependent random processes in which future and past weakly depend on each other, and that in Markov chains it is assumed that
P( Y_{t+1} = y_{t+1} | Y_t = y_t, Y_{t-1} = y_{t-1}, …, Y_0 = y_0 )
= P( X_{t+1} = y_{t+1} | Y_t = y_t )
= P_{y_t,y_{t+1}}.
$$ In other words, a Markov chain allows for less dependency on the past than what the process \(\{ X_t \}_{t \geq 0}\) actually needs.

In this project, you will first investigate under which conditions on \(Q, h_n\), and \(n\) such a history-dependent stochastic process may be well-approximated by a Markov chain with transition matrix \(P\). This involves bounding a distance measure between distributions – an example being the Kullback-Leibler divergence \(KL(P \| Q)\). For large state spaces with large \(h_n\), the time-correlations may become asymptotically negligible. Next, we will define for fixed \(Q, h_n, n\) a “best” Markov chain; one that uses for example the transition matrix \(P^* = \arg \min_{P} KL(P \| Q)\). For this specific Markov chain, we will then answer how good this somewhat naively chosen “best” approximation to the history-dependent process works as a substitute. This requires us to bound quantities such as \(E( | f(X_t) – f(Y_t) | )\) and \(P( f(X_t) \neq f(Y_t) )\) for given functions \(f\).


In this BSc project, you will:

  1. Carry out a literature study on model selection for history-dependent processes, and Markov chains.
  2. Give an overview of mixing time results for Markov chains and for history-dependent processes, if any exist for the latter.
  3. Determine under which conditions on \(Q, h_n, n\) the aforementioned history-dependent stochastic process may be well-approximated by a Markov chain with some transition matrix \(P\).
  4. Analyze how well a naively chosen “best” Markov chain approximation to the history-dependent can function, for different objective functions.

To apply for this job email your details to jaron.sanders@tue.nl

Jaron Sanders received in 2012 M.Sc. degrees in Mathematics and Physics from the Eindhoven University of Technology, The Netherlands, as well as a PhD degree in Mathematics in 2016. After he obtained his PhD degree, he worked as a post-doctoral researcher at the KTH Royal Institute of Technology in Stockholm, Sweden. Jaron Sanders then worked as an assistant professor at the Delft University of Technology, and now works as an assistant professor at the Eindhoven University of Technology. His research interests are applied probability, queueing theory, stochastic optimization, stochastic networks, wireless networks, and interacting (particle) systems.