BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Rajesh Sundaresan

Rajesh Sundaresan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITNetworking and Internet Architecturemath.OCmath.PRComputer Science and Game Theorymath.STStatistics TheorySystems and ControlOther Computer Sciencephysics.soc-phPopulations and EvolutionQuantitative MethodsCryptography and SecurityDiscrete MathematicsDistributed, Parallel, and Cluster ComputingMachine Learning

Catalog footprint

What is connected

29works
17topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

29 published item(s)

preprint2023arXiv

A sufficient condition for the quasipotential to be the rate function of the invariant measure of countable-state mean-field interacting particle systems

This paper considers the family of invariant measures of Markovian mean-field interacting particle systems on a countably infinite state space and studies its large deviation asymptotics. The Freidlin-Wentzell quasipotential is the usual candidate rate function for the sequence of invariant measures indexed by the number of particles. The paper provides two counterexamples where the quasipotential is not the rate function. The quasipotential arises from finite horizon considerations. However there are certain barriers that cannot be surmounted easily in any finite time horizon, but these barriers can be crossed in the stationary regime. Consequently, the quasipotential is infinite at some points where the rate function is finite. After highlighting this phenomenon, the paper studies some sufficient conditions on a class of interacting particle systems under which one can continue to assert that the Freidlin-Wentzell quasipotential is indeed the rate function.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Learning to detect an oddball target with observations from an exponential family

The problem of detecting an odd arm from a set of K arms of a multi-armed bandit, with fixed confidence, is studied in a sequential decision-making scenario. Each arm's signal follows a distribution from a vector exponential family. All arms have the same parameters except the odd arm. The actual parameters of the odd and non-odd arms are unknown to the decision maker. Further, the decision maker incurs a cost for switching from one arm to another. This is a sequential decision making problem where the decision maker gets only a limited view of the true state of nature at each stage, but can control his view by choosing the arm to observe at each stage. Of interest are policies that satisfy a given constraint on the probability of false detection. An information-theoretic lower bound on the total cost (expected time for a reliable decision plus total switching cost) is first identified, and a variation on a sequential policy based on the generalised likelihood ratio statistic is then studied. Thanks to the vector exponential family assumption, the signal processing in this policy at each stage turns out to be very simple, in that the associated conjugate prior enables easy updates of the posterior distribution of the model parameters. The policy, with a suitable threshold, is shown to satisfy the given constraint on the probability of false detection. Further, the proposed policy is asymptotically optimal in terms of the total cost among all policies that satisfy the constraint on the probability of false detection.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Double-Auction Mechanisms for Resource Trading Markets

We consider a double-auction mechanism, which was recently proposed in the context of rate allocation in mobile data-offloading markets. Network operators (users) derive benefit from offloading their traffic to third party WiFi or femtocell networks (link-suppliers). Link-suppliers experience costs for the additional capacity that they provide. Users and link-suppliers (collectively referred to as agents) have their pay-offs and cost functions as private knowledge. A network-manager decomposes the problem into a network problem and agent problems. The surrogate pay-offs and cost functions are modulated by the agents' bids. Agents' payoffs and costs are then determined by the allocations and prices set by the network-manager. Under this design, so long as the agents do not anticipate the effect of their actions on the prices set by the network-manager (i.e., price-taking agents), a competitive equilibrium exists as a solution to the network and agent problems, and this equilibrium optimizes the sum utility of all agents. However, this design fails when the agents are all strategic (price-anticipating). Specifically, the presence of a strategic link-supplier drives the system to an undesirable equilibrium with zero participation resulting in an efficiency loss of 100%. This is in stark contrast to an earlier setting where the users alone are strategic but the link-supplier is not - the efficiency loss is known to be at most 34%. The paper then proposes a Stackelberg game modification where the efficiency loss can be characterized in terms of the link-supplier's cost function when the users' pay-off functions are linear. Specifically, when the link-supplier's cost function is quadratic, the worst case efficiency loss is 25%. Further, the loss in efficiency improves for polynomial cost functions of higher degree.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Large Time Behaviour and the Second Eigenvalue Problem for Finite State Mean-Field Interacting Particle Systems

This article examines large time behaviour of finite state mean-field interacting particle systems. Our first main result is a sharp estimate (in the exponential scale) on the time required for convergence of the empirical measure process of the $N$-particle system to its invariant measure; we show that when time is of the order of $\exp\{NΛ\}$ for a suitable constant $Λ\geq 0$, the process has mixed well and it is close to its invariant measure. We then obtain large-$N$ asymptotics of the second largest eigenvalue of the generator associated with the empirical measure process when it is reversible with respect to its invariant measure. We show that its absolute value scales as $\exp\{-NΛ\}$. The main tools used in establishing our results are the large deviation properties of the empirical measure process from its large-$N$ limit. As an application of the study of large time behaviour, we also show convergence of the empirical measure of the system of particles to a global minimum of a certain `entropy' function when particles are added over time in a controlled fashion. The controlled addition of particles is analogous to the cooling schedule associated with the search for a global minimum of a function using the simulated annealing algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic

We highlight the usefulness of city-scale agent-based simulators in studying various non-pharmaceutical interventions to manage an evolving pandemic. We ground our studies in the context of the COVID-19 pandemic and demonstrate the power of the simulator via several exploratory case studies in two metropolises, Bengaluru and Mumbai. Such tools become common-place in any city administration's tool kit in our march towards digital health.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai

The nation-wide lockdown starting 25 March 2020, aimed at suppressing the spread of the COVID-19 disease, was extended until 31 May 2020 in three subsequent orders by the Government of India. The extended lockdown has had significant social and economic consequences and `lockdown fatigue' has likely set in. Phased reopening began from 01 June 2020 onwards. Mumbai, one of the most crowded cities in the world, has witnessed both the largest number of cases and deaths among all the cities in India (41986 positive cases and 1368 deaths as of 02 June 2020). Many tough decisions are going to be made on re-opening in the next few days. In an earlier IISc-TIFR Report, we presented an agent-based city-scale simulator(ABCS) to model the progression and spread of the infection in large metropolises like Mumbai and Bengaluru. As discussed in IISc-TIFR Report 1, ABCS is a useful tool to model interactions of city residents at an individual level and to capture the impact of non-pharmaceutical interventions on the infection spread. In this report we focus on Mumbai. Using our simulator, we consider some plausible scenarios for phased emergence of Mumbai from the lockdown, 01 June 2020 onwards. These include phased and gradual opening of the industry, partial opening of public transportation (modelling of infection spread in suburban trains), impact of containment zones on controlling infections, and the role of compliance with respect to various intervention measures including use of masks, case isolation, home quarantine, etc. The main takeaway of our simulation results is that a phased opening of workplaces, say at a conservative attendance level of 20 to 33\%, is a good way to restart economic activity while ensuring that the city's medical care capacity remains adequate to handle the possible rise in the number of COVID-19 patients in June and July.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Detecting an Odd Restless Markov Arm with a Trembling Hand

In this paper, we consider a multi-armed bandit in which each arm is a Markov process evolving on a finite state space. The state space is common across the arms, and the arms are independent of each other. The transition probability matrix of one of the arms (the odd arm) is different from the common transition probability matrix of all the other arms. A decision maker, who knows these transition probability matrices, wishes to identify the odd arm as quickly as possible, while keeping the probability of decision error small. To do so, the decision maker collects observations from the arms by pulling the arms in a sequential manner, one at each discrete time instant. However, the decision maker has a trembling hand, and the arm that is actually pulled at any given time differs, with a small probability, from the one he intended to pull. The observation at any given time is the arm that is actually pulled and its current state. The Markov processes of the unobserved arms continue to evolve. This makes the arms restless. For the above setting, we derive the first known asymptotic lower bound on the expected time required to identify the odd arm, where the asymptotics is of vanishing error probability. The continued evolution of each arm adds a new dimension to the problem, leading to a family of Markov decision problems (MDPs) on a countable state space. We then stitch together certain parameterised solutions to these MDPs and obtain a sequence of strategies whose expected times to identify the odd arm come arbitrarily close to the lower bound in the regime of vanishing error probability. Prior works dealt with independent and identically distributed (across time) arms and rested Markov arms, whereas our work deals with restless Markov arms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sequential Multi-hypothesis Testing in Multi-armed Bandit Problems:An Approach for Asymptotic Optimality

We consider a multi-hypothesis testing problem involving a K-armed bandit. Each arm's signal follows a distribution from a vector exponential family. The actual parameters of the arms are unknown to the decision maker. The decision maker incurs a delay cost for delay until a decision and a switching cost whenever he switches from one arm to another. His goal is to minimise the overall cost until a decision is reached on the true hypothesis. Of interest are policies that satisfy a given constraint on the probability of false detection. This is a sequential decision making problem where the decision maker gets only a limited view of the true state of nature at each stage, but can control his view by choosing the arm to observe at each stage. An information-theoretic lower bound on the total cost (expected time for a reliable decision plus total switching cost) is first identified, and a variation on a sequential policy based on the generalised likelihood ratio statistic is then studied. Due to the vector exponential family assumption, the signal processing at each stage is simple; the associated conjugate prior distribution on the unknown model parameters enables easy updates of the posterior distribution. The proposed policy, with a suitable threshold for stopping, is shown to satisfy the given constraint on the probability of false detection. Under a continuous selection assumption, the policy is also shown to be asymptotically optimal in terms of the total cost among all policies that satisfy the constraint on the probability of false detection.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Survey of Algorithms for Separable Convex Optimization with Linear Ascending Constraints

The paper considers the minimization of a separable convex function subject to linear ascending constraints. The problem arises as the core optimization in several resource allocation scenarios, and is a special case of an optimization of a separable convex function over the bases of a polymatroid with a certain structure. The paper presents a survey of state-of-the-art algorithms that solve this optimization problem. The algorithms are applicable to the class of separable convex objective functions that need not be smooth or strictly convex. When the objective function is a so-called $d$-separable function, a simpler linear time algorithm solves the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Active Search with a Cost for Switching Actions

Active Sequential Hypothesis Testing (ASHT) is an extension of the classical sequential hypothesis testing problem with controls. Chernoff (Ann. Math. Statist., 1959) proposed a policy called Procedure A and showed its asymptotic optimality as the cost of sampling was driven to zero. In this paper we study a further extension where we introduce costs for switching of actions. We show that a modification of Chernoff's Procedure A, one that we call Sluggish Procedure A, is asymptotically optimal even with switching costs. The growth rate of the total cost, as the probability of false detection is driven to zero, and as a switching parameter of the Sluggish Procedure A is driven down to zero, is the same as that without switching costs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Learning to detect an oddball target

We consider the problem of detecting an odd process among a group of Poisson point processes, all having the same rate except the odd process. The actual rates of the odd and non-odd processes are unknown to the decision maker. We consider a time-slotted sequential detection scenario where, at the beginning of each slot, the decision maker can choose which process to observe during that time slot. We are interested in policies that satisfy a given constraint on the probability of false detection. We propose a generalised likelihood ratio based sequential policy which, via suitable thresholding, can be made to satisfy the given constraint on the probability of false detection. Further, we show that the proposed policy is asymptotically optimal in terms of the conditional expected stopping time among all policies that satisfy the constraint on the probability of false detection. The asymptotic is as the probability of false detection is driven to zero. We apply our results to a particular visual search experiment studied recently by neuroscientists. Our model suggests a neuronal dissimilarity index for the visual search task. The neuronal dissimilarity index, when applied to visual search data from the particular experiment, correlates strongly with the behavioural data. However, the new dissimilarity index performs worse than some previously proposed neuronal dissimilarity indices. We explain why this may be attributed to the experiment conditons.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Minimization Problems Based on Relative $α$-Entropy I: Forward Projection

Minimization problems with respect to a one-parameter family of generalized relative entropies are studied. These relative entropies, which we term relative $α$-entropies (denoted $\mathscr{I}_α$), arise as redundancies under mismatched compression when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the usual relative entropy (Kullback-Leibler divergence). Just like relative entropy, these relative $α$-entropies behave like squared Euclidean distance and satisfy the Pythagorean property. Minimizers of these relative $α$-entropies on closed and convex sets are shown to exist. Such minimizations generalize the maximum Rényi or Tsallis entropy principle. The minimizing probability distribution (termed forward $\mathscr{I}_α$-projection) for a linear family is shown to obey a power-law. Other results in connection with statistical inference, namely subspace transitivity and iterated projections, are also established. In a companion paper, a related minimization problem of interest in robust statistics that leads to a reverse $\mathscr{I}_α$-projection is studied.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Minimization Problems Based on Relative $α$-Entropy II: Reverse Projection

In part I of this two-part work, certain minimization problems based on a parametric family of relative entropies (denoted $\mathscr{I}_α$) were studied. Such minimizers were called forward $\mathscr{I}_α$-projections. Here, a complementary class of minimization problems leading to the so-called reverse $\mathscr{I}_α$-projections are studied. Reverse $\mathscr{I}_α$-projections, particularly on log-convex or power-law families, are of interest in robust estimation problems ($α>1$) and in constrained compression settings ($α<1$). Orthogonality of the power-law family with an associated linear family is first established and is then exploited to turn a reverse $\mathscr{I}_α$-projection into a forward $\mathscr{I}_α$-projection. The transformed problem is a simpler quasiconvex minimization subject to linear constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Neural dissimilarity indices that predict oddball detection in behaviour

Neuroscientists have recently shown that images that are difficult to find in visual search elicit similar patterns of firing across a population of recorded neurons. The $L^{1}$ distance between firing rate vectors associated with two images was strongly correlated with the inverse of decision time in behaviour. But why should decision times be correlated with $L^{1}$ distance? What is the decision-theoretic basis? In our decision theoretic formulation, we modeled visual search as an active sequential hypothesis testing problem with switching costs. Our analysis suggests an appropriate neuronal dissimilarity index which correlates equally strongly with the inverse of decision time as the $L^{1}$ distance. We also consider a number of other possibilities such as the relative entropy (Kullback-Leibler divergence) and the Chernoff entropy of the firing rate distributions. A more stringent test of equality of means, which would have provided a strong backing for our modeling fails for our proposed as well as the other already discussed dissimilarity indices. However, test statistics from the equality of means test, when used to rank the indices in terms of their ability to explain the observed results, places our proposed dissimilarity index at the top followed by relative entropy, Chernoff entropy and the $L^{1}$ indices. Computations of the different indices requires an estimate of the relative entropy between two Poisson point processes. An estimator is developed and is shown to have near unbiased performance for almost all operating regions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Asynchronous Gossip for Averaging and Spectral Ranking

We consider two variants of the classical gossip algorithm. The first variant is a version of asynchronous stochastic approximation. We highlight a fundamental difficulty associated with the classical asynchronous gossip scheme, viz., that it may not converge to a desired average, and suggest an alternative scheme based on reinforcement learning that has guaranteed convergence to the desired average. We then discuss a potential application to a wireless network setting with simultaneous link activation constraints. The second variant is a gossip algorithm for distributed computation of the Perron-Frobenius eigenvector of a nonnegative matrix. While the first variant draws upon a reinforcement learning algorithm for an average cost controlled Markov decision problem, the second variant draws upon a reinforcement learning algorithm for risk-sensitive control. We then discuss potential applications of the second variant to ranking schemes, reputation networks, and principal component analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Belief propagation for optimal edge cover in the random complete graph

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wästlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the $ζ(2)$ limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Relative $α$-Entropy Minimizers Subject to Linear Statistical Constraints

We study minimization of a parametric family of relative entropies, termed relative $α$-entropies (denoted $\mathscr{I}_α(P,Q)$). These arise as redundancies under mismatched compression when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the usual relative entropy (Kullback-Leibler divergence). Just like relative entropy, these relative $α$-entropies behave like squared Euclidean distance and satisfy the Pythagorean property. Minimization of $\mathscr{I}_α(P,Q)$ over the first argument on a set of probability distributions that constitutes a linear family is studied. Such a minimization generalizes the maximum Rényi or Tsallis entropy principle. The minimizing probability distribution (termed $\mathscr{I}_α$-projection) for a linear family is shown to have a power-law.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An asymptotically optimal push-pull method for multicasting over a random network

We consider allcast and multicast flow problems where either all of the nodes or only a subset of the nodes may be in session. Traffic from each node in the session has to be sent to every other node in the session. If the session does not consist of all the nodes, the remaining nodes act as relays. The nodes are connected by undirected links whose capacities are independent and identically distributed random variables. We study the asymptotics of the capacity region (with network coding) in the limit of a large number of nodes, and show that the normalized sum rate converges to a constant almost surely. We then provide a decentralized push-pull algorithm that asymptotically achieves this normalized sum rate without network coding.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Asymptotics of the Invariant Measure in Mean Field Models with Jumps

We consider the asymptotics of the invariant measure for the process of the empirical spatial distribution of $N$ coupled Markov chains in the limit of a large number of chains. Each chain reflects the stochastic evolution of one particle. The chains are coupled through the dependence of the transition rates on this spatial distribution of particles in the various states. Our model is a caricature for medium access interactions in wireless local area networks. It is also applicable to the study of spread of epidemics in a network. The limiting process satisfies a deterministic ordinary differential equation called the McKean-Vlasov equation. When this differential equation has a unique globally asymptotically stable equilibrium, the spatial distribution asymptotically concentrates on this equilibrium. More generally, its limit points are supported on a subset of the $ω$-limit sets of the McKean-Vlasov equation. Using a control-theoretic approach, we examine the question of large deviations of the invariant measure from this limit.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Regulation of off-network pricing in a nonneutral network

Representatives of several Internet service providers (ISPs) have expressed their wish to see a substantial change in the pricing policies of the Internet. In particular, they would like to see content providers (CPs) pay for use of the network, given the large amount of resources they use. This would be in clear violation of the "network neutrality" principle that had characterized the development of the wireline Internet. Our first goal in this paper is to propose and study possible ways of implementing such payments and of regulating their amount. We introduce a model that includes the users' behavior, the utilities of the ISP and of the CPs, and the monetary flow that involves the content users, the ISP and CP, and in particular, the CP's revenues from advertisements. We consider various game models and study the resulting equilibria; they are all combinations of a noncooperative game (in which the ISPs and CPs determine how much they will charge the users) with a "cooperative" one on how the CP and the ISP share the payments. We include in our model a possible asymmetric weighting parameter (that varies between zero to one). We also study equilibria that arise when one of the CPs colludes with the ISP. We also study two dynamic game models and study the convergence of prices to the equilibrium values.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Neighbor Oblivious and Finite-State Algorithms for Circumventing Local Minima in Geographic Forwarding

We propose distributed link reversal algorithms to circumvent communication voids in geographic routing. We also solve the attendant problem of integer overflow in these algorithms. These are achieved in two steps. First, we derive partial and full link reversal algorithms that do not require one-hop neighbor information, and convert a destination-disoriented directed acyclic graph (DAG) to a destination-oriented DAG. We embed these algorithms in the framework of Gafni and Bertsekas ("Distributed algorithms for generating loop-free routes in networks with frequently changing topology", 1981) in order to establish their termination properties. We also analyze certain key properties exhibited by our neighbor oblivious link reversal algorithms, e.g., for any two neighbors, their t-states are always consecutive integers, and for any node, its t-state size is upper bounded by log(N). In the second step, we resolve the integer overflow problem by analytically deriving one-bit full link reversal and two-bit partial link reversal versions of our neighbor oblivious link reversal algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Combined Base Station Association and Power Control in Multi-channel Cellular Networks

A combined base station association and power control problem is studied for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one cell (i.e., base station). A distributed association and power update algorithm is proposed and shown to converge to a Nash equilibrium of a noncooperative game. We consider network models with discrete mobiles (yielding an atomic congestion game), as well as a continuum of mobiles (yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. It is shown that these mechanisms can be implemented in a distributed fashion.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Further Results on Geometric Properties of a Family of Relative Entropies

This paper extends some geometric properties of a one-parameter family of relative entropies. These arise as redundancies when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the Kullback-Leibler divergence. They satisfy the Pythagorean property and behave like squared distances. This property, which was known for finite alphabet spaces, is now extended for general measure spaces. Existence of projections onto convex and certain closed sets is also established. Our results may have applications in the Rényi entropy maximization rule of statistical physics.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal Forwarding in Delay Tolerant Networks with Multiple Destinations

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., a deterministic fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed loop policy.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Spatial SINR Games of Base Station Placement and Mobile Association

We study the question of determining locations of base stations that may belong to the same or to competing service providers. We take into account the impact of these decisions on the behavior of intelligent mobile terminals who can connect to the base station that offers the best utility. The signal to interference and noise ratio is used as the quantity that determines the association. We first study the SINR association-game: we determine the cells corresponding to each base stations, i.e., the locations at which mobile terminals prefer to connect to a given base station than to others. We make some surprising observations: (i) displacing a base station a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction; (ii) A cell corresponding to a BS may be the union of disconnected sub-cells. We then study the hierarchical equilibrium in the combined BS location and mobile association problem: we determine where to locate the BSs so as to maximize the revenues obtained at the induced SINR mobile association game. We consider the cases of single frequency band and two frequency bands of operation. Finally, we also consider hierarchical equilibria in two frequency systems with successive interference cancellation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Guessing Revisited: A Large Deviations Approach

The problem of guessing a random string is revisited. A close relation between guessing and compression is first established. Then it is shown that if the sequence of distributions of the information spectrum satisfies the large deviation property with a certain rate function, then the limiting guessing exponent exists and is a scalar multiple of the Legendre-Fenchel dual of the rate function. Other sufficient conditions related to certain continuity properties of the information spectrum are briefly discussed. This approach highlights the importance of the information spectrum in determining the limiting guessing exponent. All known prior results are then re-derived as example applications of our unifying approach.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Shannon Cipher System with a Guessing Wiretapper: General Sources

The Shannon cipher system is studied in the context of general sources using a notion of computational secrecy introduced by Merhav & Arikan. Bounds are derived on limiting exponents of guessing moments for general sources. The bounds are shown to be tight for iid, Markov, and unifilar sources, thus recovering some known results. A close relationship between error exponents and correct decoding exponents for fixed rate source compression on the one hand and exponents for guessing moments on the other hand is established.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Guessing based on length functions

A guessing wiretapper's performance on a Shannon cipher system is analyzed for a source with memory. Close relationships between guessing functions and length functions are first established. Subsequently, asymptotically optimal encryption and attack strategies are identified and their performances analyzed for sources with memory. The performance metrics are exponents of guessing moments and probability of large deviations. The metrics are then characterized for unifilar sources. Universal asymptotically optimal encryption and attack strategies are also identified for unifilar sources. Guessing in the increasing order of Lempel-Ziv coding lengths is proposed for finite-state sources, and shown to be asymptotically optimal. Finally, competitive optimality properties of guessing in the increasing order of description lengths and Lempel-Ziv coding lengths are demonstrated.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Separable convex optimization problems with linear ascending constraints

Separable convex optimization problems with linear ascending inequality and equality constraints are addressed in this paper. Under an ordering condition on the slopes of the functions at the origin, an algorithm that determines the optimum point in a finite number of steps is described. The optimum value is shown to be monotone with respect to a partial order on the constraint parameters. Moreover, the optimum value is convex with respect to these parameters. Examples motivated by optimizations for communication systems are used to illustrate the algorithm.

0 citations0 reviewsNo code linkedOpen access