The onset of dominance in balls‐in‐bins processes with feedback

Consider a balls‐in‐bins process in which each new ball goes into a given bin with probability proportional to f(n), where n is the number of balls currently in the bin and f is a fixed positive function. It is known that these so‐called balls‐in‐bins processes with feedback have a monopolistic regime: if f(x) = x^p for p > 1, then there is a finite time after which one of the bins will receive all incoming balls. Our goal in this article is to quantify the onset of monopoly. We show that the initial number of balls is large and bin 1 starts with a fraction α > 1/2 of the balls, then with very high probability its share of the total number of balls never decreases significantly below α. Thus a bin that obtains more than half of the balls at a “large time” will most likely preserve its position of leadership. However, the probability that the winning bin has a non‐negligible advantage after n balls are in the system is ～const. × n^1‐p, and the number of balls in the losing bin has a power‐law tail. Similar results also hold for more general functions f. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On Keisler singular‐like models

Keisler in [7] proved that for a strong limit cardinal κ and a singular cardinal λ, the transfer relation κ → λ holds. We analyze the λ ‐like models produced in the proof of Keisler's transfer theorem when κ is further assumed to be regular. Our main result shows that with this extra assumption, Keisler's proof can be modified to produce a λ ‐like model M with built‐in Skolem functions that satisfies the following two properties: (1) M is generated by a subset C of order‐type λ. (2) M can be written as union of an elementary end extension chain 〈N_i: i < δ 〉 such that for each i < δ, there is an initial segment C_i of C with C_i ? N_i, and N_i ∩ (C \Ci) = ??. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Distribution sensitivity in a highway flow model

We examine a model of traffic flow on a highway segment, where traffic can be impaired by random incidents (usually, collisions). Using analytical and numerical methods, we show the degree of sensitivity that the model exhibits to the distributions of service times (in the queueing model) and incident clearance times. Its sensitivity to the distribution of time until an incident is much less pronounced. Our analytical methods include an M/G_t/∞ analysis (G_t denotes a service process whose distribution changes with time) and a fluid approximation for an M/M/c queue with general distributions for the incident clearance times. Our numerical methods include M/PH₂/c/K models with many servers and with phase‐type distributions for the time until an incident occurs or is cleared. We also investigate different time scalings for the rate of incident occurrence and clearance. Copyright © 2009 John Wiley & Sons, Ltd.     

Existence and uniqueness of an invariant probability for a class of Feller Markov chains

We consider the class of Feller Markov chains on a phase spaceX whose kernels mapC ₀ (X), the space of bounded continuous functions that vanish at infinity, into itself. We provide a necessaryand sufficient condition for the existence of an invariant probability measure using a generalized Farkas Lemma. This condition is a Lyapunov type criterion that can be checked in practice. We also provide a necessaryand sufficient condition for existence of aunique invariant probability measure. When the spaceX is compact, the conditions simplify.     

Ruin Probabilities under a Markovian Risk Model

In this paper, a Markovian risk model is developed, in which the occurrence of the claims is described by a point process {N(t)}t≥0 with N(t) being the number of jumps of a Markov chain during the interval [0, t]. For the model, the explicit form of the ruin probability ψ(0) and the bound for the convergence rate of the ruin probability ψ(u) are given by using the generalized renewal technique developed in this paper.Finally, we prove that the ruin probability ψ(u) is a linear combination of some negative exponential functions in a special case when the claims are exponentially distributed and the Markov chain has an intensity matrix(qij)i,j∈E such that qm = qml and qi=qi(i 1), 1≤i≤m-1.     

On Markov chains induced by partitioned transition probability matrices

Let S be a denumerable state space and let P be a transition probability matrix on S. If a denumerable set M of nonnegative matrices is such that the sum of the matrices is equal to P, then we call M a partition of P.     

The connectivity threshold for the min‐degree random graph process

Let ??_n = {G_min(n, M)}_M≥0 denote a min‐degree random multigraph process in which G_min(n, M + 1) is obtained from G_min(n, M) by connecting a randomly chosen vertex of a minimum degree with another vertex of the multigraph. We study the probability that the random multigraph G_min(n, M) is connected. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On triangle‐free random graphs

We show that for every k≥1 and δ>0 there exists a constant c>0 such that, with probability tending to 1 as n→∞, a graph chosen uniformly at random among all triangle‐free graphs with n vertices and M≥cn^3/2 edges can be made bipartite by deleting ⌊δM⌋ edges. As an immediate consequence of this fact we infer that if M/n^3/2→∞ but M/n²→0, then the probability that a random graph G(n, M) contains no triangles decreases as 2^−(1+o(1))M. We also discuss possible generalizations of the above results. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 260–276, 2000     

Lusternik‐Schnirelmann category and systolic category of low‐dimensional manifolds

We show that the geometry of a Riemannian manifold (M, ??) is sensitive to the apparently purely homotopy‐theoretic invariant of M known as the Lusternik‐Schnirelmann category, denoted cat_LS(M). Here we introduce a Riemannian analogue of cat_LS(M), called the systolic category of M. It is denoted cat_sys(M) and defined in terms of the existence of systolic inequalities satisfied by every metric ??, as initiated by C. Loewner and later developed by M. Gromov. We compare the two categories. In all our examples, the inequality cat_sysM ≤ cat_LSM is satisfied, which typically turns out to be an equality, e.g., in dimension 3. We show that a number of existing systolic inequalities can be reinterpreted as special cases of such equality and that both categories are sensitive to Massey products. The comparison with the value of cat_LS(M) leads us to prove or conjecture new systolic inequalities on M. © 2006 Wiley Periodicals, Inc.     

A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions

Let M_T be the mean first passage matrix for an n‐state ergodic Markov chain with a transition matrix T. We partition T as a 2×2 block matrix and show how to reconstruct M_T efficiently by using the blocks of T and the mean first passage matrices associated with the non‐overlapping Perron complements of T. We present a schematic diagram showing how this method for computing M_T can be implemented in parallel. We analyse the asymptotic number of multiplication operations necessary to compute M_T by our method and show that, for large size problems, the number of multiplications is reduced by about 1/8, even if the algorithm is implemented in serial. We present five examples of moderate sizes (of orders 20–200) and give the reduction in the total number of flops (as opposed to multiplications) in the computation of M_T. The examples show that when the diagonal blocks in the partitioning of T are of equal size, the reduction in the number of flops can be much better than 1/8. Copyright © 2001 John Wiley & Sons, Ltd.     

On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph

A uniform attachment graph (with parameter k), denoted G_n,k in the paper, is a random graph on the vertex set [n], where each vertex v makes k selections from [v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of G_n,k to show that the conductance of G_n,k is of order . We also study the bootstrap percolation on G_n,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.     

Dynamical behaviors of a discrete HIV‐1 virus model with bilinear infective rate

We establish a discrete virus dynamic model by discretizing a continuous HIV‐1 virus model with bilinear infective rate using ‘hybrid’ Euler method. We discuss not only the existence and global stability of the uninfected equilibrium but also the existence and local stability of the infected equilibrium. We prove that there exists a crucial value similar to that of the continuous HIV‐1 virus dynamics, which is called the basic reproductive ratio of the virus. If the basic reproductive ratio of the virus is less than one, the uninfected equilibrium is globally asymptotically stable. If the basic reproductive ratio of the virus is larger than one, the infected equilibrium exists and is locally stable. Moreover, we consider the permanence for such a system by constructing a Lyapunov function v_n. Copyright © 2013 John Wiley & Sons, Ltd.     

A two‐level method in space and time for the Navier‐Stokes equations

A two‐level method in space and time for the time‐dependent Navier‐Stokes equations is considered in this article. The approximate solution u_M∈H_M is decomposed into the large eddy component v∈H_m(m < M) and the small eddy component w∈H. We obtain the large eddy component v by solving a standard Galerkin equation in a coarse‐level subspace H_m with a time step length k, whereas the small eddy component w is derived by solving a linear equation in an orthogonal complement subspace H with a time step length pk, where p is a positive integer. The analysis shows that our two‐level scheme has long‐time stability and can reach the same accuracy as the standard Galerkin method in fine‐level subspace H_M for an appropriate configuration of p and m. Moreover, some numerical examples are provided to complement our theoretical analysis. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Asymptotic analysis for loss probability of queues with finite <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 type structure

This paper discusses the asymptotic behavior of the loss probability for general queues with finite GI/M/1 type structure such as GI/M/c/K, SM/M/1/K and GI/MSP/1/K queues. We find an explicit expression for the asymptotic behavior of the loss probability as K tends to infinity. With the result, it is shown that the loss probability tends to 0 at a geometric rate. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

Long‐time dynamics of KdV solitary waves over a variable bottom

We study the variable‐bottom, generalized Korteweg—de Vries (bKdV) equation ?_tu = ??_x(?u + f(u) ? b(t,x)u), where f is a nonlinearity and b is a small, bounded, and slowly varying function related to the varying depth of a channel of water. Many variable‐coefficient KdV‐type equations, including the variable‐coefficient, variable‐bottom KdV equation, can be rescaled into the bKdV. We study the long‐time behavior of solutions with initial conditions close to a stable, b = 0 solitary wave. We prove that for long time intervals, such solutions have the form of the solitary wave whose center and scale evolve according to a certain dynamical law involving the function b(t,x) plus an H¹(?)‐small fluctuation. © 2005 Wiley Periodicals, Inc.     

On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

Nontopological Condensates for the Self‐Dual Chern‐Simons‐Higgs Model

For the abelian self‐dual Chern‐Simons‐Higgs model we address existence issues of periodic vortex configurations—the so‐called condensates—of nontopological type as k → 0, where k > 0 is the Chern‐Simons parameter. We provide a positive answer to the longstanding problem on the existence of nontopological condensates with magnetic field concentrated at some of the vortex points (as a sum of Dirac measures) as k → 0, a question that is of definite physical interest. © 2015 Wiley Periodicals, Inc.     

A block‐preconditioner for a special regularized least‐squares problem

We consider a linear system of the form A₁x₁ + A₂x₂ + η=b₁. The vector ηconsists of independent and identically distributed random variables all with mean zero. The unknowns are split into two groups x₁ and x₂. It is assumed that AA₁ has full rank and is easy to invert. In this model, usually there are more unknowns than observations and the resulting linear system is most often consistent having an infinite number of solutions. Hence, some constraint on the parameter vector x is needed. One possibility is to avoid rapid variation in, e.g. the parameters x₂. This can be accomplished by regularizing using a matrix A₃, which is a discretization of some norm (e.g. a Sobolev space norm). We formulate the problem as a partially regularized least‐squares problem and use the conjugate gradient method for its solution. Using the special structure of the problem we suggest and analyse block‐preconditioners of Schur compliment type. We demonstrate their effectiveness in some numerical tests. The test examples are taken from an application in modelling of substance transport in rivers. Copyright © 2007 John Wiley & Sons, Ltd.     

Towards a Mathematical Theory of Super‐resolution

This paper develops a mathematical theory of super‐resolution. Broadly speaking, super‐resolution is the problem of recovering the fine details of an object—the high end of its spectrum—from coarse scale information only—from samples at the low end of the spectrum. Suppose we have many point sources at unknown locations in [0,1] and with unknown complex‐valued amplitudes. We only observe Fourier samples of this object up to a frequency cutoff f_c. We show that one can super‐resolve these point sources with infinite precision—i.e., recover the exact locations and amplitudes—by solving a simple convex optimization problem, which can essentially be reformulated as a semidefinite program. This holds provided that the distance between sources is at least 2/f_c. This result extends to higher dimensions and other models. In one dimension, for instance, it is possible to recover a piecewise smooth function by resolving the discontinuity points with infinite precision as well. We also show that the theory and methods are robust to noise. In particular, in the discrete setting we develop some theoretical results explaining how the accuracy of the super‐resolved signal is expected to degrade when both the noise level and the super‐resolution factor vary. © 2014 Wiley Periodicals, Inc.