Perfect information two-person zero-sum markov games with imprecise transition probabilities

Based on an extension of the controlled Markov set-chain model by Kurano et al. (in J Appl Prob 35:293–302, 1998) into competitive two-player game setting, we provide a model of perfect information two-person zero-sum Markov games with imprecise transition probabilities. We define an equilibrium value for the games formulated with the model in terms of a partial order and then establish the existence of an equilibrium policy pair that achieves the equilibrium value. We further analyze finite-approximation error bounds obtained from a value iteration-type algorithm and discuss some applications of the model.     

Converging Marriage in Honey-Bees Optimization and Application to Stochastic Dynamic Programming

In this paper, we first refine a recently proposed metaheuristic called “Marriage in Honey-Bees Optimization” (MBO) for solving combinatorial optimization problems with some modifications to formally show that MBO converges to the global optimum value. We then adapt MBO into an algorithm called “Honey-Bees Policy Iteration” (HBPI) for solving infinite horizon-discounted cost stochastic dynamic programming problems and show that HBPI also converges to the optimal value.     

STRONG LAW OF LARGE NUMBERS AND ASYMPTOTIC EQUIPARTITION PROPERTY FOR NONSYMMETRIC MARKOV CHAIN FIELDS ON CAYLEY TREES

Some strong laws of large numbers for the frequcncies of occurrence of states and ordered couples of states for nonsymmetric Markov chain fields(NSMC)on Cayley trees are studied.In the proof,a new technique for the study of strong liinit theorems of Markov chains is extended to the case of Markov chain fields.The asymptotic equiparti- tion properties with almost everywhere(a.e.)convergence for NSMC on Cayley trees are obtained.     

SPAR: stochastic programming with adversarial recourse

We consider a general adversarial stochastic optimization model. Our model involves the design of a system that an adversary may subsequently attempt to destroy or degrade. We introduce SPAR, which utilizes mixed-integer programming for the design decision and a Markov decision process (MDP) for the modeling of our adversarial phase.     

Asymptotic properties of constrained Markov Decision Processes

We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Based on the convergence of MDPs with a truncated state space to the problem with infinite state space, we show that an optimal stationary policy exists such that the number of randomisations it uses is less or equal to the number of constraints plus one. We finally apply the results to a dynamic scheduling problem.This work was partially supported by the Chateaubriand fellowship from the French embassy in Israel and by the European Grant BRA-QMIPS of CEC DG XIII     

Random walks generated by affine mappings

This article is concerned with Markov chains on ^m constructed by randomly choosing an affine map at each stage, and then making the transition from the current point to its image under this map. The distribution of the random affine map can depend on the current point (i.e., state of the chain). Sufficient conditions are given under which this chain is ergodic.     

Extremality and the global Markov property II: The global markov property for non-FKG maximal Gibbs measures

We give a condition on a Gibbs measure for an attractive Markov specification, which assures extremality and the global Markov property. As an example of application we consider the class of attractive Markov specifications defined on a compact configuration space over a two-dimensional lattice by the interaction Hamiltonians (assumed to have a finite set of periodic ground configurations) satisfying Peierl's condition. We prove that each extremal Gibbs measure for such a specification, at sufficiently low temperature, has the global Markov property.On leave of absence from the Institute of Theoretical Physics, University of Wrocaw, Poland.     

Residence times in kink sites and Markov chain model of alloy and intermetallic compound deposition

The concept of the residence time τ_ksp of an atom in a kink site has recently been suggested to understand the processes in electrochemical deposition of alloys and intermetallic compounds. Different kink sites with different residence times must be defined for alloys and intermetallic compounds. Based on this model, the finite Markov chain theory is applied to describe the selectivity of the growth process. An analytical relationship between the alloy composition and the metal ion concentrations in the electrolyte is derived. General model parameters are ratios g _i = K _ii/K _ij of equilibrium constants of the reaction of electrolyte ions with different kink sites on the surface (i, j representing different alloy components). These ratios are called selectivity constants. For simple conditions, the equation g _i ≈ τ_ii/τ_ij connects the g _i values with the residence times. The theory is tested in the deposition of alloys Co-Ni (anomalous co-deposition) and Ni-Mo (induced co-deposition). Additionally, Bi₂Te₃, an example of stoichiometric semiconductor deposition, is treated. Published in Russian in Elektrokhimiya, 2006, Vol. 42, No. 10, pp. 1216–1223. The text was submitted by the authors in English.     

Markov processes in single molecule fluorescence

This article examines the current status of Markov processes in single molecule fluorescence. For molecular dynamics to be described by a Markov process, the Markov process must include all states involved in the dynamics and the first-passage time (FPT) distributions out of those states must be describable by a simple exponential law. The observation of non-exponential FPT distributions or other evidence of non-Markovian dynamics is common in single molecule studies and offers an opportunity to expand the Markov model to include new dynamics or states that improve understanding of the system.     

有限型的首次返回例外集的测度和维数北大核心CSCD

设M=(m_(ij))是一个b×b阶矩阵且m_(ij)∈{0,1},∑_(M)是矩阵M=(m_(ij))诱导产生的有限型,σ是其上左推移算子.本文主要研究的是有限型动力系统(∑_(M),σ)上的首次返回速度问题.令τ_(k)(x)是点x∈∑_(M)首次返回到包含x的k阶柱集时间,且E_(α,β)={x∈∑_(M):lim inf_(k→∞)(logτ_(k)(x))/k=α,lim sup_(k→∞)(logτ_(k)(x))/k=β}.我们证明了:当M是不可约矩阵时,对任意0≤α≤β≤+∞,集合E_(α,β)的Markov测度要么等于0要么等于1并且具有满的Hausdorff维数.