Tree approximation for discrete time stochastic processes: a process distance approach

Kovacevic, Raimund; Pichler, Alois
December 2015
Annals of Operations Research;Dec2015, Vol. 235 Issue 1, p395
Academic Journal
Approximating stochastic processes by scenario trees is important in decision analysis. In this paper we focus on improving the approximation quality of trees by smaller, tractable trees. In particular we propose and analyze an iterative algorithm to construct improved approximations: given a stochastic process in discrete time and starting with an arbitrary, approximating tree, the algorithm improves both, the probabilities on the tree and the related path-values of the smaller tree, leading to significantly improved approximations of the initial stochastic process. The quality of the approximation is measured by the process distance (nested distance), which was introduced recently. For the important case of quadratic process distances the algorithm finds locally best approximating trees in finitely many iterations by generalizing multistage k-means clustering.


Related Articles


    The paper considers a set of linear discrete-time systems with uncertain parameters. A method of synthesis of robust control which simultaneously stabilizes all the systems from this set is proposed. This method consists of two steps. First, a set of stochastic comparison systems with...

  • A Tabu Search Based Approximate Solution Algorithm for κ-minimum Spanning Tree Problems. Katagiri, Hideki; Nishizaki, Ichiro; Hayashida, Tomohiro; Ishimatsu, Jun // International MultiConference of Engineers & Computer Scientists;2009, p2026 

    This paper considers k-minimum spanning tree problems. An existing solution algorithm based on tabu search includes an iterative procedure of applying an exact solution method to obtain a local optimal solution. This article provides a new tabu search based approximate solution method that does...

  • Iterated function system models in data analysis: Detection and separation. Alexander, Zachary; Meiss, James D.; Bradley, Elizabeth; Garland, Joshua // Chaos;Jun2012, Vol. 22 Issue 2, p023103 

    We investigate the use of iterated function system (IFS) models for data analysis. An IFS is a discrete-time dynamical system in which each time step corresponds to the application of one of the finite collection of maps. The maps, which represent distinct dynamical regimes, may be selected...

  • The iteration-approximation decoupling in the reversible KAM theory. Sevryuk, M.B. // Chaos;Sep95, Vol. 5 Issue 3, p552 

    Discusses the presence of iterative methods and approximation decoupling theory in the reversible Kolmogorov-Arnold-Moser (KAM) theory. Method on showing the persistence of quasiperiodic motions in reversible flows; Nondegeneracy conditions obtained by a new method.

  • Stability of Semi-Implicit and Iterative Centered-Implicit Time Discretizations for Various Equation Systems Used in NWP. Bénard, P. // Monthly Weather Review;Oct2003, Vol. 131 Issue 10, p2479 

    The stability of the classical semi-implicit scheme and some more advanced iterative schemes recently proposed for NWP purposes is examined. In all of these schemes, the solution of the centered-implicit nonlinear equation is approached by an iterative fixed-point algorithm, preconditioned by a...

  • Solutions of the generalized Bogomol’nyi equations via monotone iterations. Wang, Sheng; Yang, Yisong // Journal of Mathematical Physics;Dec92, Vol. 33 Issue 12, p4239 

    This paper is concerned with the numerical solutions of the classical Abelian Higgs vortex model in R2 in the critical coupling phase. A globally convergent monotone iterative method will be presented to approximate finite energy multivortex solutions of both the classical and the generalized...

  • Direct inversion in the iterative subspace (DIIS) optimization of open-shell, excited-state, and small multiconfiguration SCF wave functions. Hamilton, Tracy P.; Pulay, Peter // Journal of Chemical Physics;5/15/1986, Vol. 84 Issue 10, p5728 

    The direct inversion in the iterative subspace (DIIS) method is applied to several simple SCF wave functions in an effective Fock matrix formulation. The following cases are treated: high-spin-restricted open shell, open-shell singlet, and two-configuration wave functions. Open-shell singlet...

  • Existence of nontrivial solutions for a nonlinear fourth-order boundary value problem via iterative method. Chengbo Zhai; Chunrong Jiang // Journal of Nonlinear Sciences & Applications (JNSA);2016, Vol. 9 Issue 6, p4295 

    In this article, we study a nonlinear fourth-order differential equation two-point boundary value problem. We use monotone iterative technique and lower and upper solutions of completely continuous operators to get the existence of nontrivial solutions for the problem. The results can guarantee...

  • Bounding Synchronization Overhead for Parallel Iteration. Downey, Peter J. // ORSA Journal on Computing;Fall91, Vol. 3 Issue 4, p288 

    Suppose m stochastically identical iterative processes are run in parallel. Each iteration of the process runs for a random lime X, distributed identically and independently for each iteration. At the end of each iteration, each process cheeks a shared variable to see whether some global event...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics