Approximately Uniform Random Sampling in Sensor Networks

Recent work in sensor databases has focused extensively on distributed query problems, notably distributed computation of aggregates. Existing methods for computing aggregates broadcast queries to all sensors and use in-network aggregation of responses to minimize messaging costs. In this work, we focus on uniform random sampling across nodes, which can serve both as an alternative building block for aggregation and as an integral component of many other useful randomized algorithms. Prior to our work, the best existing proposals for uniform random sampling of sensors involve contacting all nodes in the network. We propose a practical method which is only approximately uniform, but contacts a number of sensors proportional to the diameter of the network instead of its size. The approximation achieved is tunably close to exact uniform sampling, and only relies on well-known existing primitives, namely geographic routing, distributed computation of Voronoi regions and von Neumann's rejection method. Ultimately, our sampling algorithm has the same worst-case asymptotic cost as routing a point-to-point message, and thus it is asymptotically optimal among request/reply-based sampling methods. We provide experimental results demonstrating the effectiveness of our algorithm on both synthetic and real sensor topologies.

Generating Good Degree Distributions for Sparse Parity Check Codes using Oracles

Fast forward error correction codes are becoming an important component in bulk content delivery. They fit in naturally with multicast scenarios as a way to deal with losses and are now seeing use in peer to peer networks as a basis for distributing load. In particular, new irregular sparse parity check codes have been developed with provable average linear time performance, a significant improvement over previous codes. In this paper, we present a new heuristic for generating codes with similar performance based on observing a server with an oracle for client state. This heuristic is easy to implement and provides further intuition into the need for an irregular heavy tailed distribution.

A mathematical theory of stochastic microlensing. II. Random images, shear, and the Kac-Rice formula

Continuing our development of a mathematical theory of stochastic microlensing, we study the random shear and expected number of random lensed images of different types. In particular, we characterize the first three leading terms in the asymptotic expression of the joint probability density function (pdf) of the random shear tensor due to point masses in the limit of an infinite number of stars. Up to this order, the pdf depends on the magnitude of the shear tensor, the optical depth, and the mean number of stars through a combination of radial position and the star's mass. As a consequence, the pdf's of the shear components are seen to converge, in the limit of an infinite number of stars, to shifted Cauchy distributions, which shows that the shear components have heavy tails in that limit. The asymptotic pdf of the shear magnitude in the limit of an infinite number of stars is also presented. All the results on the random microlensing shear are given for a general point in the lens plane. Extending to the general random distributions (not necessarily uniform) of the lenses, we employ the Kac-Rice formula and Morse theory to deduce general formulas for the expected total number of images and the expected number of saddle images. We further generalize these results by considering random sources defined on a countable compact covering of the light source plane. This is done to introduce the notion of global expected number of positive parity images due to a general lensing map. Applying the result to microlensing, we calculate the asymptotic global expected number of minimum images in the limit of an infinite number of stars, where the stars are uniformly distributed. This global expectation is bounded, while the global expected number of images and the global expected number of saddle images diverge as the order of the number of stars. © 2009 American Institute of Physics.

Telomere disruption results in non-random formation of de novo dicentric chromosomes involving acrocentric human chromosomes.

Genome rearrangement often produces chromosomes with two centromeres (dicentrics) that are inherently unstable because of bridge formation and breakage during cell division. However, mammalian dicentrics, and particularly those in humans, can be quite stable, usually because one centromere is functionally silenced. Molecular mechanisms of centromere inactivation are poorly understood since there are few systems to experimentally create dicentric human chromosomes. Here, we describe a human cell culture model that enriches for de novo dicentrics. We demonstrate that transient disruption of human telomere structure non-randomly produces dicentric fusions involving acrocentric chromosomes. The induced dicentrics vary in structure near fusion breakpoints and like naturally-occurring dicentrics, exhibit various inter-centromeric distances. Many functional dicentrics persist for months after formation. Even those with distantly spaced centromeres remain functionally dicentric for 20 cell generations. Other dicentrics within the population reflect centromere inactivation. In some cases, centromere inactivation occurs by an apparently epigenetic mechanism. In other dicentrics, the size of the alpha-satellite DNA array associated with CENP-A is reduced compared to the same array before dicentric formation. Extra-chromosomal fragments that contained CENP-A often appear in the same cells as dicentrics. Some of these fragments are derived from the same alpha-satellite DNA array as inactivated centromeres. Our results indicate that dicentric human chromosomes undergo alternative fates after formation. Many retain two active centromeres and are stable through multiple cell divisions. Others undergo centromere inactivation. This event occurs within a broad temporal window and can involve deletion of chromatin that marks the locus as a site for CENP-A maintenance/replenishment.

Gene selection using iterative feature elimination random forests for survival outcomes.

Although many feature selection methods for classification have been developed, there is a need to identify genes in high-dimensional data with censored survival outcomes. Traditional methods for gene selection in classification problems have several drawbacks. First, the majority of the gene selection approaches for classification are single-gene based. Second, many of the gene selection procedures are not embedded within the algorithm itself. The technique of random forests has been found to perform well in high-dimensional data settings with survival outcomes. It also has an embedded feature to identify variables of importance. Therefore, it is an ideal candidate for gene selection in high-dimensional data with survival outcomes. In this paper, we develop a novel method based on the random forests to identify a set of prognostic genes. We compare our method with several machine learning methods and various node split criteria using several real data sets. Our method performed well in both simulations and real data analysis.Additionally, we have shown the advantages of our approach over single-gene-based approaches. Our method incorporates multivariate correlations in microarray data for survival outcomes. The described method allows us to better utilize the information available from microarray data with survival outcomes.

Regularity of invariant densities for 1D systems with random switching

© 2015 IOP Publishing Ltd & London Mathematical Society.This is a detailed analysis of invariant measures for one-dimensional dynamical systems with random switching. In particular, we prove the smoothness of the invariant densities away from critical points and describe the asymptotics of the invariant densities at critical points.

Stochastic switching in infinite dimensions with applications to random parabolic PDE

© 2015 Society for Industrial and Applied Mathematics.We consider parabolic PDEs with randomly switching boundary conditions. In order to analyze these random PDEs, we consider more general stochastic hybrid systems and prove convergence to, and properties of, a stationary distribution. Applying these general results to the heat equation with randomly switching boundary conditions, we find explicit formulae for various statistics of the solution and obtain almost sure results about its regularity and structure. These results are of particular interest for biological applications as well as for their significant departure from behavior seen in PDEs forced by disparate Gaussian noise. Our general results also have applications to other types of stochastic hybrid systems, such as ODEs with randomly switching right-hand sides.

A new approach for objective identification of turns and steps in organism movement data relevant to random walk modelling

1. A first step in the analysis of complex movement data often involves discretisation of the path into a series of step-lengths and turns, for example in the analysis of specialised random walks, such as Lévy flights. However, the identification of turning points, and therefore step-lengths, in a tortuous path is dependent on ad-hoc parameter choices. Consequently, studies testing for movement patterns in these data, such as Lévy flights, have generated debate. However, studies focusing on one-dimensional (1D) data, as in the vertical displacements of marine pelagic predators, where turning points can be identified unambiguously have provided strong support for Lévy flight movement patterns. 2. Here, we investigate how step-length distributions in 3D movement patterns would be interpreted by tags recording in 1D (i.e. depth) and demonstrate the dimensional symmetry previously shown mathematically for Lévy-flight movements. We test the veracity of this symmetry by simulating several measurement errors common in empirical datasets and find Lévy patterns and exponents to be robust to low-quality movement data. 3. We then consider exponential and composite Brownian random walks and show that these also project into 1D with sufficient symmetry to be clearly identifiable as such. 4. By extending the symmetry paradigm, we propose a new methodology for step-length identification in 2D or 3D movement data. The methodology is successfully demonstrated in a re-analysis of wandering albatross Global Positioning System (GPS) location data previously analysed using a complex methodology to determine bird-landing locations as turning points in a Lévy walk. For this high-resolution GPS data, we show that there is strong evidence for albatross foraging patterns approximated by truncated Lévy flights spanning over 3·5 orders of magnitude. 5. Our simple methodology and freely available software can be used with any 2D or 3D movement data at any scale or resolution and are robust to common empirical measurement errors. The method should find wide applicability in the field of movement ecology spanning the study of motile cells to humans.

Are Fast Responses More Random? Testing the Effect of Response Time on Scale in an Online Choice Experiment

Scepticism over stated preference surveys conducted online revolves around the concerns over “professional respondents” who might rush through the questionnaire without sufficiently considering the information provided. To gain insight on the validity of this phenomenon and test the effect of response time on choice randomness, this study makes use of a recently conducted choice experiment survey on ecological and amenity effects of an offshore windfarm in the UK. The positive relationship between self-rated and inferred attribute attendance and response time is taken as evidence for a link between response time and cognitive effort. Subsequently, the generalised multinomial logit model is employed to test the effect of response time on scale, which indicates the weight of the deterministic relative to the error component in the random utility model. Results show that longer response time increases scale, i.e. decreases choice randomness. This positive scale effect of response time is further found to be non-linear and wear off at some point beyond which extreme response time decreases scale. While response time does not systematically affect welfare estimates, higher response time increases the precision of such estimates. These effects persist when self-reported choice certainty is controlled for. Implications of the results for online stated preference surveys and further research are discussed.

Hierarchical random walks in trace fossils and the origin of optimal search behavior

Efficient searching is crucial for timely location of food and other resources. Recent studies show diverse living animals employ a theoretically optimal scale-free random search for sparse resources known as a Lévy walk, but little is known of the origins and evolution of foraging behaviour and the search strategies of extinct organisms. Here we show using simulations of self-avoiding trace fossil trails that randomly introduced strophotaxis (U-turns) – initiated by obstructions such as ¬¬¬self-trail avoidance or innate cueing – leads to random looping patterns with clustering across increasing scales that is consistent with the presence of Lévy walks. This predicts optimal Lévy searches can emerge from simple behaviours observed in fossil trails. We then analysed fossilized trails of benthic marine organisms using a novel path analysis technique and find the first evidence of Lévy-like search strategies in extinct animals. Our results show that simple search behaviours of extinct animals in heterogeneous environments give rise to hierarchically nested Brownian walk clusters that converge to optimal Lévy patterns. Primary productivity collapse and large-scale food scarcity characterising mass extinctions evident in the fossil record may have triggered adaptation of optimal Lévy-like searches. The findings suggest Lévy-like behaviour has been employed by foragers since at least the Eocene but may have a more ancient origin, which could explain recent widespread observations of such patterns among modern taxa.

Quadratic Forms on Complex Random Matrices and Multiple-Antenna Systems

This research published in the foremost international journal in information theory and shows interplay between complex random matrix and multiantenna information theory. Dr T. Ratnarajah is leader in this area of research and his work has been contributed in the development of graduate curricula (course reader) in Massachusetts Institute of Technology (MIT), USA, By Professor Alan Edelman. The course name is "The Mathematics and Applications of Random Matrices", see http://web.mit.edu/18.338/www/projects.html