Probabilistic Recursion Theory and Implicit Computational Complexity

In this thesis we provide a characterization of probabilistic computation in itself, from a recursion-theoretical perspective, without reducing it to deterministic computation. More specifically, we show that probabilistic computable functions, i.e., those functions which are computed by Probabilistic Turing Machines (PTM), can be characterized by a natural generalization of Kleene's partial recursive functions which includes, among initial functions, one that returns identity or successor with probability 1/2. We then prove the equi-expressivity of the obtained algebra and the class of functions computed by PTMs. In the the second part of the thesis we investigate the relations existing between our recursion-theoretical framework and sub-recursive classes, in the spirit of Implicit Computational Complexity. More precisely, endowing predicative recurrence with a random base function is proved to lead to a characterization of polynomial-time computable probabilistic functions.

Probabilistic approaches in civil engineering: generation of random fields and structural identification with genetic algorithms

The inherent stochastic character of most of the physical quantities involved in engineering models has led to an always increasing interest for probabilistic analysis. Many approaches to stochastic analysis have been proposed. However, it is widely acknowledged that the only universal method available to solve accurately any kind of stochastic mechanics problem is Monte Carlo Simulation. One of the key parts in the implementation of this technique is the accurate and efficient generation of samples of the random processes and fields involved in the problem at hand. In the present thesis an original method for the simulation of homogeneous, multi-dimensional, multi-variate, non-Gaussian random fields is proposed. The algorithm has proved to be very accurate in matching both the target spectrum and the marginal probability. The computational efficiency and robustness are very good too, even when dealing with strongly non-Gaussian distributions. What is more, the resulting samples posses all the relevant, welldefined and desired properties of “translation fields”, including crossing rates and distributions of extremes. The topic of the second part of the thesis lies in the field of non-destructive parametric structural identification. Its objective is to evaluate the mechanical characteristics of constituent bars in existing truss structures, using static loads and strain measurements. In the cases of missing data and of damages that interest only a small portion of the bar, Genetic Algorithm have proved to be an effective tool to solve the problem.

Probabilistic tomography of atmospheric parameters from GNSS data

The objective of the work is the evaluation of the potential capabilities of navigation satellite signals to retrieve basic atmospheric parameters. A capillary study have been performed on the assumptions more or less explicitly contained in the common processing steps of navigation signals. A probabilistic procedure has been designed for measuring vertical discretised profiles of pressure, temperature and water vapour and their associated errors. Numerical experiments on a synthetic dataset have been performed with the main objective of quantifying the information that could be gained from such approach, using entropy and relative entropy as testing parameters. A simulator of phase delay and bending of a GNSS signal travelling across the atmosphere has been developed to this aim.

Implicit computational complexity and probabilistic classes

The thesis applies the ICC tecniques to the probabilistic polinomial complexity classes in order to get an implicit characterization of them. The main contribution lays on the implicit characterization of PP (which stands for Probabilistic Polynomial Time) class, showing a syntactical characterisation of PP and a static complexity analyser able to recognise if an imperative program computes in Probabilistic Polynomial Time. The thesis is divided in two parts. The first part focuses on solving the problem by creating a prototype of functional language (a probabilistic variation of lambda calculus with bounded recursion) that is sound and complete respect to Probabilistic Prolynomial Time. The second part, instead, reverses the problem and develops a feasible way to verify if a program, written with a prototype of imperative programming language, is running in Probabilistic polynomial time or not. This thesis would characterise itself as one of the first step for Implicit Computational Complexity over probabilistic classes. There are still open hard problem to investigate and try to solve. There are a lot of theoretical aspects strongly connected with these topics and I expect that in the future there will be wide attention to ICC and probabilistic classes.

On the Wick product and Wong-Zakai approximations.

This thesis is a compilation of 6 papers that the author has written together with Alberto Lanconelli (chapters 3, 5 and 8) and Hyun-Jung Kim (ch 7). The logic thread that link all these chapters together is the interest to analyze and approximate the solutions of certain stochastic differential equations using the so called Wick product as the basic tool. In the first chapter we present arguably the most important achievement of this thesis; namely the generalization to multiple dimensions of a Wick-Wong-Zakai approximation theorem proposed by Hu and Oksendal. By exploiting the relationship between the Wick product and the Malliavin derivative we propose an original reduction method which allows us to approximate semi-linear systems of stochastic differential equations of the Itô type. Furthermore in chapter 4 we present a non-trivial extension of the aforementioned results to the case in which the system of stochastic differential equations are driven by a multi-dimensional fraction Brownian motion with Hurst parameter bigger than 1/2. In chapter 5 we employ our approach and present a “short time” approximation for the solution of the Zakai equation from non-linear filtering theory and provide an estimation of the speed of convergence. In chapters 6 and 7 we study some properties of the unique mild solution for the Stochastic Heat Equation driven by spatial white noise of the Wick-Skorohod type. In particular by means of our reduction method we obtain an alternative derivation of the Feynman-Kac representation for the solution, we find its optimal Hölder regularity in time and space and present a Feynman-Kac-type closed form for its spatial derivative. Chapter 8 treats a somewhat different topic; in particular we investigate some probabilistic aspects of the unique global strong solution of a two dimensional system of semi-linear stochastic differential equations describing a predator-prey model perturbed by Gaussian noise.