Inference and experimental design for percolation and random graph models.

Abstract

The problem of optimal arrangement of nodes of a random weighted graph is studied in this thesis. The nodes of graphs under study are fixed, but their edges are random and established according to the so called edge-probability function. This function is assumed to depend on the weights attributed to the pairs of graph nodes (or distances between them) and a statistical parameter. It is the purpose of experimentation to make inference on the statistical parameter and thus to extract as much information about it as possible. We also distinguish between two different experimentation scenarios: progressive and instructive designs. We adopt a utility-based Bayesian framework to tackle the optimal design problem for random graphs of this kind. Simulation based optimisation methods, mainly Monte Carlo and Markov Chain Monte Carlo, are used to obtain the solution. We study optimal design problem for the inference based on partial observations of random graphs by employing data augmentation technique. We prove that the infinitely growing or diminishing node configurations asymptotically represent the worst node arrangements. We also obtain the exact solution to the optimal design problem for proximity graphs (geometric graphs) and numerical solution for graphs with threshold edge-probability functions. We consider inference and optimal design problems for finite clusters from bond percolation on the integer lattice Zd and derive a range of both numerical and analytical results for these graphs. We introduce inner-outer plots by deleting some of the lattice nodes and show that the ‘mostly populated’ designs are not necessarily optimal in the case of incomplete observations under both progressive and instructive design scenarios. Finally, we formulate a problem of approximating finite point sets with lattice nodes and describe a solution to this problem.