Statistical maps and generalized random walks

We continue our study of statistical maps (equivalently, fuzzy random variables in the sense of Gudder and Bugajski). In the realm of fuzzy probability theory, statistical maps describe the transportation of probability measures on one measurable space into probability measures on another measurable space. We show that for discrete probability spaces each statistical map can be represented via a special matrix the rows of which are probability functions related to conditional probabilities and the columns are related to fuzzy n-partitions of the domain. Discrete statistical maps sending a probability measure p to a probability measure q can be represented via conditional distributions and correspond to joint probabilities on the product. The composition of statistical maps provide a tool to describe and to study generalized random walks and Markov chains.     

Reading dependencies from covariance graphs

The covariance graph (aka bi-directed graph) of a probability distribution p is the undirected graph G where two nodes are adjacent iff their corresponding random variables are marginally dependent in p. (It is worth mentioning that our definition of covariance graph is somewhat non-standard. The standard definition states that the lack of an edge between two nodes of G implies that their corresponding random variables are marginally independent in p. This difference in the definition is important in this paper.) In this paper, we present a graphical criterion for reading dependencies from G, under the assumption that p satisfies the graphoid properties as well as weak transitivity and composition. We prove that the graphical criterion is sound and complete in certain sense. We argue that our assumptions are not too restrictive. For instance, all the regular Gaussian probability distributions satisfy them.     

A note on multitype branching process with bounded immigration in random environment

In this paper, we study the total number of progeny, W, before regenerating of multitype branching process with immigration in random environment. We show that the tail probability of |W| is of order t-κ as t→∞, with κ some constant. As an application, we prove a stable law for (L-1) random walk in random environment, generalizing the stable law for the nearest random walk in random environment (see "Kesten, Kozlov, Spitzer: A limit law for random walk in a random environment. Compositio Math., 30, 145-168 (1975)").     

Telegraph Process with Elastic Boundary at the Origin

We investigate the one-dimensional telegraph random process in the presence of an elastic boundary at the origin. This process describes a finite-velocity random motion that alternates between two possible directions of motion (positive or negative). When the particle hits the origin, it is either absorbed, with probability α, or reflected upwards, with probability 1?α. In the case of exponentially distributed random times between consecutive changes of direction, we obtain the distribution of the renewal cycles and of the absorption time at the origin. This investigation is performed both in the case of motion starting from the origin and non-zero initial state. We also study the probability law of the process within a renewal cycle.     

A Note on a Composition of Two Random Integral Mappings β and Some Examples

Abstract

The method of random integral representation, that is, the method of representing a given probability measure as the probability distribution of some random integral, was quite successful in the past few decades. In this note, we show that a composition of two random integral mappings ^β is again a random integral mapping. We illustrate our results with some examples.     

Rank-based selection strategies for the random walk process

In many decision situations such as hiring a secretary, selling an asset, or seeking a job, the value of each offer, applicant, or choice is assumed to be an independent, identically distributed random variable. In this paper, we consider a special case where the observations are auto-correlated as in the random walk model for stock prices. For a given random walk process of n observations, we explicitly compute the probability that the j-th observation in the sequence is the maximum or minimum among all n observations. Based on the probability distribution of the rank, we derive several distribution-free selection strategies under which the decision maker's expected utility of selecting the best choice is maximized. We show that, unlike in the classical secretary problem, evaluating more choices in the random walk process does not increase the likelihood of successfully selecting the best.     

Characterizations of the uniform distribution via sample spacings and nonlinear transformations

We prove that an absolutely continuous probability distribution with compact support is uniformly distributed if and only if the mean sample spacings resulting from a random sample of size N are all equal for every integer N. We also present a related characterization of uniformity using nonlinear transformations. We discuss potential applications of these results to hypothesis testing and to testing the effectiveness of different random number generators.     

Formulas for approximating pseudo-Boolean random variables

We consider {0,1}ⁿ as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. We then derive explicit formulas for approximating a pseudo-Boolean random variable by a linear function if the measure is permutation-invariant, and by a function of degree at most k if the measure is a product measure. These formulas generalize results due to Hammer-Holzman and Grabisch-Marichal-Roubens. We also derive a formula for the best faithful linear approximation that extends a result due to Charnes-Golany-Keane-Rousseau concerning generalized Shapley values. We show that a theorem of Hammer-Holzman that states that a pseudo-Boolean function and its best approximation of degree at most k have the same derivatives up to order k does not generalize to this setting for arbitrary probability measures, but does generalize if the probability measure is a product measure.     

Profile of Random Exponential Binary Trees

We introduce the random exponential binary tree (EBT) and study its profile. As customary, the tree is extended by padding each leaf node (considered internal), with the appropriate number of external nodes, so that the outdegree of every internal node is made equal to 2. In a random EBT, at every step, each external node is promoted to an internal node with probability p, stays unchanged with probability 1 - p, and the resulting tree is extended. We study the internal and external profiles of a random EBT and get exact expectations for the numbers of internal and external nodes at each level. Asymptotic analysis shows that the average external profile is richest at level \(\frac {2p}{p+1}n\), and it experiences phase transitions at levels a n, where the a’s are the solutions to an algebraic equation. The rates of convergence themselves go through an infinite number of phase changes in the sublinear range, and then again at the nearly linear levels.     

RENEWAL THEOREM FOR （L, 1）-RANDOM WALK IN RANDOM ENVIRONMENT

We consider a random walk on Z in random environment with possible jumps {-L,…, -1, 1}, in the case that the environment {ωi ： i ∈ Z} are i.i.d.. We establish the renewal theorem for the Markov chain of ＂the environment viewed from the particle＂ in both annealed probability and quenched probability, which generalize partially the results of Kesten （1977） and Lalley （1986） for the nearest random walk in random environment on Z, respectively. Our method is based on （L, 1）-RWRE formulated in Hong and Wang the intrinsic branching structure within the （2013）.     

Transforms of pseudo-Boolean random variables

As in earlier works, we consider {0,1}ⁿ as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. Under the assumption that the coordinate random variables are independent, we show it is very easy to give an orthonormal basis for the space of pseudo-Boolean random variables of degree at most k. We use this orthonormal basis to find the transform of a given pseudo-Boolean random variable and to answer various least squares minimization questions.     

Linear Extensions and Comparable Pairs in Partial Orders

We study the number of linear extensions of a partial order with a given proportion of comparable pairs of elements, and estimate the maximum and minimum possible numbers. We also consider a random interval partial order on n elements, which has close to a third of the pairs comparable with high probability: we show that the number of linear extensions is n! 2^?Θ(n) with high probability.     

Attainable densities for random maps

We consider a random map T=T(Γ,ω), where Γ=(τ₁,τ₂,…,τK) is a collection of maps of an interval and ω=(p₁,p₂,…,pK) is a collection of the corresponding position dependent probabilities, that is, pk(x)?0 for k=1,2,…,K and . At each step, the random map T moves the point x to τk(x) with probability pk(x). For a fixed collection of maps Γ, T can have many different invariant probability density functions, depending on the choice of the (weighting) probabilities ω. Most of the results in this paper concern random maps where Γ is a family of piecewise linear semi-Markov maps. We investigate properties of the set of invariant probability density functions of T that are attainable by allowing the probabilities in ω to vary in a certain class of functions. We prove that the set of all attainable densities can be determined algorithmically. We also study the duality between random maps generated by transformations and random maps constructed from a collection of their inverse branches. Such representation may be of greater interest in view of new methods of computing entropy [W. S?omczyński, J. Kwapień, K. ?yczkowski, Entropy computing via integration over fractal measures, Chaos 10 (2000) 180-188].     

Spectra of Large Random Trees

We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees that we call probability fringe convergence, we show that the empirical spectral distributions for many random tree models converge to a deterministic (model-dependent) limit as the number of vertices goes to infinity. Moreover, the masses assigned by the empirical spectral distributions to individual points also converge in distribution to constants. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain lower bounds on the mass assigned to zero by the empirical spectral measures via the connection between the number of zero eigenvalues of the adjacency matrix of a tree and the cardinality of a maximal matching on the tree. In particular, we employ a simplified version of an algorithm due to Karp and Sipser to construct maximal matchings and understand their properties. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, nonnegative random variables with finite expected value, thereby significantly extending a result obtained by Aldous and Steele in the special case of uniform random trees. We greatly generalize a celebrated result obtained by Schwenk for the uniform random trees by showing that if any ensemble converges in the probability fringe sense and a very mild further condition holds, then, with probability converging to one, the spectrum of a realization is shared by at least one other (nonisomorphic) tree. For the linear preferential attachment model with parameter a>?1, we show that for any fixed k, the k largest eigenvalues jointly converge in distribution to a nontrivial limit when rescaled by $n^{1/2\gamma_{a}}$ , where ?? _a =a+2 is the Malthusian rate of growth parameter for an associated continuous-time branching process.     

Minimum variance quadratic unbiased estimators as a tool to identify compound normal distributions

We derive the minimum variance quadratic unbiased estimator (MIVQUE) of the variance of the components of a random vector having a compound normal distribution (CND). We show that the MIVQUE converges in probability to a random variable whose distribution is essentially the mixing distribution characterising the CND. This fact is very important, because the MIVQUE allows us to make out the signature of a particular CND, and notably allows us to check if an hypothesis of normality for multivariate observations y₁,…,y_M is plausible.     

Decomposable processes and continuous products of probability spaces

Sequences of independent random variables and products of probability spaces are just two ways of looking at the same thing. The natural generalization of a sequence of independent random variables is a decomposable process. We introduce a corresponding generalization of a product of probability spaces, which will be called a factored probability space, and study the structure and classification of such systems and their relation to decomposable processes.     

Two Applications of Random Spanning Forests

We use random spanning forests to find, for any Markov process on a finite set of size n and any positive integer \(m \le n\), a probability law on the subsets of size m such that the mean hitting time of a random target that is drawn from this law does not depend on the starting point of the process. We use the same random forests to give probabilistic insights into the proof of an algebraic result due to Micchelli and Willoughby and used by Fill and by Miclo to study absorption times and convergence to equilibrium of reversible Markov chains. We also introduce a related coalescence and fragmentation process that leads to a number of open questions.     

Hitting times with taboo for a random walk

For a symmetric homogeneous and irreducible random walk on the d-dimensional integer lattice, which have a finite variance of jumps, we study passage times (taking values in [0,??]) determined by a starting point x, a hitting state y, and a taboo state z. We find the probability that these passage times are finite, and study the distribution tail. In particular, it turns out that, for the above-mentioned random walks on ? ^d except for a simple random walk on ?, the order of the distribution tail decrease is specified by dimension d only. In contrast, for a simple random walk on ?, the asymptotic properties of hitting times with taboo essentially depend on mutual location of the points x, y, and z. These problems originated in recent study of a branching random walk on ? ^d with a single source of branching.     

Description of random fields by means of one-point finite-conditional distributions

The aim of this note is to investigate the relationship between strictly positive random fields on a lattice ? ^ν and the conditional probability measures at one point given the values on a finite subset of the lattice ? ^ν . We exhibit necessary and sufficient conditions for a one-point finite-conditional system to correspond to a unique strictly positive probability measure. It is noteworthy that the construction of the aforementioned probability measure is done explicitly by some simple procedure. Finally, we introduce a condition on the one-point finite conditional system that is sufficient for ensuring the mixing of the underlying random field.