On simulating the quantum and classical branching programs

The complexity classes defined on the basis of branching programs are considered. Some basic relations are established between the complexity classes defined by the probabilistic and quantum branching programs (measure-once, as well as measure-many), computing with bounded or unbounded error. To prove these relations, we developed a method of “linear simulation” of a quantum branching program and a method of “quantum simulation” of a probabilistic branching program.     

Numerical Solution for the Non-linear Dirichlet Problem of a Branching Process

We give a probabilistic numerical approach for the nonlinear Dirichlet problem associated with a branching process. Main tools are the probabilistic representation of the solution with the measure-valued branching process, as well as specific techniques for the numerical solution of linear partial differential equations, introduced and developed by Milstein and Tretyakov, and Monte Carlo methods.     

Nonlinear PDEs and measure-valued branching type processes

We deal with the probabilistic approach to a nonlinear operator Λ of the form , in connection with the works of M. Nagasawa, N. Ikeda, S. Watanabe, and M.L. Silverstein on the discrete branching processes. Instead of the Laplace operator we may consider the generator of a right (Markov) process, called base process, with a general (not necessarily locally compact) state space. It turns out that solutions of the nonlinear equation Λu=0 are produced by the harmonic functions with respect to the (linear) generator of a discrete branching type process. The consideration of the general state space allows to take as base process a measure-valued superprocess (in the sense of E.B. Dynkin). The probabilistic counterpart is a Markov process which is a combination between a continuous branching process (e.g., associated with a nonlinear operator of the form Δu−uα, 1<α?2) and a discrete branching type one, on a space of configurations of finite measures. Our approach uses probabilistic and analytic potential theoretical tools, like the potential kernel of a continuous additive functional and the subordination operators.     

Doubly stochastic Yule cascades (Part I): The explosion problem in the time-reversible case

Motivated by the probabilistic methods for nonlinear differential equations introduced by McKean (1975) for the Kolmogorov-Petrovski-Piskunov (KPP) equation, and by Le Jan and Sznitman (1997) for the incompressible Navier-Stokes equations (NSE), we identify a new class of stochastic cascade models, referred to as doubly stochastic Yule cascades. We establish non-explosion criteria under the assumption that the randomization of Yule intensities from generation to generation is by an ergodic time-reversible Markov process. In addition to the cascade models that arise in the analysis of certain deterministic nonlinear differential equations, this model includes the multiplicative branching random walks, the branching Markov processes, and the stochastic generalizations of the percolation and/or cell ageing models introduced by Aldous and Shields (1988) and independently by Athreya (1985).     

Branching diffusion representation of semi-linear elliptic PDEs and estimation using Monte Carlo method

We study semi-linear elliptic PDEs with polynomial non-linearity in bounded domains and provide a probabilistic representation of their solution using branching diffusion processes. When the non-linearity involves the unknown function but not its derivatives, we extend previous results in the literature by showing that our probabilistic representation provides a solution to the PDE without assuming its existence. In the general case, we derive a new representation of the solution by using marked branching diffusion processes and automatic differentiation formulas to account for the non-linear gradient term. We consider several examples and estimate their solution by using the Monte Carlo method.     

Nombre de branchement d’un pseudogroupe

Lyons has defined an average number of branches per vertex of an infinite locally finite rooted tree. This number has an important role in several probabilistic processes such as random walk and percolation. In this paper, we extend the notion of branching number to any measurable graphed pseudogroup of finite type acting on a probability space. We prove that such a pseudogroup is Liouvillian (i.e. almost every orbit does not admit non-constant bounded harmonic functions) if its branching number is equal to 1. In order to prove that this actually generalizes results of C. Series and V. Kaimanovich on equivalence relations with polynomial and subexponential growth, we describe an example of minimal lamination whose holonomy pseudogroup has exponential growth and branching number equal to 1.     

Nombre de branchement d’un pseudogroupe

Lyons has defined an average number of branches per vertex of an infinite locally finite rooted tree. This number has an important role in several probabilistic processes such as random walk and percolation. In this paper, we extend the notion of branching number to any measurable graphed pseudogroup of finite type acting on a probability space. We prove that such a pseudogroup is Liouvillian (i.e. almost every orbit does not admit non-constant bounded harmonic functions) if its branching number is equal to 1. In order to prove that this actually generalizes results of C. Series and V. Kaimanovich on equivalence relations with polynomial and subexponential growth, we describe an example of minimal lamination whose holonomy pseudogroup has exponential growth and branching number equal to 1.     

Convergence of a stochastic particle approximation for fractional scalar conservation laws

We are interested in a probabilistic approximation of the solution to scalar conservation laws with fractional diffusion and nonlinear drift. The probabilistic interpretation of this equation is based on a stochastic differential equation driven by an α-stable Lévy process and involving a nonlinear drift. The approximation is constructed using a system of particles following a time-discretized version of this stochastic differential equation, with nonlinearity replaced by interaction. We prove convergence of the particle approximation to the solution of the conservation law as the number of particles tends to infinity whereas the discretization step tends to 0 in some precise asymptotics.     

Forward-backward stochastic differential equation with subdifferential operator and associated variational inequality

We study the existence and uniqueness of the solution to a forward-backward stochastic differential equation with subdifferential operator in the backward equation. This kind of equations includes, as a particular case, multi-dimensional forward-backward stochastic differential equation where the backward equation is reflected on the boundary of a closed convex(time-independent) domain. Moreover, we give a probabilistic interpretation for the viscosity solution of a kind of quasilinear variational inequalities.     

Some generalized methods of optimal scaling and their asymptotic theories: The case of multiple responses-multiple factors

Seven generalized criteria are proposed with the corresponding formulations for optimal scaling of multiple responses. Then, on the basis of a natural probabilistic model, the asymptotic theories are derived concerning the test statistics on factor-response relationships as well as the distributions of sample criteria (eigenvalues of the determinantal equation) and optimal scores (eigenvectors) by means of socalled δ-method. A numerical example is provided for illustrations.     

Stochastic equations for two-type continuous-state branching processes with immigration and competition

A class of two-type continuous-state branching processes with immigration and competition is constructed as the solution of a jump-type stochastic integral equation system. We first show that the stochastic equation system has a pathwise unique non-negative strong solution and then prove the comparison property of the solution.     

HYERS-ULAM-RASSIAS STABILITY OF FUNCTIONAL EQUATIONS IN MENGER PROBABILISTIC NORMED SPACES

We introduce the approximately quadratic functional equation in Menger probabilistic normed spaces. More precisely, we show under some suitable conditions that an approximately quadratic functional equation can be approximated by a quadratic function in above mentioned spaces. Also we consider the stability problem for approximately pexiderized functional equation in Menger probabilistic normed spaces.     

Some problems on super-diffusions and one class of nonlinear differential equations

The historical superprocesses are considered on bounded regular domains with a complete branching form, as a probabilistic argument, the limit property of superprocesses is studied when the domains enlarge to the whole space. As an important application of superprocess, the representation of solutions of involved differential equations is used in term of historical superprocesses. The differential equations including the existence of nonnegative solution, the closeness of solutions and probabilistic representations to the maximal and minimal solutions are discussed, which helps develop the well-known results on nonlinear differential equations. Project supported by the National Natural Science Foundation of China (Grant No. 19631060) and the Postdoctoral Foundation of China.     

Small solutions of nonlinear differential equations near branching points

We construct parametric families of small branching solutions to nonlinear differential equations of the nth order near branching points. We use methods of the analytical theory of branching solutions of nonlinear equations and the theory of differential equations with a regular singular point. We illustrate the general existence theorems with an example of a nonlinear differential equation in a certain magnetic insulation problem.     

Branching on general disjunctions

This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming where branching is performed on general disjunctions rather than on variables. We select promising branching disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining the mixed integer Gomory cuts at an optimal basis of the linear programming relaxation. The procedure is tested on instances from the literature. Experiments show that, for a majority of the instances, the enumeration tree obtained by branching on these general disjunctions has a smaller size than the tree obtained by branching on variables, even when variable branching is performed using full strong branching.     

Continuous-State Branching Processes in Lévy Random Environments

A general continuous-state branching processes in random environment (CBRE-process) is defined as the strong solution of a stochastic integral equation. The environment is determined by a Lévy process with no jump less than \(-1\). We give characterizations of the quenched and annealed transition semigroups of the process in terms of a backward stochastic integral equation driven by another Lévy process determined by the environment. The process hits zero with strictly positive probability if and only if its branching mechanism satisfies Grey’s condition. In that case, a characterization of the extinction probability is given using a random differential equation with blowup terminal condition. The strong Feller property of the CBRE-process is established by a coupling method. We also prove a necessary and sufficient condition for the ergodicity of the subcritical CBRE-process with immigration.     

Solution of a stochastic Darcy equation by polynomial chaos expansion

This paper deals with solving a boundary value problem for the Darcy equation with a random hydraulic conductivity field.We use an approach based on polynomial chaos expansion in a probability space of input data.We use a probabilistic collocation method to calculate the coefficients of the polynomial chaos expansion. The computational complexity of this algorithm is determined by the order of the polynomial chaos expansion and the number of terms in the Karhunen–Loève expansion. We calculate various Eulerian and Lagrangian statistical characteristics of the flow by the conventional Monte Carlo and probabilistic collocation methods. Our calculations show a significant advantage of the probabilistic collocation method over the directMonte Carlo algorithm.     

On the uniqueness of possibilistic measure of uncertainty and information

It is demonstrated, through a series of theorems, that the U-uncertainty (introduced by Higashi and Klir in 1982) is the only possibilistic measure of uncertainty and information that satisfies possibilistic counterparts of axioms of the well established Shannon and hartley measures of uncertainty and information. Two complementary forms of the possibilistic counterparts of the probabilistic branching (or grouping) axiom, which is usually used in proofs of the uniqueness of the Shannon measure, are introduced in this paper for the first time. A one-to-one correspondence between possibility distributions and basic probabilistic assignments (introduced by Shafer in his mathematical theory of evidence) is instrumental in most proofs in this paper. The uniqueness proof is based on possibilistic formulations of axioms of symmetry, expansibility, additivity, branching, monotonicity, and normalization.     

Solution of Volterra operator-integral equations in the nonregular case by the successive approximation method

The branches of solutions of a nonlinear integral equation of Volterra type in a Banach space are constructed by the successive approximation method. We consider the case in which a solution may have an algebraic branching point. We reduce the equation to a system regular in a neighborhood of the branching point. Continuous and generalized solutions are considered. General existence theorems are used to study an initial-boundary value problem with degeneration in the leading part.     

Branching of solutions for the problem of mean-square approximation of a real finite function of two variables by the modulus of double Fourier transformation

We investigate the branching of solutions of a Hammerstein-type nonlinear two-dimensional integral equation that arises in the problems of mean-square approximation of a real finite nonnegative function of two variables by the modulus of double Fourier integral, depending on two parameters [Mat. Metody Fiz.-Mekh. Polya, 51, No. 1, 53–64; No. 4, 80–85 (2008)]. We have derived analytical expressions for eigenfunctions of the corresponding linear homogeneous integral equation, necessary for the construction of branched-off solutions, and obtained systems of transcendental equations for finding the points of their branching. We also present, in the first approximation, the analytical representations of complex solutions branched-off from the real solution for the two-dimensional case of branching.