New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

Exponential stability in mean square of neutral stochastic differential functional equations

The aim of this paper is to investigate the exponential stability in mean square for a neutral stochastic differential functional equation of the form d[x(t) − G(x_t)] = [f(t,x(t)) + g(t, x_t)]dt + σ(t, x_t)dw(t), where x_t = {x(t + s): − τ s 0}, with τ > 0, is the past history of the solution. Several interesting examples are a given for illustration.     

Filtering of some nonlinear diffusions satisfying the general Bene condition

Under some regularity assumptions and the following generalization of the well-known Bene condition [1]:

Full-size image

, where F(t,z) = g⁻²(t)∫f(t,z)dz, F_t, F_z, F_zz, are partial derivatives of F, we obtain explicit formulas for the unnormalized conditional density q_t(z, x) α Px_t ε dz| y_s, 0 st, where diffusion x_t on R¹ solves x₀ = x, dx_t = [β(t) + α(t)x_t + f(t, x_t] dt + g(t) dw₁, and observation y_t = ∫_o^th(s)x_s ds + ∫_o^t(s) dw_2t, with w = (w₁, w₂) a two-dimensional Wiener process.     

On the non-existence of stationary diffusions which satisfy the Bene condition

The one-dimensional diffusion x_t satisfying dx_t = f(x_t)dt + dw_t, where w_t is a standard Brownian motion and f(x) satisfies the Bene condition f′(x) + f²(x) = ax² + bx + c for all real x, is considered. It is shown that this diffusion does not admit a stationary probability measure except for the linear case f(x) = αx + β, α < 0.     

Maximum flow and critical cutset as descriptors of multi-state systems with randomly capacitated components

Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b₁(τ), …, B_n(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation.     

Stochastic stabilisation of functional differential equations

In this paper we investigate the problem of stochastic stabilisation for a general nonlinear functional differential equation. Given an unstable functional differential equation dx(t)/dt=f(t,x_t), we stochastically perturb it into a stochastic functional differential equation , where Σ is a matrix and B(t) a Brownian motion while X_t={X(t+θ):-τθ0}. Under the condition that f satisfies the local Lipschitz condition and obeys the one-side linear bound, we show that if the time lag τ is sufficiently small, there are many matrices Σ for which the stochastic functional differential equation is almost surely exponentially stable while the corresponding functional differential equation dx(t)/dt=f(t,x_t) may be unstable.     

A note on two-sided stochastic control problems

We consider a class of two-sided stochastic control problems. For each continuous process π_t = π_t⁺ − π_t⁻ with bounded variation, the state process (x_t) is defined by x_t = B_t + f₀^t I(x_s - a)^d_πs+ − f₀^t I(x_s a)^dπ_s−, where a is a positive constant and (B_t) is a standard Brownian motion. We show the existence of an optimal policy so as to minimize the cost function J(π) = E [f₀^∞ e^−αsX_s² ds], with discount rate α > 0, associated with π.     

Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ² for any simple graph with maximum degree Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.     

Stochastic stabilization and destabilization

It is shown in this paper that any nonlinear systems in ^d can be stabilized by Brownian motion provided |ƒ(x,t)| ≤ K|x| for some K > 0. On the other hand, this system can also be destabilized by Brownian motion if the dimension d ≥ 2. Similar results are also obtained for any given stochastic differential equation dx(t) = ƒ(x(t), t) + g(x(t), t) dW(t).     

Existence of triple positive solutions of two-point right focal boundary value problems on time scales

We consider the following boundary value problem, (−1)ⁿ⁻¹y^Δn(t)=(−1)^p+1F(t,y(σⁿ⁻¹(t))),t[a,b]∩T, y^Δn(a)=0,0≤i≤p−1, y^Δn(σ(b))=0,p≤i≤n−1,where n ≥ 2, 1 ≤ p ≤ n - 1 is fixed and T is a time scale. By applying fixed-point theorems for operators on a cone, existence criteria are developed for triple positive solutions of the boundary value problem. We also include examples to illustrate the usefulness of the results obtained.     

Stochastic suppression and stabilization of delay differential systems

In this paper, we investigate stochastic suppression and stabilization for nonlinear delay differential system ${\dot{x}}(t)=f(x(t),x(t-\delta(t)),t)In this paper, we investigate stochastic suppression and stabilization for nonlinear delay differential system ${\dot{x}}(t)=f(x(t),x(t-\delta(t)),t)$, where δ(t) is the variable delay and f satisfies the one‐sided polynomial growth condition. Since f may defy the linear growth condition or the one‐sided linear growth condition, this system may explode in a finite time. To stabilize this system by Brownian noises, we stochastically perturb this system into the nonlinear stochastic differential system dx(t)=f(x(t), x(t?δ(t)), t)dt+qx(t)dw₁(t)+σ|x(t)|^βx(t)dw₂(t) by introducing two independent Brownian motions w₁(t) and w₂(t). This paper shows that the Brownian motion w₂(t) may suppress the potential explosion of the solution of this stochastic system for appropriate choice of β under the condition σ≠0. Moreover, for sufficiently large q, the Brownian motion w₁(t) may exponentially stabilize this system. Copyright © 2010 John Wiley & Sons, Ltd.     

On input-output linearization of discrete-time nonlinear systems

We consider a nonlinear discrete-time system of the form Σ: x(t+1)=f(x(t), u(t)), y(t) =h(x(t)), where x ε R^N, u ε R^m, y ε R^q and f and h are analytic. Necessary and sufficient conditions for local input-output linearizability are given. We show that these conditions are also sufficient for a formal solution to the global input-output linearization problem. Finally, we show that zeros at infinity of ε can be obtained by the structure algorithm for locally input-output linearizable systems.     

The μ-basis of a planar rational curve—properties and computation

A moving line L(x,y;t)=0 is a family of lines with one parameter t in a plane. A moving line L(x,y;t)=0 is said to follow a rational curve P(t) if the point P(t₀) is on the line L(x,y;t₀)=0 for any parameter value t₀. A μ-basis of a rational curve P(t) is a pair of lowest degree moving lines that constitute a basis of the module formed by all the moving lines following P(t), which is the syzygy module of P(t). The study of moving lines, especially the μ-basis, has recently led to an efficient method, called the moving line method, for computing the implicit equation of a rational curve [3 and 6]. In this paper, we present properties and equivalent definitions of a μ-basis of a planar rational curve. Several of these properties and definitions are new, and they help to clarify an earlier definition of the μ-basis [3]. Furthermore, based on some of these newly established properties, an efficient algorithm is presented to compute a μ-basis of a planar rational curve. This algorithm applies vector elimination to the moving line module of P(t), and has O(n²) time complexity, where n is the degree of P(t). We show that the new algorithm is more efficient than the fastest previous algorithm [7].     

On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction

Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ₊ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination. This research was supported in part by NSF grant IIS-0118635 and by DIMACS, the NSF Center for Discrete Mathematics & Theoretical Computer Science. Preprints DTR-2005-04 and DTR-2006-13 are available at and . Our co-author Leonid Khachiyan passed away with tragic suddenness on April 29th, 2005.     

A different class of homing problems

The problem of minimizing the expected time spent by a one-dimensional controlled diffusion process x(t) in the interval [−d,d], while taking the quadratic control costs into account, is considered. Both the infinitesimal mean and variance of the controlled process x(t) depend on the control variable u(t). The optimization problem reduces to a purely probabilistic problem.     

Inapproximability of the Tutte polynomial

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P.     

Computational-Complexity of Arithmetical Sentences

Arithmetical sentences are the sentences containing usual logical symbols and arithmetical symbols +, ·, and constants of Z. An arithmetical sentence φ is called an sentence if and only if φ is logically equivalent to a sentence of the form x yψ(x, y) where ψ(x, y) is a quantifier free formula. It is shown that the decision problems of determining sentences true in N or Z, respectively, are co-NP-complete, whereas the decision problem of determining sentences true in Q is in P. Consequently, the decision problems of determining sentences true in N or Z, respectively, are NP-complete. Also, the decision problem of determining sentences true in Q is in P.     

Approximation by Bézier type of Meyer–König and Zeller operators

In this paper, we give direct, inverse and equivalence approximation theorems for the Bézier type of Meyer–König and Zeller operator with unified Ditzian–Totik modulus ω_φ^λ(f,t) (0≤λ≤1).     

On the Attainable Order of Collocation Methods for the Neutral Functional-Differential Equations with Proportional Delays

In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫₀ ^t by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE): and the delay Volterra integro-differential equation (DVIDE) : with proportional delays p _i t and q _i t, 0<p _i ,q _i ≤1 and complex numbers a,b _i and c _i . We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u _it (t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M _m (t) of v(th) or M^ _m (t) of u _it (th), t∈[0,1] such that the rational approximant v(h) or u _it (h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h ^{2 m +1}). If they exist, then we actually give the conditions of M _m (t) and M^ _m (t), respectively. Received September 17, 1998; revised September 30, 1999     

Diagonal polynomials and diagonal orders on multidimensional lattices

HereR andN denote the real numbers and the nonnegative integers, respectively. Alsos(x)=x ₁+···+x _n whenx=(x ₁, …,x _n) inR ⁿ. A mapf:R ⁿ →R is call adiagonal function of dimensionn iff|N ⁿ is a bijection ontoN and, for allx, y inN ⁿ, f(x)<f(y) whens(x)<s(y). Morales and Lew [6] constructed 2 ⁿ⁻² inequivalent diagonal polynomial functions of dimensionn for eachn>1. Here we use new combinatorial ideas to show that numberd _n of such functions is much greater than 2 ⁿ⁻² forn>3. These combinatorial ideas also give an inductive procedure to constructd _n+1 diagonal orderings of {1, …,n}.