We revisit the random m-ary search tree and study a finer profile of its node outdegrees with the purpose of exploring possibilities of data structure compression. The analysis is done via Pólya urns. The analysis shows that the number of nodes of each individual node outdegree has a phase transition: Up to m = 26, the number of nodes of outdegree k, for k = 0, 1, …, m, is asymptotically normal; that behavior changes at m = 27. Based on the analysis, we propose a compact m-ary tree that offers significant space saving.

Binary series-parallel (BSP) graphs have applications in transportation modeling, and exhibit interesting combinatorial properties. This work is limited to the second aspect. The BSP graphs of a given size – measured in edges – are enumerated. Under a uniform probability model, we investigate the asymptotic distribution of the order (number of vertices) and the asymptotic average length of a random walk (under different strategies) of large graphs of the same size. The systematic method throughout is to define the graphs, and the features we evaluate by a structural equation (equivalent to a regular expression). The structural equation is translated into an equation for a generating function, which is then analyzed.

In this paper, we propose a novel method for constructing upper bounds of the quasi-stationary distribution of SIS processes. Using this method, we obtain an upper bound that is better than the state-of-the-art upper bound. Moreover, we prove that the fixed point map Φ [7] actually preserves the equilibrium reversed hazard rate order under a certain condition. This allows us to further improve the upper bound. Some numerical results are presented to illustrate the results.

The random neural network is a biologically inspired neural model where neurons interact by probabilistically exchanging positive and negative unit-amplitude signals that has superior learning capabilities compared to other artificial neural networks. This paper considers non-negative least squares supervised learning in this context, and develops an approach that achieves fast execution and excellent learning capacity. This speedup is a result of significant enhancements in the solution of the non-negative least-squares problem which regard (a) the development of analytical expressions for the evaluation of the gradient and objective functions and (b) a novel limited-memory quasi-Newton solution algorithm. Simulation results in the context of optimizing the performance of a disaster management problem using supervised learning verify the efficiency of the approach, achieving two orders of magnitude execution speedup and improved solution quality compared to state-of-the-art algorithms.

De Bruijn's identity shows a link between two fundamental concepts in information theory: entropy and Fisher information. In the literature, De Bruijn's identity has been stated under the assumption of independence between input signal and an additive noise. However, in the real world, the noise could be highly dependent on the main signal. The main aim of this paper is, firstly, to extend De bruijn's identity for signal-dependent noise channels and, secondly, to study how Stein and heat identities are related to De bruijn's identity. Thus, new versions of De Bruijn's identity are introduced in the case when input signal and additive noise are dependent and are jointly distributed according to Archimedean and Gaussian copulas. It is shown that in this generalized model, the derivatives of the differential entropy can be expressed in terms of a function of Fisher information. Our finding enfolds the conventional De Bruijn's identity as some remarks. Then, the equivalence among the new De Bruijn-type identity, Stein's identity and heat equation identity is established. The paper concludes with an application of the developed results in information theory.

In the present paper, we introduce a generalization of the cumulative entropy proposed by Di Crescenzo and Longobardi [8]. This new notion is related to the lower records and the reversed relevation transform. Dynamic version of the newly proposed measure is considered. Several properties including the effect of linear transformations, a two-dimensional version, a normalized version, bounds, stochastic ordering, etc. are studied for the generalized cumulative entropy (GCE). Similar results are obtained for the dynamic GCE. Various relationships with other functions are derived. A class of distributions is introduced and several properties are studied. Finally, empirical GCE is proposed to estimate the newly proposed information measure.

For non-negative random variables with finite means we introduce an analogous of the equilibrium residual-lifetime distribution based on the quantile function. This allows us to construct new distributions with support (0, 1), and to obtain a new quantile-based version of the probabilistic generalization of Taylor's theorem. Similarly, for pairs of stochastically ordered random variables we come to a new quantile-based form of the probabilistic mean value theorem. The latter involves a distribution that generalizes the Lorenz curve. We investigate the special case of proportional quantile functions and apply the given results to various models based on classes of distributions and measures of risk theory. Motivated by some stochastic comparisons, we also introduce the “expected reversed proportional shortfall order”, and a new characterization of random lifetimes involving the reversed hazard rate function.

A large increase in the number and types of vehicles occurred due to the growth in population. This fact brings the need for efficient vehicle classification systems that can be used in traffic surveillance and intelligent transportation systems. In this study, a multi-type vehicle classification system based on Random Neural Networks (RNNs) and Bag-Of-Visual Words (BOVWs) is developed. A 10-fold cross-validation technique is used, with a large dataset, to assess the proposed approach. Moreover, the BOVW–RNN's classification performance is compared with LIVCS, a vehicle classification system based on RNNs. The results reveal that BOVW–RNN classification system produces more reliable and accurate classification results than LIVCS. The main contribution of this paper is that the developed system can serve as a framework for many vehicle classification systems.

This paper deals with the mean residual life function (MRLF) and its monotonicity in the case of additive and multiplicative hazard rate models. It is shown that additive (multiplicative) hazard rate does not imply reduced (proportional) MRLF and vice versa. Necessary and sufficient conditions are obtained for the two models to hold simultaneously. In the case of non-monotonic failure rates, the location of the turning points of the MRLF is investigated in both the cases. The case of random additive and multiplicative hazard rate is also studied. The monotonicity of the mean residual life is studied along with the location of the turning points. Examples are provided to illustrate the results.

Markov chains (MCs) are widely used to model systems which evolve by visiting the states in their state spaces following the available transitions. When such systems are composed of interacting subsystems, they can be mapped to a multi-dimensional MC in which each subsystem normally corresponds to a different dimension. Usually the reachable state space of the multi-dimensional MC is a proper subset of its product state space, that is, Cartesian product of its subsystem state spaces. Compact storage of the matrix underlying such a MC and efficient implementation of analysis methods using Kronecker operations require the set of reachable states to be represented as a union of Cartesian products of subsets of subsystem state spaces. The problem of partitioning the reachable state space of a three or higher dimensional system with a minimum number of partitions into Cartesian products of subsets of subsystem state spaces is shown to be NP-complete. Two algorithms, one merge based the other refinement based, that yield possibly non-optimal partitionings are presented. Results of experiments on a set of problems from the literature and those that are randomly generated indicate that, although it may be more time and memory consuming, the refinement based algorithm almost always computes partitionings with a smaller number of partitions than the merge-based algorithm. The refinement based algorithm is insensitive to the order in which the states in the reachable state space are processed, and in many cases it computes partitionings that are optimal.

It is pointed out that the weighted generalized gamma distribution of Priyadarshani and Oluyede [2] is a generalized gamma distribution.

Motivated by applications to multi-antenna wireless networks, we propose a distributed and asynchronous algorithm for stochastic semidefinite programming. This algorithm is a stochastic approximation of a continuous-time matrix exponential scheme which is further regularized by the addition of an entropy-like term to the problem's objective function. We show that the resulting algorithm converges almost surely to an ɛ-approximation of the optimal solution requiring only an unbiased estimate of the gradient of the problem's stochastic objective. When applied to throughput maximization in wireless systems, the proposed algorithm retains its convergence properties under a wide array of mobility impediments such as user update asynchronicities, random delays and/or ergodically changing channels. Our theoretical analysis is complemented by extensive numerical simulations, which illustrate the robustness and scalability of the proposed method in realistic network conditions.

Autonomic computing is emerging as a significant new approach to the design of computer services. Its goal is the development of services that are able to manage themselves with minimal direct human intervention, and, in particular, are able to sense their environment and to tune themselves to meet end-user needs. However, the impact on performance of the interaction between multiple uncoordinated self-optimizing services is not yet well understood. We present some recent results on a non-cooperative load-balancing game which help to better understand the result of this interaction. In this game, users generate jobs of different services, and the jobs have to be processed on one of the servers of a computing platform. Each service has its own dispatcher which probabilistically routes jobs to servers so as to minimize the mean processing cost of its own jobs. We first investigate the impact of heterogeneity in the amount of incoming traffic routed by dispatchers and present a result stating that, for a fixed amount of total incoming traffic, the worst-case overall performance occurs when each dispatcher routes the same amount of traffic. Using this result we then study the so-called Price of Anarchy (PoA), an oft-used worst-case measure of the inefficiency of non-cooperative decentralized architectures. We give explicit bounds on the PoA for cost functions representing the mean delay of jobs when the service discipline is PS or SRPT. These bounds indicate that significant performance degradations can result from the selfish behavior of self-optimizing services. In practice, though, the worst-case scenario may occur rarely, if at all. Some recent results suggest that for the game under consideration the PoA is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem.

Motivated by applications in areas such as cloud computing and information technology services, we consider GI/GI/1 queueing systems under workloads (arrival and service processes) that vary according to one discrete time scale and under controls (server capacity) that vary according to another discrete time scale. We take a stochastic optimal control approach and formulate the corresponding optimal dynamic control problem as a stochastic dynamic program. Under general assumptions for the queueing system, we derive structural properties for the optimal dynamic control policy, establishing that the optimal policy can be obtained through a sequence of convex programs. We also derive fluid and diffusion approximations for the problem and propose analytical and computational approaches in these settings. Computational experiments demonstrate the benefits of our theoretical results over standard heuristics.