Consider the setting of sparse graphs on N vertices, where the vertices have distinct “names”, which are strings of length O(log N) from a fixed finite alphabet. For many natural probability models, the entropy grows as c N log N for some model-dependent rate constant c. The mathematical content of this paper is the (often easy) calculation of c for a variety of models, in particular for various standard random graph models adapted to this setting. Our broader purpose is to publicize this particular setting as a natural setting for future theoretical study of data compression for graphs, and (more speculatively) for discussion of unorganized versus organized complexity.

Bootstrap percolation (BP) has been used effectively to model phenomena as diverse as emergence of magnetism in materials, spread of infection, diffusion of software viruses in computer networks, adoption of new technologies, and emergence of collective action and cultural fads in human societies. It is defined on an (arbitrary) network of interacting agents whose state is determined by the state of their neighbors according to a threshold rule. In a typical setting, BP starts by random and independent “activation” of nodes with a fixed probability p, followed by a deterministic process for additional activations based on the density of active nodes in each neighborhood (θ activated nodes). Here, we study BP on random geometric graphs (RGGs) in the regime when the latter are (almost surely) connected. Random geometric graphs provide an appropriate model in settings where the neighborhood structure of each node is determined by geographical distance, as in wireless ad hoc and sensor networks as well as in contagion. We derive bounds pc′, pc″ on the critical thresholds such that for all p > p″c full percolation takes place, whereas for p < p′c it does not. We conclude with simulations that compare numerical thresholds with those obtained analytically.

We introduce a level-crossing analysis of the finite time-t probability distributions of the excess life, age, total life, and related quantities of renewal processes. The technique embeds the renewal process as one cycle of a regenerative process with a barrier at level t, whose limiting probability density function leads directly to the time-t quantities. The new method connects the analysis of renewal processes with the analysis of a large class of stochastic models of Operations Research. Examples are given.

Consider an absolutely continuous distribution on [0, ∞) with known mean μ, and hazard rate function, h satisfying, 0<a≤h(t)≤b<∞, for almost all t≥0. We derive the sharp range for σ2, under these constraints.

Let X1, …, Xn be non-negative, independent and identically distributed random variables with a common distribution function F, and denote by X1:n ≤ ··· ≤ Xn:n the corresponding order statistics. In this paper, we investigate the second-order regular variation (2RV) of the tail probabilities of Xk:n and Xj:n − Xi:n under the assumption that $\bar {F}$ is of the 2RV, where 1 ≤ k ≤ n and 1 ≤ i < j ≤ n.

Various large-scale suppliers frequently use web-based spot markets, along with discount stores and foreign distributors, for inventory liquidation. Recognizing the potential benefits of such practices, we consider a multi-period, integrated replenishment, and liquidation problem for a capacitated supplier facing stochastic demand from a spot market along with its primary market (with higher priority contractual customers). In each period, the supplier must decide: (i) how much to produce, and (ii) if there are excess units left after sales to the primary market, how many of these to liquidate. We show that the optimal policy is characterized by two quantities: the critical produce-up-to level and the critical retain-up-to level. We establish bounds for these two quantities. We identify two practical benchmark policies and establish thresholds on the unit revenue earned from the spot market such that one of the two benchmark policies is optimal. We provide closed form expressions to determine these thresholds for the infinite horizon problem under specific conditions on the available production capacity. In general, it is difficult, if not impossible, to theoretically determine these thresholds in closed form for the finite horizon problem. Hence, we report results of a computational study to gain insights regarding the behavior of the optimal policy with respect to the spot market revenue. Our computational results also quantify the benefits of the optimal policy relative to the benchmark policies and examine the effects of demand correlation.

A recent paper by Pozdnyakov and Steele [6] is devoted to distributed sensor networks in which the sensors send summarized information to some remotely located fusion agents. Main focus is on sensors that send their information according to a so-called binary-plus-passive design. Some exact relations in a sequential approach, aimed at making decisions before a given budget is exhausted are presented. In this paper, we provide asymptotic results in the case of more general sensors for increasing budgets. The essential ingredient is the observation that the setting can be modeled within the framework of certain stopped two-dimensional random walks. We also provide asymptotics for the cost for large decision boundaries, and, finally, some comments on the probability of a positive/negative decision as well as on the duration of the process until a decision is made in the binary-plus-passive design.