Power law distributions have been repeatedly observed in a wide variety of socioeconomic, biological, and technological areas. In many of the observations, e.g., city populations and sizes of living ...organisms, the objects of interest evolve because of the replication of their many independent components, e.g., births and deaths of individuals and replications of cells. Furthermore, the rates of replications are often controlled by exogenous parameters causing periods of expansion and contraction, e.g., baby booms and busts, economic booms and recessions, etc. In addition, the sizes of these objects often have reflective lower boundaries, e.g., cities do not fall below a certain size, low-income individuals are subsidized by the government, companies are protected by bankruptcy laws, etc.
Hence, it is natural to propose reflected modulated branching processes as generic models for many of the preceding observations. Indeed, our main results show that the proposed mathematical models result in power law distributions under quite general polynomial Gärtner-Ellis conditions, the generality of which could explain the ubiquitous nature of power law distributions. In addition, on a logarithmic scale, we establish an asymptotic equivalence between the reflected branching processes and the corresponding multiplicative ones. The latter, as recognized by Goldie Goldie, C. M. 1991. Implicit renewal theory and tails of solutions of random equations.
Ann. Appl. Probab.
1
(1) 126-166, is known to be dual to queueing/additive processes. We emphasize this duality further in the generality of stationary and ergodic processes.
We investigate a widely popular least-recently-used (LRU) cache replacement algorithm with semi-Markov modulated requests. Semi-Markov processes provide the flexibility for modeling strong ...statistical correlation, including the widely reported long-range dependence in the World Wide Web page request patterns. When the frequency of requesting a page
n is equal to the generalized Zipf's law
c
/
n
α
,
α
>
1
, our main result shows that the cache fault probability is asymptotically, for large cache sizes, the same as in the corresponding LRU system with i.i.d. requests. The result is asymptotically explicit and appears to be the first computationally tractable average-case analysis of LRU caching with statistically dependent request sequences. The surprising insensitivity of LRU caching performance demonstrates its robustness to changes in document popularity. Furthermore, we show that the derived asymptotic result and simulation experiments are in excellent agreement, even for relatively small cache sizes.
We study the conditional sojourn time distributions of processor sharing (PS), foreground background processor sharing (FBPS) and shortest remaining processing time first (SRPT) scheduling ...disciplines on an event where the job size of a customer arriving in stationarity is smaller than exactly
k
≥0 out of the preceding
m
≥
k
arrivals. Then, conditioning on the preceding event, the sojourn time distribution of this newly arriving customer behaves asymptotically the same as if the customer were served in isolation with a server of rate (1−
ρ
)/(
k
+1) for PS/FBPS, and (1−
ρ
) for SRPT, respectively, where
ρ
is the traffic intensity. Hence, the introduced notion of conditional limits allows us to distinguish the asymptotic performance of the studied schedulers by showing that SRPT exhibits considerably better asymptotic behavior for relatively smaller jobs than PS/FBPS.
Inspired by the preceding results, we propose an approximation to the SRPT discipline based on a novel adaptive job grouping mechanism that uses relative size comparison of a newly arriving job to the preceding
m
arrivals. Specifically, if the newly arriving job is smaller than
k
and larger than
m
−
k
of the previous
m
jobs, it is routed into class
k
. Then, the classes of smaller jobs are served with higher priorities using the static priority scheduling. The good performance of this mechanism, even for a small number of classes
m
+1, is demonstrated using the asymptotic queueing analysis under the heavy-tailed job requirements. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.
It was recently proved by Jelenković and Radovanović (2004) that the least-recently-used (LRU) caching policy, in the presence of semi-Markov-modulated requests that have a generalized Zipf's law ...popularity distribution, is asymptotically insensitive to the correlation in the request process. However, since the previous result is asymptotic, it remains unclear how small the cache size can become while still retaining the preceding insensitivity property. In this paper, assuming that requests are generated by a nearly completely decomposable Markov-modulated process, we characterize the critical cache size below which the dependency of requests dominates the cache performance. This critical cache size is small relative to the dynamics of the modulating process, and in fact is sublinear with respect to the sojourn times of the modulated chain that determines the dependence structure.
It is well known that the static caching algorithm that keeps the most frequently requested documents in the cache is optimal in case when documents are of the same size and requests are independent ...and identically distributed. However, it is hard to develop explicit and provably optimal caching algorithms when requests are statistically correlated. In this paper, we show that keeping the most frequently requested documents in the cache is still optimal for large cache sizes even if the requests are strongly correlated.
Consider distributional fixed point equations of the form R=Df(Q,Ci,Ri,1≤i≤N), where f(⋅) is a possibly random real-valued function, N∈{0,1,2,3,…}∪{∞}, {Ci}i∈N are real-valued random weights and ...{Ri}i∈N are iid copies of R, independent of (Q,N,C1,C2,…); =D represents equality in distribution. Fixed point equations of this type are important for solving many applied probability problems, ranging from the average case analysis of algorithms to statistical physics. We develop an Implicit Renewal Theorem that enables the characterization of the power tail behavior of the solutions R to many equations of multiplicative nature that fall into this category. This result extends the prior work in Jelenković and Olvera-Cravioto (2012) 16, which assumed nonnegative weights {Ci}, to general real-valued weights. We illustrate the developed theorem by deriving the power tail asymptotics of the solution R to the linear equation R=D∑i=1NCiRi+Q.
Maximums on trees Jelenković, Predrag R.; Olvera-Cravioto, Mariana
Stochastic processes and their applications,
January 2015, 2015-01-00, Volume:
125, Issue:
1
Journal Article
Peer reviewed
Open access
We study the minimal/endogenous solution R to the maximum recursion on weighted branching trees given by R=D(⋁i=1NCiRi)∨Q, where (Q,N,C1,C2,…) is a random vector with N∈N∪{∞}, P(|Q|>0)>0 and ...nonnegative weights {Ci}, and {Ri}i∈N is a sequence of i.i.d. copies of R independent of (Q,N,C1,C2,…); =D denotes equality in distribution. Furthermore, when Q>0 this recursion can be transformed into its additive equivalent, which corresponds to the maximum of a branching random walk and is also known as a high-order Lindley equation. We show that, under natural conditions, the asymptotic behavior of R is power-law, i.e., P(|R|>x)∼Hx−α, for some α>0 and H>0. This has direct implications for the tail behavior of other well known branching recursions.
Cells contain elaborate and interconnected networks of protein polymers, which make up the cytoskeleton. The cytoskeleton governs the internal positioning and movement of vesicles and organelles and ...controls dynamic changes in cell polarity, shape, and movement. Many of these processes require tight control of the size and shape of cytoskeletal structures, which is achieved despite rapid turnover of their molecular components. Here we review mechanisms by which cells control the size of filamentous cytoskeletal structures, from the point of view of simple quantitative models that take into account stochastic dynamics of their assembly and disassembly. Significantly, these models make experimentally testable predictions that distinguish different mechanisms of length control. Although the primary focus of this review is on cytoskeletal structures, we believe that the broader principles and mechanisms discussed herein will apply to a range of other subcellular structures whose sizes are tightly controlled and are linked to their functions.
Consider a sequence of stationary GI/D/N queues indexed by Narrow upinfinity, with servers' utilization 1-beta/sqrt{N}, beta>0. For such queues we show that the scaled waiting times sqrt{N}W(sub)N ...converge to the (finite) supremum of a Gaussian random walk with drift -beta. This further implies a corresponding limit for the number of customers in the system, an easily computable non-degenerate limiting delay probability in terms of Spitzer's random-walk identities, and sqrt{N} rate of convergence for the latter limit. Our asymptotic regime is important for rational dimensioning of large-scale service systems, for example telephone- or internet-based, since it achieves, simultaneously, arbitrarily high service-quality and utilization-efficiency. PUBLICATION ABSTRACT
We extend Goldie's (1991) implicit renewal theorem to enable the analysis of recursions on weighted branching trees. We illustrate the developed method by deriving the power-tail asymptotics of the ...distributions of the solutions
R
to
and similar recursions, where (
Q
,
N
,
C
1
,
C
2
,…) is a nonnegative random vector with
N
∈ {0, 1, 2, 3,…} ∪ {∞}, and
are independent and identically distributed copies of
R
, independent of (
Q
,
N
,
C
1
,
C
2
,…); here ‘∨’ denotes the maximum operator.
PDF
