Hitting time and time change

This paper determines first‐passage time distributions with a twofold emphasis on the dynamics of the state variables and interest rate uncertainty. Underlyings follow two‐dimensional geometric Brownian motions, Ornstein–Uhlenbeck processes or Poisson jump‐diffusion processes, and boundaries are either fixed or indexed on risk‐free bonds. Forward‐neutral changes of numeraire enable one to derive generic valuation expressions, while changing time allows one to determine closed‐form solutions for geometric Brownian motions and moving barriers. In turn, the latter formulas are used to reduce the variance of Monte Carlo simulations in the case of jump‐diffusion processes, by means of the control variate method.     

A time minimising transportation problem with quality dependent time

The usual assumption made in time minimising transportation problem is that the time for transporting a positive amount in a route is independent of the actual amount transported in that route. In this paper we make a more general and natural assumption that the time depends on the actual amount transported. We assume that the time function for each route is an increasing piecewise constant function. Four algorithms - (1) a threshold algorithm, (2) an upper bounding technique, (3) a primal dual approach, and (4) a branch and bound algorithm - are presented to solve the given problem. A method is also given to compute the minimum bottle-neck shipment corresponding to the optimal time. A numerical example is solved illustrating the algorithms presented in this paper.     

Parallelization in time through tensor-product space–time solvers

In this Note, we extend the fast tensor-product algorithm for the simulation of time-dependent partial differential equations. We use the natural tensorization of the space–time domain to propose, after discretization, a set of independent problems, each one with the complexity of a single steady problem. This allows for an efficient parallel implementation that is already interesting on small architectures, but that can also be combined with standard domain-decomposition-based algorithms providing a further direction of parallelism on large computer platforms. Preliminary numerical simulations are presented for a one-dimensional unsteady heat equation. To cite this article: Y. Maday, E.M. Rønquist, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Local time and first return time for periodic semi-flows

We study Z^d-periodic semi-flows, which are versions in continuous time of Z^d-extensions of dynamical systems. These systems are defined by an underlying dynamical system, a step time (the time to wait before the system makes a move), and a step function (the displacement in Z^d at each step). We are interested in two statistics related to these semi-flows: the local time, i.e., the time spent in some subset, and the first return time to the origin. We get some partial results under spectral conditions on the transfer operator of the underlying dynamical system. If the underlying dynamics is Gibbs–Markov, and under additional constraints on the step time and step function, we get distributional asymptotics for the local time, and an equivalent of the tail of the first return time.     

Compile time preparations for run time scheduling in monitors

High level programming language constructs are proposed for scheduling of concurrent operations on a shared variable. Proof rules are given that can be used to check if an adequate scheduling can be prepared from the program text. The basis for the constructs is the condition that must be fulfilled before an operation on a shared variable is performed (the precondition of the operation) and what can be proved to hold when an operation terminates (the postassertion of the operation).     

Dynamical networks: Continuous time and general discrete time models

Dynamical networks are characterized by 1) their topology (structure of the graph of interactions among the elements of a network); 2) the interactions between the elements of the network; 3) the intrinsic (local) dynamics of the elements of the network. A general approach to studying the commulative effect of all these three factors on the evolution of networks of a very general type has been developed in [1]. Besides, in this paper there were obtained sufficient conditions for a global stability (generalized strong synchronization) of networks with an arbitrary topology and the dynamics which is a composition (action of one after another) of a local dynamics of the elements of a network and of the interactions between these elements. Here we extend the results of [1] on global stability (generalized strong synchronization) to the case of a general dynamics in discrete time dynamical networks and to general dynamical networks with continuous time.     

Minimum time problem for distributed hyperbolic systems with time lags

In this paper the time-optimal control problem for distributedhyperbolic systems in which constant lags appear both in thestate equations and in the boundary conditions is considered.The particular properties of the optimal control are discussed.     

Lead time management

In intermittent production systems, job shops, manufacturing lead times are often long and variable, yet only about 10% is due to the actual processing time. This is a major difficulty in planning production. Two alternative approaches exist for determining planning values for manufacturing lead times to use in production planning and control systems. The first is to treat them as independent uncontrollable variables. It is then a forecasting problem with the emphasis on minimising the impact of the forecasting errors. The second approach puts the emphasis on control and attempts to manage the average lead times to match pre-determined norms. This article reviews and compares these two approaches. It concludes that the second is the most appropriate but that it requires a close cooperation between the production and marketing functions of the firm. This is best achieved by regarding the firm as a hierarchical chain of backlogs connected by input/output relations.     

Reverse time diffusions

The paper considers a diffusion evolving in $\text{R}$ⁿ. The stochastic differential equations giving the same process, but with the time parameter evolving in the negative direction, are obtained under a certain integrability hypothesis when the diffusion has a density function on a time varying submanifold of $\text{R}$ⁿ.     

On time graphs

For n points on the real line, joining each pair of points such that their difference is less than a certain positive constant, we have a time graph. In this paper we characterize time graphs and enumerate them.     

Multiple cover time

Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distribution. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the following conjecture: that the blanket time of a graph never exceeds the cover time by more than a constant factor. In other words, at the cost of a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case includes almost all graphs, as well as most “natural” graphs: the hypercube, k-dimensional lattices for k ≥ 2, balanced k-ary trees, and expanders. We further prove the conjecture for perhaps the most natural graphs not falling in the above case: paths and cycles. Finally, we prove the conjecture in the case of independent stochastic processes. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 403–411 (1996)     

Real time computation

We introduce a concept of real-time computation by a Turing machine. The relative strengths of one-tape versus two-tape machines is established by a new method of proofs of impossibility of actual computations. This research was supported in part by National Science Foundation grant GP-228 to Harvard University. This paper was written while the author was visiting at the Computation Laboratory of Harvard University during the summer of 1963.     

Artificial time integration

Many recent algorithmic approaches involve the construction of a differential equation model for computational purposes, typically by introducing an artificial time variable. The actual computational model involves a discretization of the now time-dependent differential system, usually employing forward Euler. The resulting dynamics of such an algorithm is then a discrete dynamics, and it is expected to be “close enough” to the dynamics of the continuous system (which is typically easier to analyze) provided that small – hence many – time steps, or iterations, are taken. Indeed, recent papers in inverse problems and image processing routinely report results requiring thousands of iterations to converge. This makes one wonder if and how the computational modeling process can be improved to better reflect the actual properties sought. In this article we elaborate on several problem instances that illustrate the above observations. Algorithms may often lend themselves to a dual interpretation, in terms of a simply discretized differential equation with artificial time and in terms of a simple optimization algorithm; such a dual interpretation can be advantageous. We show how a broader computational modeling approach may possibly lead to algorithms with improved efficiency. AMS subject classification (2000)  65L05, 65M32, 65N21, 65N22, 65D18     

Choiceless polynomial time

Turing machines define polynomial time (PTime) on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time (without presuming the presence of a linear order)? Earlier, one of us conjectured a negative answer. The problem motivated a quest for stronger and stronger PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines (formerly called evolving algebras). The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime.     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

Optimal selling time in stock market over a finite time horizon

In this paper, we examine the best time to sell a stock at a price being as close as possible to its highest price over a finite time horizon [0, T ], where the stock price is modelled by a geometric Brownian motion and the ’closeness’ is measured by the relative error of the stock price to its highest price over [0, T ]. More precisely, we want to optimize the expression: where (V t ) t≥0 is a geometric Brownian motion with constant drift α and constant volatility σ > 0, M t = max Vs is the running maximum of the stock price, and the supremum is taken over all possible stopping times 0 ≤τ≤ T adapted to the natural filtration (F t ) t≥0 of the stock price. The above problem has been considered by Shiryaev, Xu and Zhou (2008) and Du Toit and Peskir (2009). In this paper we provide an independent proof that when α = 1 2 σ 2 , a selling strategy is optimal if and only if it sells the stock either at the terminal time T or at the moment when the stock price hits its maximum price so far. Besides, when α > 1 2 σ 2 , selling the stock at the terminal time T is the unique optimal selling strategy. Our approach to the problem is purely probabilistic and has been inspired by relating the notion of dominant stopping ρτ of a stopping time τ to the optimal stopping strategy arisen in the classical "Secretary Problem".     

Time-dependent analysis of virtual waiting time behaviour in discrete time queues

Discrete time queueing models have been shown previously to be of practical use for modelling the approximate time-dependent behaviour of queue length in systems of the form M(t)/G/c. In this paper we extend these models to include the time-dependent behaviour of virtual waiting time.     

Lead time and response time in a pull production control system

In the late 80s, most manufacturers have shifted their manufacturing strategies from cost and quality to speed. This paper focuses on two performance measures of speed: manufacturing lead time and response time. Manufacturing lead time is the sum of the processing time to convert raw material to finished goods and the waiting time at the buffers. Response time is the time between the customer places an order and the customer receives the order. In this paper we develop a queueing model of a pull-based production control system for a single-stage facility. The intent of the model is two-fold. First, we highlight the trade-off between manufacturing lead time and response time. Second, we develop an optimization model to determine an optimal control system that guarantees certain delivery performance (in terms of response time).