Balls into bins via local search: Cover time and maximum load

Abstract–We study a natural process for allocating balls into bins that are organized as the vertices of an undirected graph . Balls arrive one at a time. When a ball arrives, it first chooses a vertex in uniformly at random. Then the ball performs a local search in starting from until it reaches a vertex with local minimum load, where the ball is finally placed on. Then the next ball arrives and this procedure is repeated. For the case , we give an upper bound for the maximum load on graphs with bounded degrees. We also propose the study of the cover time of this process, which is defined as the smallest so that every bin has at least one ball allocated to it. We establish an upper bound for the cover time on graphs with bounded degrees. Our bounds for the maximum load and the cover time are tight when the graph is vertex transitive or sufficiently homogeneous. We also give upper bounds for the maximum load when . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 681–702, 2016     

Balls,bins, and embeddings of partial k-star designs

Define a $k$-star to be the complete bipartite graph $K_{1,k}$. In a 2014 article, Hoffman and Roberts prove that a partial $k$-star decomposition of $K_n$ can be embedded in a $k$-star decomposition of $K_{n+s}$ where $s$ is at most $7k?4$ if $k$ is odd and $8k?4$ if $k$ is even. In our work, we offer a straightforward construction for embedding partial $k$-star designs and lower these bounds to $3k?2$ and $4k?2$, respectively.     

A concept of negative dependence using stochastic ordering

A concept of negative dependence called negative dependence by stochastic ordering is introduced. This concept satisfies various closure properties. It is shown that three models for negetive dependence satisfy it and that it implies the basic negative orthant inequalities. This concept is also satisfied by the multinomial, multivariate hypergeometric. Dirichlet and Dirichlet compound multinomial distributions. Furthermore, the joint distribution of ranks of a sample and the multivariate normal with nonpositive pairwise correlations also satisfy this condition. The positive dependence analog of this condition is also studied.     

Minimising bins in transmission systems

This paper deals with the problem of minimising the transmission cost in an EDI system and proves the optimality of a policy which minimizes the slack of partial sums under conditions with practical interpretations. This policy is shown to be useful as a heuristic in more general cases.     

The forgetfulness of balls and bins

We find the asymptotic total variation distance between two distributions on configurations of m balls in n labeled bins: in the first, each ball is placed in a bin uniformly at random; in the second, k balls are planted in an arbitrary but fixed arrangement and the remaining m ‐ k balls placed uniformly at random. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Reducing model risk via positive and negative dependence assumptions

We give analytical bounds on the Value-at-Risk and on convex risk measures for a portfolio of random variables with fixed marginal distributions under an additional positive dependence structure. We show that assuming positive dependence information in our model leads to reduced dependence uncertainty spreads compared to the case where only marginals information is known. In more detail, we show that in our model the assumption of a positive dependence structure improves the best-possible lower estimate of a risk measure, while leaving unchanged its worst-possible upper risk bounds. In a similar way, we derive for convex risk measures that the assumption of a negative dependence structure leads to improved upper bounds for the risk while it does not help to increase the lower risk bounds in an essential way. As a result we find that additional assumptions on the dependence structure may result in essentially improved risk bounds.     

Air traverse time in grain bins

To maintain the quality of cereal grains during storage, it is necessary to keep the grain cool and free from insects, and typical methods for dealing with these problems are considered in this paper. In particular the insect population is controlled by fumigating the grain bed with carbon dioxide gas and the grain is cooled by forcing ambient air through the bed. In both problems, the equations which describe the physical processes contain a mixture of advection and diffusion or conduction terms. This paper explores the relationship between traverse time and heat and mass transfer and gains an insight into the grain storage processes that are controlled by forced convection. When heat and mass transport is dominated by the advection terms, the equations are simplified by changing variables from the (x,y) space coordinates to (ψ,τ), where ψ is the stream function for the problem and the traverse time τ at a point in the storage bin is the time taken for the air to travel to the point from the inlet duct. The conditions are described for the equations to be independent of ψ, with the main condition being that the derivatives of the metrics g₁₁, g₁₂ and g₂₂ with respect to ψ are small enough. If the equations are independent of ψ then the dependent variable (concentration or temperature) will be constant on lines of constant traverse time τ. This relationship between traverse time and the cooling or fumigation pattern can be used in the design of storage bins since it implies that the best outlet surface is a line of constant τ.     

A Pair in a Crowd of Unit Balls

Let F be a family of mutually nonoverlapping unit balls in the n -dimensional Euclidean space Rⁿ. The distance between the centres of A,B   F is denoted by d(A, B). We prove, among others, that if d(A, B)  <  4 and n ≥  5, then A andB are always visible from each other, that is, a light ray emanating from the surface of A reaches B without being blocked by other unit balls. Furthermore, if d(A, B)  < 2n / 2, then any small “shake’ of F can make A, B visible from each other.     

Tail negative dependence and its applications for aggregate loss modeling

Tail order of copulas can be used to describe the strength of dependence in the tails of a joint distribution. When the value of tail order is larger than the dimension, it may lead to tail negative dependence. First, we prove results on conditions that lead to tail negative dependence for Archimedean copulas. Using the conditions, we construct new parametric copula families that possess upper tail negative dependence. Among them, a copula based on a scale mixture with a generalized gamma random variable (GGS copula) is useful for modeling asymmetric tail negative dependence. We propose mixed copula regression based on the GGS copula for aggregate loss modeling of a medical expenditure panel survey dataset. For this dataset, we find that there exists upper tail negative dependence between loss frequency and loss severity, and the introduction of tail negative dependence structures significantly improves the aggregate loss modeling.     

发现并定位黄球

本文讨论了如何设置红球和蓝球的数量和位置,发现圆柱区域内的黄球并进行定位的问题.我们考虑了一对红球蓝球发现黄球并定位的问题,在此基础上进行扩展,基本解决了黄球的发现并定位的问题.在静止黄球发现问题中,采用了正三角形扩展和正六边形扩展两种方法.在静止黄球的定位问题中,我们结合正三角形和正六边形运用了旋转法和添点法进行扩展.在运动黄球的定位问题中,讨论了体积概率模型和时间概率模型,给出了两种模型的概率求解公式.在系统协同定位模型中,我们给出了发现定位分步模型和周期系统跟踪模型,其中后者在仿真中实现了大于80%的定位性能,该系统可以简单扩展为多目标快速定位问题.此外,文章讨论了精确测量和颜色切换模型,快速定位问题,多目标定位等问题.     

Balls in complex hyperbolic manifolds

We get an explicit lower bound for the radius of a Bergman ball contained in the Dirichlet fundamental polyhedron of a torsion free discrete group G伡PU(n,1)acting on complex hyperbolic space.As an application,we also give a lower bound for the volumes of complex hyperbolic n-manifolds.     

Inscribed Balls and Their Centers

A ball of maximal radius inscribed in a convex closed bounded set with a nonempty interior is considered in the class of uniformly convex Banach spaces. It is shown that, under certain conditions, the centers of inscribed balls form a uniformly continuous (as a set function) set-valued mapping in the Hausdorff metric. In a finite-dimensional space of dimension n, the set of centers of balls inscribed in polyhedra with a fixed collection of normals satisfies the Lipschitz condition with respect to sets in the Hausdorff metric. A Lipschitz continuous single-valued selector of the set of centers of balls inscribed in such polyhedra can be found by solving n + 1 linear programming problems.     

Bandwidth selection for the local polynomial estimator under dependence: A simulation study

Summary  Seven of the most popular methods for bandwidth selection in regression estimation are compared by means of a thorough simulation study, when the local polynomial estimator is used and the observations are dependent. The study is completed with two plug-in bandwidths for the generalized local polynomial estimator proposed by Vilar-Fernandez & Francisco-Fernández (2002).     

Characterizing mutual exclusivity as the strongest negative multivariate dependence structure

Mutual exclusivity is an extreme negative dependence structure that was first proposed and studied in Dhaene and Denuit (1999) in the context of insurance risks. In this article, we revisit this notion and present versatile characterizations of mutually exclusive random vectors via their pairwise counter-monotonic behaviour, minimal convex sum property, distributional representation and the characteristic function of the sum of their components. These characterizations highlight the role of mutual exclusivity in generalizing counter-monotonicity as the strongest negative dependence structure in a multi-dimensional setting.     

A Schwarz Lemma at the Boundary of Hilbert Balls

In this paper, the authors prove a general Schwarz lemma at the boundary for the holomorphic mapping f between unit balls B and B′in separable complex Hilbert spaces H and H′, respectively. It is found that if the mapping f ∈ C~(1+α)at z_0∈ ?B with f(z_0) = w_0∈ ?B′, then the Fr′echet derivative operator Df(z_0) maps the tangent space Tz_0(?B~n) to Tw_0(?B′), the holomorphic tangent space T_(z_0)~(1,0)(?B~n) to T_(w_0)~(1,0)(?B′),respectively.     

On intermediate inquisitive and dependence logics: An algebraic study

This article provides an algebraic study of intermediate inquisitive and dependence logics. While these logics are usually investigated using team semantics, here we introduce an alternative algebraic semantics and we prove it is complete for all intermediate inquisitive and dependence logics. To this end, we define inquisitive and dependence algebras and we investigate their model-theoretic properties. We then focus on finite, core-generated, well-connected inquisitive and dependence algebras: we show they witness the validity of formulas true in inquisitive algebras, and of formulas true in well-connected dependence algebras. Finally, we obtain representation theorems for finite, core-generated, well-connected, inquisitive and dependence algebras and we prove some results connecting team and algebraic semantics.     

Fixed Points and Stable Balls in Ultrametric Spaces

In [2] we presented a fixed point theorem for strictly contracting mappings of spherically complete ultrametric spaces; in this paper we show how this theorem looks like if we assume only that the mappings are contracting.