Search

The coalescent is a stochastic process representing ancestral lineages in a population undergoing neutral genetic drift. Originally defined for a well-mixed population, the coalescent has been adapted in various ways to accommodate spatial, age, and class structure, along with other features of real-world populations. To further extend the range of population structures to which coalescent theory applies, we formulate a coalescent process for a broad class of neutral drift models with arbitrary – but fixed – spatial, age, sex, and class structure, haploid or diploid genetics, and any fixed mating pattern. Here, the coalescent is represented as a random sequence of mappings C = C t t = 0 ∞ from a finite set G to itself. The set G represents the "sites" (in individuals, in particular locations and/or classes) at which these alleles can live. The state of the coalescent, C t : G → G , maps each site g ∈ G to the site containing g 's ancestor, t time-steps into the past. Using this representation, we define and analyze coalescence time, coalescence branch length, mutations prior to coalescence, and stationary probabilities of identity-by-descent and identity-by-state. For low mutation, we provide a recipe for computing identity-by-descent and identity-by-state probabilities via the coalescent. Applying our results to a diploid population with arbitrary sex ratio r , we find that measures of genetic dissimilarity, among any set of sites, are scaled by 4 r (1 − r) relative to the even sex ratio case. [ABSTRACT FROM AUTHOR]

We investigate properties of random mappings whose core is composed of derangements as opposed to permutations. Such mappings arise as the natural framework for studying the Screaming Toes game described, for example, by Peter Cameron. This mapping differs from the classical case primarily in the behaviour of the small components, and a number of explicit results are provided to illustrate these differences. [ABSTRACT FROM AUTHOR]

With the rapid growth of the number of images, many content-based image retrieval methods have been extensively used in our daily life. In general, image retrieval services are very expensive in terms of computing and storage. Therefore, outsourcing services to the cloud server is a good choice for image owners. However, privacy protection can become a big issue for image owners because the cloud server can only be semi-trusted. In this paper, we propose a novel image retrieval scheme. It is a ciphertext image retrieval method based on random mapping features with the bag-of-words model. After encrypting the image with Advanced Encryption Standard and block permutation, the cloud server generates random templates and then extracts the local features. All local features are clustered by k-means algorithm to form the visual word. The histogram of encrypted visual words is constructed in this way as the feature vector to represent each image. The similarity between images can be measured by the distance between feature vectors on the cloud server. Experiments and analysis prove the effect of the scheme.

Advances in network technology have enhanced the concern for network security issues. In order to address the problem that hopping graph are vulnerable to external attacks (e.g., the changing rules of fixed graphs are more easily grasped by attackers) and the challenge of achieving both interactivity and randomness in a network environment, this paper proposed a scheme for a dynamic graph based on chaos and cryptographic random mapping. The scheme allows hopping nodes to compute and obtain dynamically random and uncorrelated graph of other nodes independently of each other without additional interaction after the computational process of synchronous mirroring. We first iterate through the chaos algorithm to generate random seed parameters, which are used as input parameters for the encryption algorithm; secondly, we execute the encryption algorithm to generate a ciphertext of a specified length, which is converted into a fixed point number; and finally, the fixed point number is mapped to the network parameters corresponding to each node. The hopping nodes are independently updated with the same hopping map at each hopping period, and the configuration of their own network parameters is updated, so that the updated graph can effectively prevent external attacks. Finally, we have carried out simulation experiments and related tests on the proposed scheme and demonstrated that the performance requirements of the random graphs can be satisfied in both general and extreme cases.

To deal with the poor real - time performance and high data distribution requirements of the traditional interactive behavior anomaly detection methods, a mobile network interaction anomaly detection method based on Internet of things was studied. Based on the time series components, the high - dimensional data features of the Internet of things were detected. With the obtained subset of the interactive behavior data feature as the foundation and the positive vector data of the high - dimensional feature space as the verification core, the constant deviation function was established to obtain the minimum value of the function, and thus the detection threshold was set. According to the detection threshold, the parallel time series was used to establish the random mapping, and the Kmeans + + algorithm was used to cluster the interactive data to obtain the abnormal sets of multiple interactive data. The intersection operation was performed on all the abnormal sets to obtain the final anomaly detection object set. The simulation results show that the method can effectively improve the real - time detection of interactive behavior anomalies and the anomaly detection effect is satisfactory. [ABSTRACT FROM AUTHOR]

Aldous and Pitman (1994) studied asymptotic distributions as n → ∞, of various functional of a uniform random mapping of the set {1,..., n}, by constructing a mapping-walk and showing these random walks converge weakly to a reflecting Brownian bridge. Two different ways to encode a mapping as a walk lead to two different decompositions of the Brownian bridge, each defined by cutting the path of the bridge at an increasing sequence of recursively defined random times in the zero set of the bridge. The random mapping asymptotics entail some remarkable identities involving the random occupation measures of the bridge fragments defined by these decompositions. We derive various extensions of these identities for Brownian and Bessel bridges, and characterize the distributions of various path fragments involved, using the Lévy-ltô theory of Poisson processes of excursions for a self-similar Markov process whose zero set is the range of a stable subordinator of index α ∈ (0,1).

Aldous and Pitman (1994) studied asymptotic distributions as n → ∞, of various functional of a uniform random mapping of the set {1,..., n}, by constructing a mapping-walk and showing these random walks converge weakly to a reflecting Brownian bridge. Two different ways to encode a mapping as a walk lead to two different decompositions of the Brownian bridge, each defined by cutting the path of the bridge at an increasing sequence of recursively defined random times in the zero set of the bridge. The random mapping asymptotics entail some remarkable identities involving the random occupation measures of the bridge fragments defined by these decompositions. We derive various extensions of these identities for Brownian and Bessel bridges, and characterize the distributions of various path fragments involved, using the Lévy-ltô theory of Poisson processes of excursions for a self-similar Markov process whose zero set is the range of a stable subordinator of index α ∈ (0,1).

We study the asymptotics of the p-mapping model of random mappings on [n] as n gets large, under a large class of asymptotic regimes for the underlying distribution p. We encode these random mappings in random walks which are shown to converge to a functional of the exploration process of inhomogeneous random trees, this exploration process being derived (Aldous-Miermont-Pitman 2004) from a bridge with exchangeable increments. Our setting generalizes previous results by allowing a finite number of "attracting points" to emerge. © Springer-Verlag 2005.

The Joyal bijection between doubly-rooted trees and mappings can be lifted to a transformation on function space which takes tree-walks to mapping-walks. Applying known results on weak convergence of random tree walks to Brownian excursion, we give a conceptually simpler rederivation of the Aldous-Pitman (1994) result on convergence of uniform random mapping walks to reflecting Brownian bridge, and extend this result to random p-mappings. © 2004 Applied Probability Trust.

The Joyal bijection between doubly-rooted trees and mappings can be lifted to a transformation on function space which takes tree-walks to mapping-walks. Applying known results on weak convergence of random tree walks to Brownian excursion, we give a conceptually simpler rederivation of the Aldous-Pitman (1994) result on convergence of uniform random mapping walks to reflecting Brownian bridge, and extend this result to random p-mappings. © 2004 Applied Probability Trust.

Recurrent neural networks (RNNs) remain challenging, and there is still a lack of long-term memory or learning ability in sequential data classification and prediction. In this paper, we propose a flexible recurrent model, BIdirectional COnvolutional RaNdom RNNs (BICORN-RNNs), incorporating a series of sub-models: random projection, convolutional operation, and bidirectional transmission. These subcategories advance classification accuracy, which was limited by the gradient vanishing and the exploding problem. Experiments on public time series datasets demonstrate that our proposed method substantially outperforms a variety of existing models. Furthermore, the coordination of the accuracy and efficiency concerning a variety of factors, including SNR, length, data missing, and overlapping, is also discussed. [ABSTRACT FROM AUTHOR]

If is a polynomial of degree in , let be the number of cycles of length in the directed graph on with edges For random polynomials, the numbers have asymptotic behavior resembling that for the cycle lengths of random functions However random polynomials differ from random functions in important ways. For example, given the set of cyclic (periodic) points, it is not necessarily true that all permutations of those cyclic points are equally likely to occur as the restriction of . This, and the limitations of Lagrange interpolation, together complicate research on the ultimate period of under compositional iteration. We prove a lower bound for the average value of : if , but , then the expected value of is where the sum is over all polynomials of degree in . Similar results are proved for rational functions. [ABSTRACT FROM AUTHOR]

Critical overlap situations in the classical Hellman's cryptanalytic time memory trade-off method can be avoided, provided that during the precomputation phase, we generate perfect chains which are merge-free and loop-free chains. In this paper, we present asymptotic behavior of perfect chains in terms of time memory trade-off attacks. More precisely, we obtained expected values and variances for the coverage of perfect chains. We have also confirmed our theoretic outcomes with test results. [ABSTRACT FROM AUTHOR]

In this article, we present MaD0, an ultrafast nonlinear pseudorandom number generator (PRNG) for noncryptographic applications. MaD0 uses byte-oriented operations for state initialization and fast integer-oriented operations for state transition and pseudorandom number generation. Its state transition follows a pseudorandom mapping. MaD0 generates high-quality pseudorandom numbers and reaches a generation speed of half cycle per byte on an Intel Core i3 processor. It has a state space of 2,240 bits and an expected period length around 21120. It also shows other good properties, such as fast recovery from biased states and ease of use. [ABSTRACT FROM AUTHOR]

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of a small number of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two uniformly random spanning trees approximates the expansion of the graph to within a factor of O(log n). For the complete graph, we prove that the union of two uniformly random spanning trees is an expander with high probability. For the random graph Gn,p, for p = Ω(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is an expander. A closely related construction, which we call a selector, has similar properties. A random selector of a graph is obtained by starting with any spanning tree of the graph and adding a small number of random edges at each vertex. [ABSTRACT FROM AUTHOR]

In this paper we characterise the distributions of the number of predecessors and of the number of successors of a given set of vertices, A, in the random mapping model, Tn... (see Hansen and Jaworski (2008)), with exchangeable in-degree sequence (...1, ...22, . . ., ...n). We show that the exact formulae for these distributions and their expected values can be given in terms of the distributions of simple functions of the in-degree variables ...1, ...2, . . ., ...n. As an application of these results, we consider two special examples of Tn... which correspond to random mappings with preferential and anti-preferential attachment, and determine the exact distributions for the number of predecessors and the number of successors in these cases. We also characterise, for these two special examples, the asymptotic behaviour of the expected numbers of predecessors and successors and interpret these results in terms of the threshold behaviour of epidemic processes on random mapping graphs. The families of discrete distributions obtained in this paper are also of independent interest. [ABSTRACT FROM AUTHOR]

To solve stochastic problems with geometric uncertainties, one can transform the original problem in a domain with stochastic boundaries and interfaces to a problem defined in a deterministic domain with uncertainties in the material behavior. The latter problem is then discretized. There exist infinitely many random mappings that lead to identical results in the continuous domain but not in the discretized domain. In this paper, an a priori error indicator is proposed for electromagnetic problems with scalar and vector potential formulations. This leads to criteria for selecting random mappings that reduce the numerical error. In an illustrative numerical example, the proposed a priori error indicator is compared with an a posteriori estimator for both potential formulations. [ABSTRACT FROM AUTHOR]

The numerical solution of partial differential equations onto random domains can be done by using a mapping transforming this random domain into a deterministic domain. The issue is then to determine this one to one random mapping. In this paper, we present two methods—one based on the resolution of the Laplace equations, one based on a geometric transformation—to determine the random mapping. A stochastic magnetostatic example is treated to compare these methods. [ABSTRACT FROM PUBLISHER]

A method to solve stochastic partial differential equations on random domains consists in using a one-to-one random mapping function which transforms the random domain into a deterministic domain. With this method, the randomness is then borne by the constitutive relationship of the material. In this paper, this method is applied in electrokinetics in the case of scalar potential and vector potential formulations. An example is treated and the proposed method is compared to a nonintrusive method (NIM) based on the remeshing of the random domains. [ABSTRACT FROM AUTHOR]

Suppose that $$ \mathfrak{S} $$ n is the semigroup of mappings of the set of n elements into itself, A is a fixed subset of the set of natural numbers ℕ, and V n( A) is the set of mappings from $$ \mathfrak{S} $$ n whose contours are of sizes belonging to A. Mappings from V n( A) are usually called A-mappings. Consider a random mapping σ n, uniformly distributed on V n( A). Suppose that ν n is the number of components and λ n is the number of cyclic points of the random mapping σ n. In this paper, for a particular class of sets A, we obtain the asymptotics of the number of elements of the set V n( A) and prove limit theorems for the random variables ν n and λ n as n → ∞. [ABSTRACT FROM AUTHOR]

In this paper we investigate the 'local' properties of a random mapping model, TnD̂, which maps the set {l, 2,…,n} into itself. The random mapping TnD̂, which was introduced in a companion paper (Hansen and Jaworski (2008)), is constructed using a collection of exchangeable random variables D̂1,…D̂n which satisfy ∑i=ln D̂= n. In the random digraph, GnD̂, which represents the mapping TnD̂,, the in-degree sequence for the vertices is given by the variables D̂1,…D̂2…, D̂n, and, in some sense, GnD̂, can be viewed as an analogue of the general independent degree models from random graph theory. By local properties we mean the distributions of random mapping characteristics related to a given vertex υ of GnD̂,-for example, the numbers of predecessors and successors of υ in GnD̂,. We show that the distribution of several variables associated with the local structure of GnD̂, can be expressed in terms of expectations of simple functions of D̂1,…D̂2…, D̂n. We also consider two special examples of TnD̂ which correspond to random mappings with preferential and anti-preferential attachment, and determine, for these examples, exact and asymptotic distributions for the local structure variables considered in this paper. These distributions are also of independent interest. [ABSTRACT FROM AUTHOR]

We consider the class of all one-to-one mappings of an n-element set into itself, each of which has exactly N connected components. Letting n, N → ∞, we find that the asymptotic behavior of the mean and variance of the random variable is equal to the number of components of a given size in a mapping that is selected at random and is equiprobable among the elements of the mentioned class, and we prove the Poisson and local normal limit theorems for this random variable. Asymptotic estimates are found for the number of mappings with N components, among which there are exactly k components of a fixed size. [ABSTRACT FROM AUTHOR]

Random costs C( i, j) are assigned to the arcs of a complete directed graph on n labeled vertices. Given the cost matrix C n =( C( i, j)), let T* k = T* k ( C n ) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal to k. Since it is NP-hard to find T* k , we instead consider an efficient algorithm that finds a near-optimal spanning tree T . If the edge costs are independent, with a common exponential(I) distribution, then, as n → ∞, Upper and lower bounds for E( Cost( T* k )) are also obtained for k≥2. [ABSTRACT FROM AUTHOR]

Let X and Y be finite sets and φ: ( X,Y) → Y be a mapping. Consider a random mapping i → φ(xi,yi), where xi are arbitrarily chosen from the set X, whereas (yi) is a random sample from Y without replacement. A two-sided bound is derived for the probability of absence of collisions of this mapping. A case of mapping, defined as φ( x, y)=x + y modulo n, is considered in particular. The results may be used in the selection of identification codes. [ABSTRACT FROM AUTHOR]

Using additive functions defined on the combinatorial structure of all mappings of an N set into itself, we define paths in the space $$\mathbb{D}[0,1]$$ endowed with the Skorokhod topology. Taking a mapping with equal probability, we get a sequence of random processes. Necessary and sufficient conditions for the weak convergence of this sequence to a stochastic process with independent increments are established. It is shown that the class of such processes contains all possible limits, provided that, on the components of a mapping, the additive functions have values small in average. [ABSTRACT FROM AUTHOR]