Scientific attention is unevenly distributed, creating inequities in recognition and distorting access to opportunities. Using citations as a proxy, we quantify disparities in attention by gender and institutional prestige. We find that women receive systematically fewer citations than men, and that attention is increasingly concentrated among authors from elite institutions -- patterns not fully explained by underrepresentation alone. To explain these dynamics, we introduce a model of citation network growth that incorporates homophily (tendency to cite similar authors), preferential attachment (favoring highly cited authors) and group size (underrepresentation). The model shows that disparities arise not only from group size imbalances but also from cumulative advantage amplifying biased citation preferences. Importantly, increasing representation alone is often insufficient to reduce disparities. Effective strategies should also include reducing homophily, amplifying the visibility of underrepresented groups, and supporting equitable integration of newcomers. Our findings highlight the challenges of mitigating inequities in asymmetric networks like citations, where recognition flows in one direction. By making visible the mechanisms through which attention is distributed, we contribute to efforts toward a more responsible web of science that is fairer, more transparent, and more inclusive, and that better sustains innovation and knowledge production.

This article designs a blockchain protocol to mitigate the spread of misinformation in online social networks. The blockchain protocol processes social media postings as transactions, with misinformation being treated as double-spend attacks. The probability and duration for a double-spend attack to succeed within the blockchain protocol are used to compute the misinformation propagation time distribution. Our findings indicate that the rate of misinformation propagation in blockchain-based online social networks is inversely correlated with the fraction of honest miners who reject double-spend attacks. To further analyze the dynamics of misinformation propagation, we employ a susceptible–infectious–recovered (SIR) model combined with preferential attachment in a multicommunity network, which accounts for homophily and community structure in social networks. Numerical experiments using parameters estimated from real-world Twitter hashtag datasets show that the proposed blockchain protocol can reduce the number of users exposed to misinformation by delaying its propagation.

This article proposes a method to detect change points in dynamic social networks using Fréchet statistics. We address two main questions: 1) what metric can quantify the distances between graph Laplacians in a dynamic network and enable efficient computation, and 2) how can the Fréchet statistics be extended to detect multiple change points while maintaining the significance level of the hypothesis test? Our solution defines a metric space for graph Laplacians using the log-Euclidean metric, enabling a closed-form formula for Fréchet mean and variance. We present a framework for change point detection using Fréchet statistics and extend it to multiple change points with binary segmentation. The proposed algorithm uses incremental computation for Fréchet mean and variance to improve efficiency and is validated on simulated and four real-world datasets, namely, the UCI message dataset, the SFHH interaction dataset, the stack overflow Q&A dataset, and the Enron email dataset.

This article introduces a novel mutual information-based measure to assess the glass ceiling effect in preferential attachment networks, which advances the analysis of inequalities in attributed networks. Using Shannon entropy and generalizing to Rényi entropy, our measure evaluates the conditional probability distributions of node attributes given the node degrees of adjacent nodes, which offers a more nuanced understanding of inequality compared to traditional methods that emphasize node degree distributions and degree assortativity alone. To evaluate the efficacy of the proposed measure, we evaluate it using an analytical structural inequality model as well as historical publication data. Results show that our mutual information measure aligns well with both the theoretical model and empirical data, underscoring its reliability as a robust approach for capturing inequalities in attributed networks. Moreover, we introduce a novel stochastic optimization algorithm that utilizes a parameterized conditional logit model for edge addition. Our algorithm is shown to outperform the baseline uniform distribution based approach in mitigating the glass ceiling effect. By strategically recommending links based on this algorithm, we can effectively hinder the glass ceiling effect within networks.

Consider a target being tracked by a cognitive radar network. If the target can intercept noisy radar emissions, how can it detect coordination in the network? By ‘coordination’ we mean that the radar emissions satisfy Pareto optimality with respect to multi-objective optimization over the objective functions of each radar and a constraint on total network power output. This paper provides a novel inverse multi-objective optimization approach for statistically detecting Pareto optimal (’coordinating’) behavior, from a finite dataset of noisy radar emissions. Specifically, we develop necessary and sufficient conditions for radar network emissions to be consistent with multi-objective optimization (coordination), and we provide a statistical detector with theoretical guarantees for determining this consistency when radar emissions are observed in noise. We also provide numerical simulations which validate our approach. Note that while we make use of the specific framework of a radar network coordination problem, our results apply more generally to the field of inverse multi-objective optimization.

In this paper, we exploit the spiked covariance structure of the clutter plus noise covariance matrix for adaptive radar signal processing. Using state-of-the-art techniques from mathematical finance and high dimensional statistics we propose a non-linear shrinkage-based rotation invariant spiked covariance matrix estimator. We compare the proposed estimator with Rank Constrained Maximum Likelihood (RCML)-Expected Likelihood (EL) covariance estimator using the Challenge dataset generated from RFView. We demonstrate that the computation-time for the proposed estimator is less than the RCML-EL estimator with identical Signal to Clutter plus Noise (SCNR) performance for the Challenge dataset. We derive the lower bound and upper bound for the normalized SCNR and empirically show that RCML-EL and the proposed estimator perform within these derived bounds for the Challenge dataset. We state the convergence for the spiked eigenvalues of the estimator.

This paper considers adaptive radar electronic counter-counter measures (ECCM) to mitigate ECM by an adversarial jammer. Our ECCM approach models the jammer-radar interaction as a Principal Agent Problem (PAP), a popular economics framework for interaction between two entities with an information imbalance. In our setup, the radar does not know the jammer’s utility. Instead, the radar learns the jammer’s utility adaptively over time using inverse reinforcement learning. The radar’s adaptive ECCM objective is two-fold (1) maximize its utility by solving the PAP, and (2) estimate the jammer’s utility by observing its response. Our adaptive ECCM scheme uses deep ideas from revealed preference in micro-economics and principal agent problem in contract theory. Our numerical results show that, over time, our adaptive ECCM both identifies and mitigates the jammer’s utility.

Suppose L simultaneous independent stochastic systems generate observations, where the observations from each system depend on the underlying parameter of that system. The observations are unlabeled (anonymized), in the sense that an analyst does not know which observation came from which stochastic system. How can the analyst estimate the underlying parameters of the L systems? Since the anonymized observations at each time are an unordered set of L measurements (rather than a vector), classical stochastic gradient algorithms cannot be directly used. By using symmetric polynomials, we formulate a symmetric measurement equation that maps the observation set to a unique vector. We then construct an adaptive filtering algorithm that yields a statistically consistent estimate of the underlying parameters.

Consider a target being tracked by a cognitive radar network. If the target can intercept some radar network emissions, how can it detect coordination among the radars? By 'coordination' we mean that the radar emissions satisfy Pareto optimality with respect to multiobjective optimization over each radar's utility. This paper provides a novel multi-objective inverse reinforcement learning approach which allows for both detection of such Pareto optimal ('coordinating') behavior and subsequent reconstruction of each radar's utility function, given a finite dataset of radar network emissions. The method for accomplishing this is derived from the micro-economic setting of revealed preferences, and also applies to more general problems of inverse detection and learning of multi-objective optimizing systems.

This paper presents an inverse reinforcement learning (IRL) framework for Bayesian stopping time problems. By observing the actions of a Bayesian decision maker, we provide a necessary and sufficient condition to identify if these actions are consistent with optimizing a cost function. In a Bayesian (partially observed) setting, the inverse learner can at best identify optimality wrt the observed strategies. Our IRL algorithm identifies optimality and then constructs set-valued estimates of the cost function. To achieve this IRL objective, we use novel ideas from Bayesian revealed preferences stemming from microeconomics. We illustrate the proposed IRL scheme using two important examples of stopping time problems, namely, sequential hypothesis testing and Bayesian search. As a real-world example, we illustrate using a YouTube dataset comprising metadata from 190000 videos how the proposed IRL method predicts user engagement in online multimedia platforms with high accuracy. Finally, for finite datasets, we propose an IRL detection algorithm and give finite sample bounds on its error probabilities.

We study how a cognitive radar can mask (hide) its cognitive ability from an adversarial jamming device. Specifically, if the radar optimally adapts its waveform based on adversarial target maneuvers (probes), how should the radar choose its waveform parameters (response) so that its utility function cannot be recovered by the adversary? This paper abstracts the radar’s cognition masking problem in terms of the spectra (eigenvalues) of the state and observation noise covariance matrices, and embeds the algebraic Riccati equation into an economics-based utility maximization setup. Given an observed sequence of radar responses, the adversary tests for utility maximization behavior of the radar and estimates its utility function that rationalizes the radar’s responses. In turn, the radar deliberately chooses sub-optimal responses so that its utility function almost fails the utility maximization test, and hence, its cognitive ability is masked from the adversary. We illustrate the performance of our cognition masking scheme via simple numerical examples. Our approach in this paper is based on revealed preference theory in microeconomics for identifying rationality.

This article deals with the modeling and estimation of the sociological phenomena called echo chambers and segregation in social networks. Specifically, we present a novel community-based graph model that represents the emergence of segregated echo chambers as a Markov bridge (MB) process. An MB is a 1-D Markov random field that facilitates modeling the formation and disassociation of communities at deterministic times, which is important in social networks with known timed events. We justify the proposed model with real-world examples and examine its performance on a recent Twitter dataset. We provide a model parameter estimation algorithm based on maximum likelihood and a Bayesian filtering algorithm for recursively estimating the level of segregation using noisy samples obtained from the network. Numerical results indicate that the proposed filtering algorithm outperforms the conventional hidden Markov modeling in terms of the mean-squared error. The proposed filtering method is useful in computational social science where data-driven estimation of the level of segregation from noisy data is required.

In behavioral economics, anticipatory agents make decisions by taking into account the probability of future decisions (plans). We consider the interaction between anticipatory agents and statistical detection. A sensing device records the decisions of an anticipatory agent. Given these decisions, how can the sensing device achieve quickest detection of a change in the anticipatory system? From a decision theoretic point of view, anticipatory models are time inconsistent meaning that Bellman’s principle of optimality does not hold. The appropriate formalism is the subgame Nash equilibrium. We show that the interaction between anticipatory agents and sequential quickest detection results in unusual (nonconvex) structure of the quickest change detection policy. Our methodology yields a useful framework for anticipatory human decision makers interacting with sequential detectors in cyber-physical systems.

This paper deals with the modeling and estimation of the sociological phenomena called segregation in social networks. Specifically, we present a novel community-based graph model that represent segregation as a Markov bridge process. A Markov bridge is a one-dimensional Markov random field that facilitates modeling the formation and disassociation of communities at deterministic times which is important in social networks with known timed events. Based on the proposed model, we provide Bayesian filtering algorithms for recursively estimating the level of segregation using noisy samples obtained from the graph. Numerical results indicate that the proposed filtering algorithm outperforms the conventional hidden Markov modeling in terms of the mean-squared error. The proposed filtering method is useful in computational social science where data-driven estimation of the level of segregation from noisy data is required.

Inverse reinforcement learning (IRL) aims to estimate the reward function of optimizing agents by observing their response (estimates or actions). This paper considers IRL when noisy estimates of the gradient of a reward function generated by multiple stochastic gradient agents are observed. We present a generalized Langevin dynamics algorithm to estimate the reward function $R(\theta)$; specifically, the resulting Langevin algorithm asymptotically generates samples from the distribution proportional to $\exp(R(\theta))$. The proposed adaptive IRL algorithms use kernel-based passive learning schemes. We also construct multi-kernel passive Langevin algorithms for IRL which are suitable for high dimensional data. The performance of the proposed IRL algorithms are illustrated on examples in adaptive Bayesian learning, logistic regression (high dimensional problem) and constrained Markov decision processes. We prove weak convergence of the proposed IRL algorithms using martingale averaging methods. We also analyze the tracking performance of the IRL algorithms in non-stationary environments where the utility function $R(\theta)$ has a hyper-parameter that jump changes over time as a slow Markov chain which is not known to the inverse learner. In this case, martingale averaging yields a Markov switched diffusion limit as the asymptotic behavior of the IRL algorithm.

The paper presents risk-neutral and risk-averse caching policies that can be deployed in a femtocell network with limited storage capacity to reduce the time delay of servicing content requests. The caching policies use a forecasting algorithm to estimate the cumulative distribution function of content requests based on the content features. Given the cumulative distribution function, a mixed-integer linear program is used to compute where to cache content in the femtocell network. The caching policies account for the uncertainty associated with estimating the content requests using the coherent Conditional Value-at-Risk (CVaR) measure. For a large number of content, a risk-neutral caching policy is constructed that accounts for both the content features and routing protocol that only requires the evaluation of a unimodular linear program. Using data from YouTube (comprising 25,000 videos) and the NS-3 simulator, the caching policies reduce the delay of retrieving content in femtocell networks compared with industry standard caching policies. Specifically, a 6 percent reduction in delay is achieved by accounting for the uncertainty, and a 60 percent reduction in delay is achieved if both the uncertainty and femtocell routing protocol are accounted for compared to the risk-neutral caching policy that neglects the routing protocol.

This article considers the problem of estimating a power-law degree distribution of an undirected network using sampled data. Although power-law degree distributions are ubiquitous in nature, the widely used parametric methods for estimating them (e.g., linear regression on double-logarithmic axes and maximum likelihood estimation with uniformly sampled nodes) suffer from the large variance introduced by the lack of data-points from the tail portion of the power-law degree distribution. As a solution, we present a novel maximum likelihood estimation approach that exploits the friendship paradox to sample more efficiently from the tail of the degree distribution. We analytically show that the proposed method results in a smaller bias, variance and a Cramèr–Rao lower bound compared to the vanilla maximum likelihood estimate obtained with uniformly sampled nodes (which is the most commonly used method in literature). Detailed numerical and empirical results are presented to illustrate the performance of the proposed method under different conditions and how it compares with alternative methods. We also show that the proposed method and its desirable properties (i.e., smaller bias, variance, and Cramèr–Rao lower bound compared to vanilla method based on uniform samples) extend to parametric degree distributions other than the power-law such as exponential degree distributions as well. All the numerical and empirical results are reproducible and the code is publicly available on Github.

This paper deals with randomized polling of a social network. In the case of forecasting the outcome of an election between two candidates A and B, classical intent polling asks randomly sampled individuals: who will you vote for? Expectation polling asks: who do you think will win? In this paper, we propose a novel neighborhood expectation polling (NEP) strategy that asks randomly sampled individuals: what is your estimate of the fraction of votes for A? Therefore, in NEP, sampled individuals will naturally look at their neighbors (defined by the underlying social network graph) when answering this question. Hence, the mean squared error (MSE) of NEP methods rely on selecting the optimal set of samples from the network. To this end, we propose two NEP algorithms for the following cases: (i) the social network graph is not known but, random walks (sequential exploration) can be performed on the graph, and (ii) the social network graph is unknown but, uniformly sampled nodes from the network are available. For both cases, algorithms based on a graph theoretic consequence called friendship paradox are proposed. Theoretical results on the dependence of the MSE of the algorithms on the properties of the network are established. Numerical results on real and synthetic data sets are provided to illustrate the performance of the algorithms.

This paper considers a novel formulation of inverse reinforcement learning with behavioral economics constraints to address inverse sequential hypothesis testing (SHT) in Bayesian agents. The aim is to estimate the detection costs by observing the actions of the sequential hypothesis detector. Our methodology involves Bayesian revealed preferences from microeconomics and rational inattention from behavioral economics. First, we show that Bayesian agents optimally performing SHT are rationally inattentive utility maximizers. Using established results in Bayesian revealed preferences, we outline a feasibility test for a data analyst observing the Bayesian agents to estimate their detection costs. Numerical examples illustrate the performance of the inverse sequential hypothesis testing algorithm.

We consider fixed-interval smoothing problems for counter-adversarial autonomous systems. An adversary deploys an autonomous filtering and control system that i) measures our current state via a noisy sensor, ii) computes a posterior estimate (belief) and iii) takes an action that we can observe. Based on such observed actions and our knowledge of our state sequence, we aim to estimate the adversary's past and current beliefs - this forms a foundation for predicting, and counteracting against, future actions. We derive the optimal smoother for the adversary's beliefs (we treat the problem in a Bayesian framework). Moreover, we demonstrate how the smoother can be computed for discrete systems even though the corresponding backward variables do not admit a finite-dimensional characterization. Finally, we illustrate our results in numerical simulations.

Can the parameters of a hidden Markov model (HMM) be estimated from a single sweep through the observations – and additionally, without being trapped at a local optimum in the likelihood surface? That is the premise of recent method of moments algorithms devised for HMMs. In these, correlations between consecutive pair- or triplet-wise observations are empirically estimated and used to compute estimates of the HMM parameters. Albeit computationally very attractive, the main drawback is that by restricting to only low-order correlations in the data, information is being neglected which results in a loss of accuracy (compared to standard maximum likelihood schemes). In this paper, we propose extending these methods (both pair- and triplet-based) by also including non-consecutive correlations in a way which does not significantly increase the computational cost (which scales linearly with the number of additional lags included). We prove strong consistency of the new methods, and demonstrate an improved performance in numerical experiments on both synthetic and real-world financial time-series datasets.

We consider a novel application of inverse reinforcement learning with behavioral economics constraints to model, learn and predict the commenting behavior of YouTube viewers. Each group of users is modeled as a rationally inattentive Bayesian agent which solves a contextual bandit problem. Our methodology integrates three key components. First, to identify distinct commenting patterns, we use deep embedded clustering to estimate framing information (essential extrinsic features) that clusters users into distinct groups. Second, we present an inverse reinforcement learning algorithm that uses Bayesian revealed preferences to test for rationality: does there exist a utility function that rationalizes the given data, and if yes, can it be used to predict commenting behavior? Finally, we impose behavioral economics constraints stemming from rational inattention to characterize the attention span of groups of users. The test imposes a Renyi mutual information cost constraint which impacts how the agent can select attention strategies to maximize their expected utility. After a careful analysis of a massive YouTube dataset, our surprising result is that in most YouTube user groups, the commenting behavior is consistent with optimizing a Bayesian utility with rationally inattentive constraints. The paper also highlights how the rational inattention model can accurately predict commenting behavior. The massive YouTube dataset and analysis used in this paper are available on GitHub and completely reproducible.

This paper provides conditions on the observation probability distribution in Bayesian localization and optimal filtering so that the conditional mean estimate satisfies convex stochastic dominance. Convex dominance allows us to compare the unconditional mean square error between two optimal Bayesian state estimators over arbitrary time horizons instead of using brute force Monte-Carlo computations. The proof uses two key ideas from microeconomics, namely, integral precision dominance and aggregation of single crossing. The convex dominance result is then used to give sufficient conditions so that the optimal policy of a controlled sensing two-state partially observed Markov decision process (POMDP) is lower bounded by a myopic policy. Numerical examples are presented where the Shannon capacity of the observation distribution using one sensor dominates that of another, and convex dominance holds but Blackwell dominance does not hold. These illustrate the usefulness of the main result in localization, filtering and controlled sensing applications.

The proliferation of connected cars globally has the potential to produce torrents of Big Data that will enable improvements in driver safety, new location based services, improvements in vehicle quality, and optimized vehicle designs. One aspect of connected car data involves driving behavior data and its use for Usage Based Insurance (UBI). UBI has become one of the most widely used applications of driving behavior data. Currently, the transmission and processing of high frequency driving behavior data from the connected car to the cloud is limited by wireless data costs and in-vehicle hardware complexity. To alleviate these issues, we detail the development of a machine learning framework utilizing a kinematic classification methodology applied to down sampled time series vehicle data sets for accurate imputation of driving behavior events in UBI applications. The down-sampled data, consisting of 5 second frames with data fields of timestamp, vehicle speed, and vehicle acceleration is classified into unique kinematic clusters to standardize any driving behavior data distributions. Subsequently, machine learning is used to impute harsh driving events for each 5 second frame in select kinematic clusters. This novel machine learning methodology reduced data set sizes by 75%, utilized a limited set of five attributes, and achieved an average precision and recall of 84.5% and 63.5% for two distinct connected car data sets with 1/5 Hz down-sampled data.

Image processing and machine learning have become valuable tools for predictive maintenance applications for a wide variety of industrial and commercial components. We present a novel light transmission image processing methodology utilizing statistical distance algorithms (Wasserstein distance (WD), Kolmogorov-Smirnov statistic (K-S)) for physical attribute correlation combined with Bayesian linear regression to estimate wear level and lifetime prediction for air filters. Robustness of this machine learning algorithm was evaluated using spatial block bootstrapping to generate synthetic training data to estimate the 95% prediction interval for air filter lifetime. Validation of this lifetime prediction was performed using imaging measurements on a test air filter, which showed good agreement with the machine learning model. The proposed machine learning based image analytics framework effectively enables robust predictions of component wear for predictive maintenance.

This paper studies distributed formation of femto-clouds in a UMTS LTE network. Femtocell access points (FAPs) are equipped with computational resources. They share their resources with neighboring FAPs and form local clouds with the aim to avoid the remote cloud costs while improving the user quality of experience (QoE) in terms of handling latency. In exchange for sharing their excess resources, FAPs receive monetary incentives proportional to their contribution in performing computational tasks in the femto-cloud. The resource sharing problem is formulated as an optimization problem and a myopic procedure is presented that enables FAPs to collaboratively find its solution in a distributed fashion. In such an optimal femto-cloud structure, the local computational resources of FAPs are maximally exploited, yet the incentive earned by each femto-cloud is divided among the FAPs in a fair fashion. Numerical simulations using NS-3 verify superior QoE of users as well as higher incentives provided to FAP owners as compared with alternative heuristic schemes. Numerical results also show that the grand femto-cloud-the largest collaborative cloud comprising of all FAPs-is not always the optimal structure.

This paper deals with the problem of information fusion for state/ parameter estimation in social networks. The information consists of the sentiment of the opinions expressed by people. The average sentiment of the opinions expressed by people constitutes a noisy observation of an unknown state. A controller seeks to estimate the state by controlling the dynamics of sampling that minimizes an objective function comprising of state estimation error and the cost of acquiring sentiments. The stochastic control problem is formulated as a partially observed Markov decision process (POMDP), and sufficient conditions under which a myopic policy forms an upperbound to the optimal policy of the POMDP are provided. The myopic policy minimizes the immediate costs while ignoring the expected costs incurred over time, and is computationally inexpensive for large state spaces. Finally, the performance of the proposed myopic policy is evaluated for POMDP formulation whose parameters are computed from real-data set obtained from Twitter.

This paper considers the problem of detecting changes in utility maximizing behaviour of agents in online social media. Such changes in utility maximizing behaviour in online social media occur due to the effect of marketing, advertising, or changes in ground truth. In contrast to traditional signal processing techniques, our approach is data-centric. We use the framework of revealed preference to detect the unknown time point (change point) at which the utility function changed. We derive necessary and sufficient conditions for detecting the change point. In addition, we provide an algorithm to recover the utility function before and after the change point. The results developed are illustrated on the Yahoo! Tech Buzz dataset. From the dataset, we obtain the following useful insights: First, the changes in ground truth affecting the utility of the agent can be detected by utility maximization behaviour in online search. Second, the recovered utility functions satisfy the single crossing property indicating strategic substitute behaviour in online search.

This paper considers a number of related inverse filtering problems for hidden Markov models (HMMs). In particular, given a sequence of state posteriors and the system dynamics; i) estimate the corresponding sequence of observations, ii) estimate the observation likelihoods, and iii) jointly estimate the observation likelihoods and the observation sequence. We show how to avoid a computationally expensive mixed integer linear program (MILP) by exploiting the algebraic structure of the HMM filter using simple linear algebra operations, and provide conditions for when the quantities can be uniquely reconstructed. We also propose a solution to the more general case where the posteriors are noisily observed. Finally, the proposed inverse filtering algorithms are evaluated on real-world polysomnographic data used for automatic sleep segmentation.

We consider estimating the transition probability matrix of a finite-state finite-observation alphabet hidden Markov model with known observation probabilities. We propose a two-step algorithm: a method of moments estimator (formulated as a convex optimization problem) followed by a single iteration of a Newton-Raphson maximum-likelihood estimator. The two-fold contribution of this letter is, first, to theoretically show that the proposed estimator is consistent and asymptotically efficient, and second, to numerically show that the method is computationally less demanding than conventional methods-in particular for large datasets.

YouTube, with millions of content creators, has become the preferred destination for viewing videos online. Through the Partner program, YouTube allows content creators to monetize their popular videos. Of significant importance for content creators is which meta-level features (title, tag, thumbnail, and description) are most sensitive for promoting video popularity. The popularity of videos also depends on the social dynamics, i.e., the interaction of the content creators (or channels) with YouTube users. Using real-world data consisting of about 6 million videos spread over 25 thousand channels, we empirically examine the sensitivity of YouTube meta-level features and social dynamics. The key meta-level features that impact the view counts of a video include: first day view count, number of subscribers, contrast of the video thumbnail, Google hits, number of keywords, video category, title length, and number of upper-case letters in the title, respectively, and illustrate that these meta-level features can be used to estimate the popularity of a video. In addition, optimizing the meta-level features after a video is posted increases the popularity of videos. In the context of social dynamics, we discover that there is a causal relationship between views to a channel and the associated number of subscribers. Additionally, insights into the effects of scheduling and video playthrough in a channel are also provided. Our findings provide a useful understanding of user engagement in YouTube.

This paper studies formation of local femto-clouds in a UMTS LTE network via a cooperative game-theoretic formulation. Femtocell access points (FAPs) equipped with processing power form collaborative coalitions, namely, femto-clouds, with neighboring FAPs and share their computational resources in exchange for monetary incentives. Femto-clouds are formed with the aim to avoid the remote cloud costs while improving the quality of experience (QoE) of users in terms of handling latency. The core of the formulated game represents an optimal structure for femto-clouds such that the computational resources of FAPs are maximally exploited, yet the incentive earned by each femto- cloud is divided among the FAPs in a fair fashion. Numerical simulations using NS3 verify superior QoE of users and higher incentives to FAP owners as compared with alternative schemes.

This work considers the problem of optimal liquidation of a single risky asset portfolio as a denumerable Markov Decision Processes (MDP) control problem. The model is defined over discrete time, state, and action sets, and the optimal liquidation strategy is the solution to Bellman's equation. It is shown that the optimal strategy is monotone in the number of shares owned, the time remaining to liquidation, and the price of the underlying asset. This structural result can be exploited to estimate the optimal policy via the simultaneous perturbation stochastic approximation (SPSA) algorithm. Therefore, the optimal policy can be estimated without knowledge of the parameters of the model.

In this paper, a novel mode-driven switching state space approach is proposed for the joint tracking and recognition of gestural commands. Gestures are modeled as spatio-temporal patterns comprised of syntactic sub-units called gesturelets. These gesturelets are directional vectors modulating a switching state space model. Stochastic context-free grammars (SCFG) are used as generative models for command gestures which impart a scale-invariant modeling framework. This translates into a method that is user-independent and robust to the signing variation between and among users. In addition to the modeling framework, we also design a library of useful gestural patterns that cannot be represented by regular grammars (hidden Markov models). Our approach combines tracking and recognition in a single framework and is able to deal with a high perplexity dataset. We demonstrate the effectiveness of our approach by comparing SCFG models with HMM models on synthetic gesture trajectories.

This paper considers online reputation and polling systems where individuals make recommendations based on their private observations and recommendations of friends. Such interaction of individuals and their social influence is modeled as social learning on a directed acyclic graph. Data incest (misinformation propagation) occurs due to unintentional reuse of identical actions in the formation of public belief in social learning; the information gathered by each agent is mistakenly considered to be independent. This results in overconfidence and bias in estimates of the state. Necessary and sufficient conditions are given on the structure of information exchange graph to mitigate data incest. Incest removal algorithms are presented. Experimental results on human subjects are presented to illustrate the effect of social influence and data incest on decision-making. These experimental results indicate that social learning protocols require careful design to handle and mitigate data incest. The incest removal algorithms are illustrated in an expectation polling system where participants in a poll respond with a summary of their friends' beliefs. Finally, the principle of revealed preferences arising in microeconomics theory is used to parse Twitter datasets to determine if social sensors are utility maximizers and then determine their utility functions.

This paper considers models and algorithms for interactive sensing in social networks in which individuals act as sensors and the information exchange between individuals is exploited to optimize sensing. Social learning is used to model the interaction between individuals that aim to estimate an underlying state of nature. In this context, the following questions are addressed: how can self-interested agents that interact via social learning achieve a tradeoff between individual privacy and reputation of the social group? How can protocols be designed to prevent data incest in online reputation blogs where individuals make recommendations? How can sensing by individuals that interact with each other be used by a global decision maker to detect changes in the underlying state of nature? When individual agents possess limited sensing, computation, and communication capabilities, can a network of agents achieve sophisticated global behavior? Social and game-theoretic learning are natural settings for addressing these questions. This article presents an overview, insights, and discussion of social learning models in the context of data incest propagation, change detection, and coordination of decision-making.

This paper considers a Markov-modulated duplication-deletion random graph where at each time instant, one node can either join or leave the network; the probabilities of joining or leaving evolve according to the realization of a finite state Markov chain. Two results are presented. First, motivated by social network applications, the asymptotic behavior of the degree distribution is analyzed. Second, a stochastic approximation algorithm is presented to track empirical degree distribution as it evolves over time. The tracking performance of the algorithm is analyzed in terms of mean square error and a functional central limit theorem is presented for the asymptotic tracking error. Also, a Hilbert-space-valued stochastic approximation algorithm that tracks a Markov-modulated probability mass function with support on the set of nonnegative integers is analyzed.

Consider a financial market participant observing the trade flow of an asset traded through a limit order book. Trades are driven by an agent-based model where individual agents observe the trading decisions of previous agents, as well as their private signal on the value of the asset and then execute a trading decision. Given trading decisions of agents, how can a market observer detect a shock to the underlying value of the traded asset? The distribution of shock times is assumed to be phase-type distributed to allow for a general set of change time probabilities beyond geometric change times. We show that this problem is equivalent to change detection with social learning. We provide structural results that allow the optimal detection policy to be characterized by a single threshold policy.

In this paper, formation of stable coalitions of users, each exploiting resources in a femto-cell, and the resource allocation in each femto-cell is investigated in a UMTS long term evolution (LTE) network. We study a downlink scenario where users collaborate to increase network throughput and, simultaneously, attempt to increase their own payoffs. Payoffs to the users are defined as the monetary equivalent of the individual users' achievable throughput in the specified coalition structure. A distributed game-theoretic resource allocation mechanism is developed whereby users autonomously decide which sub-channel in which coalition to join. If each user operates according to the proposed algorithm, the sum throughput of all links converges with probability one to its maximum feasible value.

A decision maker records measurements of a finite-state Markov chain corrupted by noise. The goal is to decide when the Markov chain hits a specific target state. The decision maker can choose from a finite set of sampling intervals to pick the next time to look at the Markov chain. The aim is to optimize an objective comprising of false alarm, delay cost, and cumulative measurement sampling cost. Taking more frequent measurements yields accurate estimates but incurs a higher measurement cost. Making an erroneous decision too soon incurs a false alarm penalty. Waiting too long to declare the target state incurs a delay penalty. What is the optimal sequential strategy for the decision maker? This paper shows that under reasonable conditions, the optimal strategy has the following intuitive structure: when the Bayesian estimate (posterior distribution) of the Markov chain is away from the target state, look less frequently; while if the posterior is close to the target state, look more frequently. Bounds are derived for the optimal strategy. Also the achievable optimal cost of the sequential detector as a function of transition dynamics and observation distribution is analyzed. The sensitivity of the optimal achievable cost to parameter and strategy variations is bounded in terms of the Kullback divergence. Also structural results are obtained for joint optimal sampling and measurement control (active sensing).

In this paper, the concentration of target molecules in a fluid flow is estimated using an array of biosensors. The concentration evolves according to an advection-diffusion partial differential equation which is coupled with chemical reaction equations on the biosensor surface. An approximate characterization of the system is developed as a system of ordinary differential equations by exploiting the multiple-time scale behaviour of the system and using the divergence theorem. The estimate of target molecules is then obtained by solving a nonlinear least squares problem. An explicit expression for the asymptotic variance of the estimation error is obtained. To demonstrate the accuracy of proposed method, we illustrate our results on a novel biosensor built out of protein molecules.

We present a decentralized adaptive filtering algorithm in a clustered network of agents. Agents receive payoffs partly due to performing localized tasks in clusters and partly due to strategic interaction with agents outside clusters. Each agent is only aware of the actions of others within its cluster and is oblivious to the actions, or even existence, of agents outside the cluster. We show that the global behavior of the network converges to the set of correlated e-equilibria if the agents follow the proposed algorithm. Thus simple behavior by individual agents can result in sophisticated global behavior.

A duplication-deletion random graph is presented in this paper to model social networks which change over time. The paper analyzes the dynamics of this duplication-deletion random graph where at each time instant, one node can either join or leave the network. A degree distribution analysis is provided for this graph and an expression is derived to compute the power law component. Also a Markov-modulated random graph is analyzed where the the growth of the network evolves according to a slow Markov chain. An upper bound is derived for the mean square error between the estimated degree distribution and the asymptotic one. Using the fact that the duplication-deletion graph satisfies a power law, an upper bound is presented for the most significant singular value of the adjacency matrix of the graph.

How does local and global decision making interact in detection theory? This paper considers multi-agent quickest time change detection with social learning. We show that the optimal decision exhibits a remarkable multi-threshold behavior within the space of Bayesian distributions. For small change probabilities, an explicit characterization of this behavior is obtained in terms of fixed points of the posterior update.

In this paper, we propose a novel statistical estimation algorithm to stochastic context-sensitive grammars (SCSGs). First, we show that a SCSG model can be solved by decomposing it into several causal stochastic context-free grammars (SCFGs) models and each of these SCFGs models can be solved simultaneously using a fully synchronous distributed computing framework. An alternate updating scheme based approximate solution to multiple SCFGs is also provided under the assumption of a realistic sequential computing framework. A series of statistical algorithms are expected to learn SCFGs subsequently. The SCSGs can be then used to represent multiple-trajectory. Experimental results demonstrate the improved performance of our method compared with existing methods for multiple-trajectory classification.

How can one detect if a set of agents is deliberately trying to avoid being detected? By assuming malicious agents are utility maximizers, we use a remarkable result developed by Afriat to construct a decision test that identifies such malicious agents with pre-specified Type-I error probability. Also a stochastic gradient algorithm is given to adapt the probe signals in real time to minimize the Type-II error probabilities of the decision test.

We consider how local and global decision policies interact in stopping time problems such as quickest time change detection. Individual agents make myopic local decisions via social learning, that is, each agent records a private observation of a noisy underlying state process, selfishly optimizes its local utility and then broadcasts its local decision. Given these local decisions, how can a global decision maker achieve quickest time change detection when the underlying state changes according to a phase-type distribution? This paper presents four results. First, using Blackwell dominance of measures, it is shown that the optimal cost incurred in social-learning-based quickest detection is always larger than that of classical quickest detection. Second, it is shown that in general the optimal decision policy for social-learning-based quickest detection is characterized by multiple thresholds within the space of Bayesian distributions. Third, using lattice programming and stochastic dominance, sufficient conditions are given for the optimal decision policy to consist of a single linear hyperplane, or, more generally, a threshold curve. Estimation of the optimal linear approximation to this threshold curve is formulated as a simulation-based stochastic optimization problem. Finally, this paper shows that in multiagent sensor management with quickest detection, where each agent views the world according to its prior, the optimal policy has a similar structure to social learning.

This paper deals with estimation of the concentration of target molecules in a fluid when it flows past multiple biosensors. The fluid flow is modelled as an advection diffusion partial differential equation. Estimating the concentration from multiple biosensors then is equivalent to solving an inverse problem. We use averaging theory methods to model the asymptotic behaviour of PDE model by a system of ordinary differential equations. The resulting nonlinear least squares problem is then solved numerically. We also use the new model to derive the mean squared estimation error of concentration analytically. As a case study, we illustrate our results on a biosensor built out of protein molecules to verify the accuracy of proposed method.

We consider the prediction of a target's destination and simultaneously recover its filtered trajectory. Two novel models for trajectories with known destinations are presented using reciprocal stochastic processes and stochastic context-free grammars. We present a destination-aware syntactic tracker which uses conventional state-space estimates from a legacy tracker to perform prediction and trajectory estimation. We also provide statistical signal processing algorithms for model prediction and maximum likelihood sequence estimation using the proposed trajectory models. Simulation results show that both models considered in the paper have superior estimation performance compared to conventional hidden Markov modeling and can reliably predict the target's destination.

We present a decentralized adaptive filtering algorithm where each agent acts selfishly to maximize its payoff. Agents are only aware of the actions of other agents within their coalitions and have no knowledge of the actions of agents outside the coalition. We show that the global behavior of the system converges to the set of correlated equilibria. Thus simple behavior by individual agents can result in sophisticated global behavior.

Correlated equilibria are a generalization of Nash equilibria that permit agents to act in a correlated manner and can there fore, model learning in games. In this paper we define a special class of correlated equilibria that have hierarchical structure based on the factor graph. Such factor graph-based structural equilibria are more general than Nash equilibria and can model constrained dependencies than general correlated equilibria. We provide the numerical example for using non cooperative stochastic game model on the gene regulatory network under three solution concepts.

Constructing accurate computational models that explain how ions permeate through a biological ion channel is an important problem in biophysics and drug design. Brownian dynamics simulations are large-scale interacting particle computer simulations for modeling ion channel permeation but can be computationally prohibitive. In this paper, we show the somewhat surprising result that a small-dimensional semi-Markov model can generate events (such as conduction events and dwell times at binding sites in the protein) that are statistically indistinguishable from brownian dynamics computer simulation. This approach enables the use of extrapolation techniques to predict channel conduction when performing the actual brownian dynamics simulation that is computationally intractable. Numerical studies on the simulation of gramicidin A ion channels are presented.

As the spectral efficiency of wireless communications systems increases, and the frequency reuse pattern shifts towards universal frequency reuse, the capacity of future wireless and mobile systems will becomes interference limited. We explore the interference pattern of a shared channel in order to establish optimal distributed resource allocation techniques in that channel considering the mutual interference of coexisting links on each other. It is shown that the optimal usage of resources in such a shared channel can only be achieved via a multi-dimensional resource allocation strategy, taking into account not only the link's own channel quality, but also its channel states towards coexisting links. The improvement of capacity as a result of this approach can be attributed to the interference diversity of the channel. The interference diversity gain can be harnessed in time, frequency and space domains. To this end we study two approaches, namely maximizing the capacity of the primary and secondary links under received interference constraint and minimizing the transmitted power of primary and secondary links under minimum QoS guarantee constraint. We study the Ergodic capacity to verify the significant performance improvement which can be achieved by exploiting interference diversity in multi-channel systems such as UMTS Long Term Evolution (LTE). Further we will show that utilizing this diversity gain in QoS-guaranteed scenarios results in a considerable transmission power saving. The case of Outage capacity, which is an instantaneous measure of channel throughput, is shown to be different whereby using an instantaneous received interference threshold outperforms the usage of average received interference limit.

This paper considers downlink spectrum allocation in a long term evolution (LTE) system macrocell which contains multiple femtocells. By incorporating cognitive capabilities into femtocell base stations, the Home evolved Node Bs (HeNBs) can be formulated as secondary base stations seeking to maximize the spectrum utility while minimizing interference to primary base stations (evolved Node-Bs). The competition amongst cognitive HeNBs for spectrum resources is formulated as a non-cooperative game-theoretic learning problem where each agent (HeNB) seeks to adapt its strategy in real time. We formulate the resource block (RB) allocation among HeNBs in the downlink of a LTE system using a game-theoretic framework, where the correlated equilibrium solutions of the formulated game are being investigated. A distributed RB access algorithm is proposed to compute the correlated equilibrium RB allocation policy..

We show that the optimal decision policy for several types of Bayesian sequential detection problems has a threshold switching curve structure on the space of posterior distributions. This is established by using lattice programming and stochastic orders in a partially observed Markov decision process (POMDP) framework. A stochastic gradient algorithm is presented to estimate the optimal linear approximation to this threshold curve. We illustrate these results by first considering quickest time detection with phase-type distributed change time and a variance stopping penalty. Then it is proved that the threshold switching curve also arises in several other Bayesian decision problems such as quickest transient detection, exponential delay (risk-sensitive) penalties, stopping time problems in social learning, and multi-agent scheduling in a changing world. Using Blackwell dominance, it is shown that for dynamic decision making problems, the optimal decision policy is lower bounded by a myopic policy. Finally, it is shown how the achievable cost of the optimal decision policy varies with change time distribution by imposing a partial order on transition matrices.

In this paper, we derive single layer and scalable video rate and distortion models for video bitstreams encoded using the coarse grain quality scalability (CGS) feature of the scalable extension of H.264/AVC. In these models, we assume the source is Laplacian distributed and compensate for errors in the distribution assumption by linearly scaling the Laplacian parameter . Moreover, we present simplified approximations of the derived models that allow for a run-time calculation of sequence dependent model constants. Our models use the mean absolute difference (MAD) of the prediction residual signal and the encoder quantization parameter (QP) as input parameters. Consequently, we are able to estimate the residual MAD, bitrate, and distortion of a future video frame at any QP value and for both base-layer and CGS layer packets. We also present simulation results that demonstrate the accuracy of the proposed models.

Lifetime maximization is a key challenge in the design of sensor-network-based tracking applications. In this paper, formation of optimal coalitions of nodes is investigated for data acquisition in bearings-only target localization such that the average sleep times allocated to the nodes are maximized. Cooperative game theory is utilized as a tool to devise a distributed dynamic coalition formation algorithm in which nodes autonomously decide which coalition to join, while maximizing their feasible sleep times. If each node follows the proposed algorithm, the average sleep time for the entire network eventually converges to its maximum feasible value conditional on the pre-defined localization accuracy. This algorithm can also be employed in tracking slow moving targets.

This paper considers a Markovian dynamical game theoretic setting for distributed transmission control in a wireless sensor network. The available spectrum bandwidth is modeled as a Markov chain. A distributed algorithm named correlated Q-learning algorithm is proposed to obtain the correlated equilibrium policies of the system. This algorithm has the decentralized feature and is easily implementable in a real system. Numerical example is also provided to verify the performances of the proposed algorithms.

Cognitive radio networks (CRN) are promising to enrich the connectivity demand of users through exploiting the under-utilized licensed bands. In this paper, the load-balanced resource allocation problem is formulated as a non-superadditive coalition formation game in which the cognitive radios (CR) form collaborative groups to exploit the spectrum available to cognitive base stations (CBS) most efficiently. A distributed decision-making framework is developed for coalition formation among CRs that converges to the core of the defined game, corresponding to the maximum average payoff conditional on feasibility and subject to a fairness rule. Further, we elaborate on the load balancing properties of the proposed scheme and demonstrate its superior performance, when compared to opportunistic scheduling, through numerical examples.

This paper considers an uplink time division multiple access (TDMA) cognitive radio network where multiple cognitive radios (secondary users) attempt to access a spectrum hole. We assume that each secondary user can access the channel according to a decentralized predefined access rule based on the channel quality and the transmission delay of each secondary user. By modeling secondary user block fading channel qualities as a finite state Markov chain, we formulate the transmission rate adaptation problem of each secondary user as a general-sum Markovian dynamic game with a delay constraint. Conditions are given so that the Nash equilibrium transmission policy of each secondary user is a randomized mixture of pure threshold policies. Such threshold policies can be easily implemented. We then present a stochastic approximation algorithm that can adaptively estimate the Nash equilibrium policies and track such policies for non-stationary problems where the statistics of the channel and user parameters evolve with time.

We explore the interference pattern of a shared channel in order to establish optimal distributed resource allocation techniques in that channel. The interference diversity gain can be achieved in time, frequency and space domain. In particular we develop resource allocation techniques to harness interference diversity gain in the frequency domain. To this end we study two approaches, namely maximizing the capacity of the primary and secondary links under received interference constraint and minimizing the transmitted power of primary and secondary links under minimum QoS guarantee constraint. We will also elaborate on the application of interference diversity in UMTS Long Term Evolution (LTE) systems.

For a connected network of sensors we consider deriving the linear update weights required by a 1-hop distributed linear averaging algorithm (denoted 1-DLA) such that average-consensus is reached when the sensor nodes simultaneously track, by linear stochastic approximation, a set of distinct Markov chains with time-varying regime. It is found the desired consensus is infeasible for any 1-hop 1-DLA type algorithm in this setting, which includes the consensus filter proposed in . However, assuming a symmetric communication graph we show the average-consensus can be approached with zero asymptotic error by an alternative 1-hop algorithm (denoted 4-DLA) that requires each sensor compute 4 estimates {picirc s, s0, scirc} rather than only {s} as required under 1-DLA. We demonstrate a simulation of 4-DLA and explain its advantages compared to alternative multihop algorithms.

With the advances in communication and embedded systems, the monitoring and/or controlling of physical phenomena that span over wide spatial area have been attempted with deployment of a network of inexpensive and miniature sensors. In this paper, we focus on the automated sensor management for target identification at the application layer. The sensor management is formulated using graph grammar that reactively control the states of the sensors based on their proximity to the target and the states of their neighboring sensors. Target identification, on the other hand, concerns the estimation of the target's kinematics and attributes. The current practice is often formulated as finding the conditional probability of the target type on features derived from the sensor measurements with statistical pattern recognition. However, due to lack of training data, we demonstrate that the use of semantic latent indexing and stochastic approximation techniques, borrowed from the computer science community, is a more powerful method for sensor management and target identification.

Biological ion channels are protein tubes that span the cell membrane. They provide a conduction pathway and regulate the flow of ions though the low dielectric membrane. Modeling the dynamics of these channels is crucial in understanding their functionality. This paper proposes a novel simulation framework for modeling ion channels that is based on Finite Element Method (FEM). By using FEM, this is the first framework to allow the use of multiple dielectric constants inside the channel thus providing a more realistic model of the channel. Due to the run-time complexity of the problem, lookup tables must be constructed in memory to store pre- calculated electric potential information. Because of the large number of elements involved in FEM and channel resolution requirements there is the potential for very large lookup tables leading to a performance "bottleneck". This paper discusses strategies for minimizing table size and shows that currently available personal computers are sufficient for attaining reasonable levels of accuracy. For the framework proposed, results show diminishing returns in accuracy with tables sized greater than 2.2 GB.

We present an optimal adaptive modulation and coding policy that minimizes the transmission latency and modulation/coding switching cost across a finite-state Markovian fading channel. We formulate the optimal tradeoff between transmission latency and modulation/coding switching cost as a discounted infinite horizon Markov Decision Problem (MDP). By exploiting special structures of the formulated MDP and under certain sufficient conditions, we show that optimal modulation and coding selection policies are monotone in the state variables. These monotone optimal policies are computationally inexpensive to implement and are scalable in terms of channel and switching cost parameters. Numerical results confirm the monotonicity and threshold-based structure of the optimal Modulation and Coding Scheme (MCS) selection policies under the proposed sufficient conditions.

We consider dynamic spectrum access among cognitive radios from an adaptive, game theoretic learning perspective. Spectrum-agile cognitive radios compete for channels temporarily vacated by licensed primary users in order to satisfy their own demands while minimizing interference. For both slowly varying primary user activity and slowly varying statistics of "fast" primary user activity, we apply an adaptive regret based learning procedure which tracks the set of correlated equilibria of the game, treated as a distributed stochastic approximation. This procedure is shown to perform very well compared with other similar adaptive algorithms. We also estimate channel contention for a simple CSMA channel sharing scheme.

We consider exploiting perfect channel state information for optimal scheduling for point-to-point data transmission over correlated fading wireless channels, where retransmissions are allowed via the use of a channel-aware ARQ protocol. The objective is to achieve a trade-off between energy and packet loss rate subject to a hard delay constraint. Specifically, the aim of the transmission scheduling problem is to minimize the sum of accumulated transmission costs and a penalty cost on the number of lost packets, subject to the constraint that each batch of a finite number of link layer packets has to be transmitted within a prespecified number of transmission time slots. Using the concept of supermodularity, we prove that under some conditions on the costs, the optimal transmission scheduling policy is threshold in the residual transmission time and the buffer occupancy. These two threshold results substantially reduce the computational complexity required to implement the optimal transmission scheduling policy.

In this paper, we address the problem of efficiently allocating network resources to support multiple scalable video streams over a constrained wireless channel. We present a resource allocation framework that jointly optimizes the operation of the link adaptation scheme in the physical layer (PHY), and that of a traffic control module in the network or medium access control (MAC) layer in multirate wireless networks, while satisfying bandwidth/capacity constraints. Multirate networks, such as IEEE 802.16 or IEEE 802.11, adjust the PHY coding and modulation schemes to maintain the reliability of transmission under varying channel conditions. Higher reliability is achieved at the cost of reduced PHY bit-rate which in turn necessitates a reduction in video stream bit-rates. The rate reduction for scalable video is implemented using a traffic control module. Conventional solutions operate unaware of the importance and loss tolerance of data and drop the higher layers of scalable video altogether. In this paper, we consider medium grain scalable (MGS) extension of H.264/AVC video and develop new rate and distortion models that characterize the coded bitstream. Performance evaluations show that our proposed framework results in significant gains over existing schemes in terms of average video PSNR that can reach 3 dB in some cases for different channel SNRs and different bandwidth budgets.

This paper addresses the secondary user rate adaptation problem in cognitive radio networks. By modeling primary user activities and secondary user block fading channels as finite state Markov chains, the transmission rate adaptation problem of each secondary user is formulated as a general-sum dynamic Markovian game with a delay constraint. Assumptions are given so that the Nash equilibrium transmission policy of each user is a randomized mixture of pure threshold policies. We also present a stochastic approximation algorithm which can adaptively estimate the Nash equilibrium policies and track such policies for non-stationary problems where the statistics of the channel and user parameters evolve with time.

We consider the issue of fair share of the spectrum opportunity for the case of spectrum-overlay cognitive radio networks. Owing to the decentralized nature of the network, we adopt a pricing based game-theoretic approach where the actions of players would be choosing the modulation rate. The resulting game can be verified to be supermodular, and thus has at least one pure strategy Nash equilibrium. Next, we propose a Stochastic Approximation based algorithm for the computation of best response correspondence whose convergence to the Pareto-dominant Nash equilibrium can be established. Furthermore, we also propose a decentralized algorithm for tuning the price factor of the network. Our simulation results demonstrate the gains that can be achieved with pricing.

In this paper, we propose a joint source-channel unequal error protection scheme for scalable video streaming over capacity constrained high speed packet access (HSPA) networks. Conventional link adaptation schemes in HSPA networks use the modulation and coding scheme (MCS) that achieves a preset channel frame error rate. Our scheme utilizes video priority information along with channel quality information to set the channel coding rate that maximizes the cumulative coding rate of channel coding and application layer unequal error protection. Performance evaluations show that that under the same constraints our scheme results in an average performance improvement of 0.5dB in video PSNR for different channel conditions and different video sequences.

We present a power and retransmission control policy that achieves an optimal tradeoff between transmission power, delay, and packet drop penalty costs over a radio fading channel. We formulate the underlying power and retransmission control as a Markov decision problem (MDP). Under certain sufficient conditions, we show that the optimal transmission power monotonically decreases in the channel quality and the number of retransmission slots left. These structural results lead to power allocation policies that are computationally inexpensive for on-line implementation and are scalable in terms of transmission parameters. Numerical examples confirm the monotonicity results and demonstrate the improvement in the transmission cost enabled by the optimal policy.

We consider comparison of Mutual Information (MI)-Energy tradeoff in correlated wireless sensor network (WSN) for cooperative multiple input and multiple output (MIMO) and non-cooperative (referred to as single input and single output (SISO)) transmission schemes. Our numerical results indicate that for short distances SISO schemes achieve better Mi-Energy tradeoff than the cooperative MIMO schemes, while for long distances the cooperative MIMO schemes achieve better Mi-Energy tradeoff. We next consider the issue of sensor placement in a correlated WSN. Specifically, we prove that the spacing between nodes to maximize MI is in general an increasing function of observation SNR. From this structural result, we conclude that at high SNR, the various stages of the WSN can be separated by relatively large distances than at low SNR.

The uplink capacity of CDMA cellular networks is improved by adaptive sectoring based on tracking of mobiles' spatial distribution. The distribution is modeled as a spatial Poisson process, with its rate function quantizes the density of the active mobiles. The rate function's time dynamics is assumed to evolve according to mobiles' mobility pattern, and is formulated using the Influence model. In this paper, particle filtering is applied in the tracking and estimation of the mobile concentration based on network traffic, and it enables the computation of the network interference and thus the system outage probability. Different sectoring schemes are compared in terms of outage probabilities, and the minimum scheme is chosen for each time period. More specifically, the adaptive sectoring problem is formulated as a shortest path problem, and the optimal path corresponds to the sectoring scheme with the minimum outage probability.

Scalability in video coding is becoming the primary choice for providing quality of service (QoS) guarantees in wireless video communication. In this paper, we develop real-time rate and distortion prediction models for medium grained scalable (MGS) coded video streams. These models allow mobile video encoders to predict the packet size and corresponding distortion of a video frame using only the mean absolute difference (MAD) of the motion prediction and the quantization parameter (QP). The prediction of rate and distortion measures can be used in devices with cross layer optimization capabilities to choose the combination of base and enhancement layer packets that deliver the best picture quality given channel quality information. Performance evaluations demonstrate that our models accurately predict the size and distortion of base and enhancement layer MGS packets.

In this paper, we present a real-time joint bit-rate and error protection allocation scheme for multiple scalable video streams sharing a single downlink channel. High speed downlink packet access (HSDPA) systems allow for multiple live video streams to share a common downlink channel among multiple mobile users. However, the unreliable nature of the wireless link results in packet losses and fluctuations in the available channel capacity. This calls for flexible error protection and rate control strategies implemented at the video encoders that can respond to the variation in channel conditions. In this paper, we formulate a global optimization problem, which is solved at every frame transmission instant and minimizes the expected sum of the video frame distortions of all users by adjusting the encoding quality at the base- and enhancement-layers as well as the application layer error protection overhead used to combat packet losses. We consider frame-level unequal erasure protection (UXP) as the application layer forward error correction scheme. Performance evaluations show that compared with existing schemes our proposed scheme delivers far superior decoded video quality averaging 1.2 dB in PSNR.

In this paper, adaptive sectoring of a CDMA cellular network is investigated, and the aim is to maximize the uplink capacity by utilizing mobiles' spatial information. One important feature of the algorithm developed is that it does not depend on tracking individual mobile, but rather on the statistics of mobiles. The distribution of mobiles is modeled as a spatial Poisson process, whose rate function quantizes mobile concentration and is inferred with a Bayesian estimator based on the statistics of network traffic. In addition, the time dynamics of the rate function is assumed to evolve according to mobiles' mobility pattern and it is formulated using the influence model. With the knowledge of mobiles' spatial distribution, the interference and thus the outage probability of different sector partitions of a cell can be computed. The adaptive sectoring problem is formulated as a shortest path problem, where each path corresponds to a particular sector partition, and the partition is weighted by its outage probability. In simulation examples, a hot spot scenario is simulated with the adaptive sectoring mechanism, and it is observed that load balancing between sectors is achieved and which greatly reduces the effect of hot spot.

In this paper, we analyze the performance of media-aware multiuser video streaming strategies in capacity limited wireless channels suffering from latency problems and packet losses. Wireless video streaming applications are characterized by their bandwidth-intensity, delay-sensitivity, and loss-tolerance. Our main contributions include (i) a rate-minimized unequal erasure protection (UXP) scheme, (ii) an analytical expression for packet delay and play-out deadline of UXP protected scalable video, (iii) a loss-distortion model for hierarchical predictive video coders with picture copy concealment, (iv) an analysis of the performance and complexity of delay-aware, capacity-aware, and optimized UXP streaming scenarios, and (v) we show that the use of unequal error protection causes a rate-constrained optimization problem to be nonconvex. Performance evaluations using a 3GPP network simulator show that, for different channel capacities and packet loss rates, delay-aware nonstationary rate-allocation streaming policies deliver significant gains which range between 1.65 dB to 2 dB in average Y-PSNR of the received video streams over delay-unaware strategies. These gains come at a cost of increasedofflinecomputation which is performed prior to the start of the streaming session or in batches during transmission and therefore, do not affect the run-time performance of the streaming system.

An efficient radio resource allocation scheme is crucial for guaranteeing the quality of service (QoS) requirements and fully utilizing the scarce radio resources in wireless multimedia networks. Most of previous work of radio resource allocation in traditional wireless networks concentrates on network layer connection blocking probability QoS. In this paper, we show that physical layer techniques and QoS have significant impacts on network layer QoS. We use a concept of cross-layer effective bandwidth to measure the unified radio resource usage taking into account both physical layer receivers and network layer traffic in code devision multiple access (CDMA) networks. Based on this concept, we can use rich theories developed in traditional wireless mobile networks for packet multimedia wireless networks. Moreover, since both physical layer QoS and network layer QoS are considered simultaneously, we can explore the tradeoff between physical layer QoS and network layer QoS in packet multimedia wireless networks.

A fundamental issue in Bayesian decentralized estimation over a sensor network is the inadvertent multiple re-use of data also known as data incest. We show the relationship between data incest and the network topology by using a graph theoretical formulation. A novel necessary and sufficient condition based on the topology of the network is derived so that data incest management can be optimally achieved. This approach requires large storage capabilities at the sensor level. In the case of an arbitrary network, if the necessary and sufficient condition for data incest does not hold then finding a sub-optimal strategy requires solving a 0-1 integer optimization problem where the dimension of the vector to optimize increases with time. Numerical results illustrate the effectiveness of our approach.

This paper deals with the experimental construction, stochastic modeling and statistical signal processing of a novel biosensor comprising of biological ion channels. Such nano-scale biosensors are built by incorporating dimeric gramicidin ion channels into the bilayer membranes of giant unilamellar liposomes and then excising small patches of the membrane loaded with ion channels. We show that target molecules affect the statistics of the gating mechanism of the dimeric gramicidin ion channels and present statistical verifications on the adequacy of a hidden Markov model for modeling of the biosensor. A likelihood ratio test is then devised to detect the presence of target molecules. To test the sensitivity of this model we conducted patch-clamp experiments with and without the methylbenzthonium chloride compound. The real-time detection algorithm was able to accurately detect the presence of the compound from alterations in the patch-clamp recordings. This algorithm provides the sensitive detection system for ongoing development of lipid-based nano-sensors.

A constrained Markov decision process (MDP) approach is deployed to prove the monotone structure of optimal channel-aware transmission policies for packet transmission over a correlated fading wireless channel subject to an average delay constraint. A transmission policy is a function mapping channel state information (CSI), buffer states and numbers of arriving packets to transmit probabilities. The objective is to minimize the average transmission energy cost subject to an average delay constraint. We use the Lagrange multiplier method to convert the constrained MDP to an unconstrained MDP and prove that the unconstrained optimal policy is threshold in the buffer state. It then follows that the constrained optimal transmission policy is a randomized mixture of two pure transmission policies that are threshold in the buffer occupancy.

Multifunction radars (MFRs) are sophisticated sensors with complex dynamical modes that are widely used in surveillance and tracking systems. It is shown in this paper that the stochastic context free grammar (SCFG) is an adequate model for capturing the essential features of the MFR dynamics. We model MFRs as systems that "speak" according to a SCFG, and the grammar is modulated by a Markov chain representing MFRs' policies of operation. We then deal with the statistical signal processing problems of the MFR signal, especially the problem of threat evaluation (electronic support). Maximum likelihood estimator is derived to estimate the threat of the MFR and Bayesian estimator to infer the system parameter values.

We consider opportunistic spectrum access (OSA) which allows secondary users to identify and exploit instantaneous spectrum opportunities resulting from the bursty traffic of primary users. Within the framework of partially observable Markov decision process (POMDP), we develop decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. The focus of this paper is the tradeoff between optimality and complexity of obtaining OSA protocols. We first analyze the computational complexity of designing OSA protocols within the POMDP framework and demonstrate that the complexity grows exponentially with the horizon length (i.e, the spectrum access time of secondary users). By exploiting the underlying structure of the problem, we aim to develop a quantitative characterization of the fundamental tradeoff between optimality and complexity so that a systematic way of balancing these two can be obtained. Specifically, by exploiting the mixing time of the underlying Markov process of spectrum occupancy, we develop a truncated MDP formulation of OSA and reduce the computational complexity from growing exponentially to linearly with the horizon length. More importantly, this truncated MDP formulation provides a systematical way of trading off performance with complexity by choosing an appropriate truncation parameter.

We present an optimal Adaptive Modulation and Coding (AMC) policy that minimizes the transmission latency and modulation/coding switching cost across a finite-state Markovian fading channel. We formulate the optimal tradeoff between the transmission latency and the modulation/coding switching cost as a stochastic shortest path Markov decision problem (MDP). By exploiting special structures of the formulated MDP and under certain sufficient conditions, we show that optimal modulation and coding selection policies are monotone in the state variables. These monotone optimal policies are computationally inexpensive to implement and are scalable in terms of channel and switching cost parameters. Numerical results confirm the monotonicity and threshold-based structure of the optimal MCS selection policies under the proposed sufficient conditions.

We describe a decentralized learning-based activation algorithm for a ZigBee-enabled unattended ground sensor network. Sensor nodes learn to monitor their environment in a low-power "sleep" mode, until an intruder is detected, then enter a full-power mode only if the benefit for doing so outweighs an energy cost. Our formulation accounts for the energy required to transmit and the probability of successful transmission in a crowded ZigBee network. Since these depend on the activity of other nodes, we propose a decentralized adaptive algorithm for sensor activation based on game theoretic principles. We show that the algorithm tracks the time-varying set of correlated equilibria of the problem, and illustrate performance through simulation. The algorithm is described as a stochastic approximation, with attendant differential inclusion analysis.

We consider combination of distributed source coding (DSC) and cooperative transmission techniques to improve energy efficiency in sensor networks. To start with we formulate the data gathering problem in correlated wireless sensor networks with cooperative multiple input and multiple output (MIMO) transmission at the physical layer and DSC at the application layer. Using the concepts of super and sub modularity on a lattice, we analytically quantify as how the optimal constellation size and the optimal number of cooperating nodes vary with respect to the correlation coefficient. In particular, we show that the optimal constellation size is an increasing function of the correlation coefficient. For the MIMO transmission case, the optimal number of cooperating nodes is a decreasing function of the correlation coefficient. We also prove that in a MIMO transmission based scheme the optimal constellation size adopted by each cooperating node is a decreasing function of the number of cooperating nodes. Also, it is shown that the optimal number of cooperating nodes is a decreasing function of the constellation size adopted by each cooperating node. Finally through our numerical results, it is shown that significant energy savings can be obtained if correlation in the network is exploited. Also, when the desired probability of error is small MIMO transmission can lead to large scale energy savings.

Biological ion channels are water-filled angstrom-unit$(1\ { \hbox{angstrom}}\ {\hbox{ unit}}=10^{-10}\ {\hbox{m}})$sized pores formed by proteins in the cell membrane. They are responsible for regulating the flow of ions into and out of a cell and hence they control all electrical activities in a cell. This paper deals with constructing large scale stochastic dynamical models for explaining ion permeation; that is, how individual ions interact with the protein atoms in an ion channel and travel through the channel. These permeation models capture the dynamics of the ions at a femto-second time scale and angstrom-unit spatial scale. We review large scale multiparticle simulation methods such as Brownian dynamics for modeling permeation. Then we present a novel multiparticle simulation methodology, which we call adaptive controlled Brownian dynamics, for estimating the force experienced by a permeating ion at each discrete position along the ion-conducting pathway. The profile of this force, commonly known as thepotential of mean force, results from the electrostatic interactions between the ions in the conduit and all the charges carried by atoms forming the channel the protein, as well as the induced charges on the protein wall. We illustrate the use of adaptive controlled Brownian dynamics in gramicidin channels and shape estimation of sodium channels.

Multifunction radars (MFRs) are sophisticated sensors with complex dynamical modes that are widely used in surveillance and tracking. This paper demonstrates that stochastic context-free grammars (SCFGs) are adequate models for capturing the essential features of the MFR dynamics. Specifically, MFRs are modeled as systems that “speak” a language that is characterized by an SCFG. The paper shows that such a grammar is modulated by a Markov chain representing radar's policy of operation. The paper also demonstrates how some well-known statistical signal processing techniques can be applied to MFR signal processing using these stochstic syntactic models. We derive two statistical estimation approaches for MFR signal processing—a maximum likelihood sequence estimator to estimate radar's policies of operation, and a maximum likelihood parameter estimator to infer the radar parameter values. Two layers of signal processing are introduced in this paper. The first layer is concerned with the estimation of MFR's policies of operation. It involves signal processing in the CFG domain. The second layer is concerned with identification of tasks the radar is engaged in. It involves signal processing in the finite-state domain. Both of these signal processing techniques are important elements of a bigger radar signal processing problem that is often encountered in electronic warfare applications—the problem of the estimation of the level of threat that a radar poses to each individual target at any point in time.

This paper considers the problem of scheduling multiple users in the downlink of a time-slotted cellular data network. For such a network, opportunistic scheduling algorithms improve system performance by exploiting time variations of the radio channel. We present novel optimal and approximate opportunistic scheduling algorithms that combine channel fluctuation and user mobility information in their decision rules. The algorithms modify the opportunistic scheduling framework of Liu et al., (1993) with dynamic constraints for fairness. These fairness constraints adapt according to the user mobility. The adaptation of constraints in the proposed algorithms implicitly results in giving priority to the users that are in the most favorable locations. The optimal algorithm is an offline algorithm that precomputes constraint values according to a known mobility model. The approximate algorithm is an online algorithm that relies on the future prediction of the user mobility locations in time. We show that the use of mobility information in opportunistic scheduling increases channel capacity. We also provide analytical bounds on the performance of the approximate algorithm using the fundamental inequality of Dyer et al., (1986) for linear programs. Simulation results on high data rate (HDR) illustrate the usefulness of the proposed schemes for elastic traffic and macrocell structures

This paper considers optimizing the utilization of radio resources in a heterogeneous integrated system consisting of two different networks: a wireless local area network (WLAN) and a wideband code division multiple access (CDMA) network. We propose a joint session admission control scheme for multimedia traffic that maximizes overall network revenue with quality of service (QoS) constraints over both the WLAN and the CDMA cellular networks. The WLAN operates under the IEEE 802.11e medium access control (MAC) protocol, which supports QoS for multimedia traffic. A novel concept of effective bandwidth is used in the CDMA network to derive the unified radio resource usage, taking into account both physical layer linear minimum mean square error (LMMSE) receivers and characteristics of the packet traffic. Numerical examples illustrate that the network revenue earned in the proposed joint admission control scheme is significantly larger than that when the individual networks are optimized independently with no vertical handoff between them. The revenue gain is also significant over the scheme in which vertical handoff is supported, but admission control is not done jointly. Furthermore, we show that the optimal joint admission control policy is a randomized policy, i.e., sessions are admitted to the system with probabilities in some states.

This paper describes the development of a hierarchical situation assessment system using Bayesian networks and also a situation assessment based decision making system for battlespace environment. The situation assessment system consists of two levels of reconfigurable Bayesian networks that are adapted with changes that occur in the battlespace on two different timescales. The decision making system uses this adaptive situation assessment system to make decisions that in turn affect the battlespace dynamics. An algorithm is provided to model these interactions and dynamics of the battlespace. Furthermore, a Markovian model for the battlespace dynamics is provided

This paper addresses learning based adaptive resource allocation for wireless MIMO channels with Markovian fading. The problem is posed as constrained Markov decision process with the goal of minimizing the average transmission cost (such as the transmission power) with the constraint on the average holding cost (such as the transmitter delay). Standard Q-learning algorithm is employed to adaptively find the optimal policy for unknown channel/traffic statistics, its convergence properties discussed and shown that it can relatively quickly compute the optimal policy even for rather large state spaces. In order to further improve the convergence rate of the standard Q- learning, we establish several structural results on the optimal policies. We show that the optimal transmission policy is monotonic in the buffer occupancy. This permits us to utilize the supermodularity of the Q-factors and form a structured Q-learning algorithm that increases the convergence rate with respect to the standard Q-learning algorithm.

Differentiated services provision is essential for satisfactory performance of ad hoc wireless local area networks (WLAN) carrying applications with different requirements. The IEEE 802.11 protocol, as the dominating standard, does not support differentiated services in its original ad hoc mode of operation, distributed coordination function (DCF). In this paper, a new access protocol is proposed which seamlessly sits on top of and is completely compatible with the IEEE 802.11's DCF and point coordination function (PCF). The new access protocol can successfully prioritize the traffic according to a pre-defined cost function using a burst of black slots. Performance analysis together with comprehensive simulation studies show improved performance, fairness, and differentiation capability over IEEE 802.11.

We consider the problem of optimal transmission scheduling for real time multimedia (video) data transmission over wireless communication links. It is assumed that the wireless channel is Rayleigh fading and can be represented by a finite state Markov chain (FSMC) model, and that retransmissions are allowed via the use of an ARQ protocol. Due to a delay constraint, there is a limit on the number of time slots that may be used to transmit some (pre-designed) number of packets. The problem of optimal transmission scheduling is formulated as a finite horizon Markov decision process (MDP) with a cost function that takes into account the transmission cost and a penalty cost on the packet loss rate. Using the concept of supermodularity and convexity on the optimal cost and immediate cost functions, we prove that the optimal transmission scheduling policy is a threshold function of time and buffer size. These threshold policies are applicable for any delay-sensitive real time packet transmission system. Finally, the theoretical results are illustrated via numerical examples.

This paper addresses optimal sensor scheduling for maximizing network lifetime. We formulate this problem as a stochastic shortest-path multi-armed bandit problem. The optimal transmission scheduling policy is thus to choose the sensor with the largest Gittins index. Exploiting the underlying structure of the sensor scheduling problem, we derive a closed-form expression for the Gittins index. We show that choosing the sensor with the most residual energy is an optimal strategy when the channel fading is independently and identically distributed across sensors.

In modern network centric warfare (NCW) there is a dedicated platform (airplane) assigned to every group of aircraft that specializes in the hard-kill of the enemy guidance-radars by deploying high speed anti-radiation missiles (HARM)s. In this paper we consider the problem of optimal launch control of the HARMs. We formulate the optimal trade-off between the cost of the HARMs and the latency in performing the hard-kill of the enemy radar as a partially observable Markov decision process (POMDP). Next, by reformulating this POMDP as a Markovian search problem, we prove that optimal missile launch control policies are threshold-based policies in nature. We then present optimal threshold policies that unlike their POMDP counterparts are computationally efficient and inexpensive to implement in real time combat systems. Numerical results demonstrate the effectiveness of these threshold based missile deployment algorithms

We discuss the off-line and on-line aspects of trajectory planning in bearings-only localization. Assuming that there are m(ges 1) moveable sensors (e.g. UAVs), which fly in closed trajectories, the aim is to determine the optimal shape of the trajectory. We investigate the properties of closed optimal trajectories in the off-line problem and show that these solutions are invariant under a scaling transformation of the problem parameters. This result is used to numerically derive a set of solutions for the normalized parameters. These solutions are then used in a stochastic search algorithm which randomly explores the trajectories but spends the largest amount of time in the optimal trajectory

We provide a game theoretic formulation for a sensor activation problem in a multi-attribute environment. Activated sensors randomly select one of M environmental attributes, and transmit data on that attribute to an end user. The goal is to maximize the number of attributes reported while minimizing redundant reports and packet collisions, which both increase with the number of active sensors. Sensor participation is optimized according to an adaptive scheme, in which sensors activate only when their expected utility, given by the number of unique attributes reported minus an energy cost, is positive. We formulate a Nash equilibrium policy that maximizes the expected performance from the perspective of each sensor when transmission is according to a one-shot frequency hopping scheme, and compare this to the global optimum

In this paper we present re-enforcement learning algorithms for adaptive modulation in flat fading channels for reconfigurable, agile wireless communications devices. We derive the dynamical stochastic control model, convexity properties of the stated optimization problem, learning based feedback control optimization and numerical simulations of the designed system. We show how this technique can be applied independently of channel model, error correction coding, and modulation constellation options. In addition, we demonstrate the algorithm's learning and tracking capabilities

In this paper, adaptive sectoring of a CDMA cellular network is investigated, and the aim is to maximize the uplink capacity by utilizing mobiles spatial information. The distribution of mobiles is modeled as a spatial Poisson process, whose rate function quantizes mobiles concentration and which can be inferred with a Bayesian estimator based on network traffic. The time dynamics of the rate function is assumed to evolve according to mobiles mobility pattern and which is formulated using the influence model. With mobiles spatial distribution, the interference and thus the outage probability of different sector partitions of a cell can be computed. The adaptive sectoring problem is formulated as a shortest path problem, and the optimal path corresponds to the sector partition with the minimum outage probability

This paper considers the problem of scheduling of multiple users in the downlink of a time-slotted cellular data network. It introduces optimal and approximate opportunistic scheduling algorithms, which combine channel variations and user mobility information in the decision rule. The proposed algorithms modify opportunistic scheduling algorithm of Liu et al. with dynamic fairness constraints that adapt according to the user mobility. The optimum algorithm is an offline algorithm because it pre-computes constraint values for all mobility states according to a known mobility model. The approximate algorithm is an on-line algorithm, and it relies on the future prediction of user mobility locations in time. These predicted values are used in computing constraint values. Simulation results illustrate the usefulness of the proposed schemes for elastic traffic and restrictive constraints. The use of mobility information in opportunistic scheduling also increases channel capacity.

This paper presents a mathematical model which represents packet-level performance in a wireless network using amplify-and-forward cooperative diversity. This model takes into account a bursty traffic arrival pattern at the source node as well as an error recovery mechanism based on a general automatic repeat request (ARQ) protocol. We derive not only the expectation but also the distribution of packet delivery delay. Using the model, we quantify throughput/delay improvement for increasing SNR and/or cooperative nodes. For an additional cooperative node, we quantify the amount of SNR that can be reduced (i. e., SNR saving) without degrading system performance. As an application of the proposed model, we also demonstrate how to determine the minimum number of cooperative nodes to satisfy a certain level of quality of service (QoS) requirements.

We consider the uplink of random access multipacket reception wireless sensor networks where packets may have different priorities. Each sensor aims to optimize its transmission policy, which maps instantaneous channel states and packet priorities to transmit probabilities, to maximize its individual reward. The problem is formulated as a non-cooperative game. We show that the optimal transmission policies have a special structure: given a packet priority, it is optimal for a sensor to transmit with certainty if its channel state is beyond a certain threshold and not to transmit otherwise. We prove that there exists a Nash equilibrium profile at which every sensor deploys a transmission policy of this structure. A convergent stochastic approximation algorithm is proposed for estimating the best response transmission policy for any sensor. The theoretical results and the performance of the proposed algorithm are illustrated via numerical examples.

This paper addresses the problem of dynamic control for power and rate allocation in V-BLAST wireless systems over Markovian fading channels. The problem is posed as a controlled Markov decision process problem with the goal of minimizing the average transmission power with the constraint on the average delay that can be interpreted as the quality of service (QoS) requirement of a given application. Several structural results on the nature of the optimal randomized policies and costs are derived. In particular, it is shown that number of actions to be considered can be reduced by dividing the rate allocation problem into bit-loading problem across individual antennas and the total rate allocation based on the current buffer and channel state. Further, optimal rate allocation policies are shown to be a mixture of two pure policies that are nondecreasing in the buffer state. These results can be utilized to devise an efficient online learning algorithm for optimal rate allocation policies

High-speed downlink packet access (HSDPA) achieves high data rates and high spectral efficiency by using adaptive modulation and coding schemes and employing multicode CDMA. In this paper, we present opportunistic algorithms for scheduling HSDPA users and selecting modulation/coding and multicode schemes that exploit channel and buffer variations to increase the probability of uninterrupted media play-out. First, we introduce a stochastic discrete event model for a HSDPA system. By employing the discrete event model, we transform the scheduling problem of providing uninterrupted play-out to a feasibility problem that considers two sets of stochastic quality-of-service (QoS) constraints: stability constraints and robustness constraints. A methodology for obtaining a feasible solution is then proposed by starting with a so-called stable algorithm that satisfies the stability QoS constraints. Next, we present stochastic approximation algorithms that adapt the parameters of the stable algorithm in a way that a feasible point for the robustness QoS is reached within the feasibility region of the stability QoS

We present a computationally efficient algorithm that minimizes the transmission energy and latency associated with transmitting a file across a Gilbert Elliott fading channel. We formulate the optimal tradeoff between transmission energy and latency as a partially observed Markov decision process problem (POMDP). The channel state is not directly observed and hence transmission decisions must be based on ACK/NAK information provided over a feedback channel. The key idea is to reformulate the resulting POMDP as a Markovian search problem, with optimal transmission control policies that are threshold in nature. Threshold policies are computationally inexpensive to implement. Our analysis shows that for different parameter values of the Gilbert Elliott fading channel, the optimal transmission policy, while threshold in structure, exhibits vastly different behaviour - from persistent retransmission to back-off and wait. Numerical examples demonstrate the performance improvements that can be obtained using the optimal threshold policies as compared to existing heuristic algorithms.

We propose a novel concept of cross-layer effective bandwidth that characterizes the unified resource usage taking into account both physical layer linear minimum mean square error (LMMSE) receivers and statistical characteristics of the packet traffic in code division multiple access (CDMA) networks. Based on the concept of cross-layer effective bandwidth, we develop an optimal connection admission control (CAC) scheme for variable bit rate packet traffic with QoS constraints at both physical and network layers. By introducing a small signal-to-interference ratio (SIR) outage probability using the concept of cross-layer effective bandwidth, the capacity of CDMA networks in the proposed CAC scheme can be increased significantly compared to some existing schemes. The effectiveness of the proposed approaches is demonstrated by numerical examples.

In network centric warfare, sensor platforms with active sensing equipment such as radars can betray their existence, by emitting energy that can be intercepted by enemy surveillance sensors thereby increasing the vulnerability of the entire combat system. To achieve the important tactical requirement of low probability of intercept (LPI), requires dynamically controlling the emission energy of sensors. In this paper, we propose computationally efficient dynamic emission control and management algorithms for multiple networked heterogenous sensors. By formulating the problem as a partially observed Markov decision process (POMDP) with an on-going multi-armed bandit structure, near optimal sensor management algorithms are developed for controlling the active sensor emission to minimize the threat.

Ion channels are biological nanotubes formed by large protein molecules. In this paper we address the permeation problem which deals with the propagation of individual ions in an ion channel at an Angstrom unit spatial scale and femtosecond time scale. We present an adaptive controlled Brownian dynamics simulation approach to predict the structure of an ion channel. The Brownian dynamics algorithm is coupled with a stochastic gradient algorithm to match the simulated current with experimentally determined currents.

In this paper we consider finite-size slotted ALOHA sensor networks with multiple packet reception capability and selfish sensors. Each sensor wishes to maximize its individual expected reward. We exploit decentralized channel state information (CSI) to obtain transmission policies that are optimal for each sensor The problem is formulated as a finite player finite action, non-cooperative stochastic game where each sensor is a selfish but rational player We prove for the first time that under the signal to interference noise ratio (SINR) threshold reception model the optimal transmission policy for each player belongs to the class of threshold policies. As a result, there exists a Nash equilibrium at which all players adopt pure strategies. The optimality of threshold policies greatly simplifies the estimation of optimal transmission schemes. We present a provably convergent algorithm for finding the threshold for each sensor and illustrate its performance via numerical examples.

In this paper we utilize decentralized channel state information (CSI) for designing optimal transmission schemes for slotted ALOHA sensor networks that have multi-packet reception capability. We prove that under certain conditions the optimal transmit probability function is deterministic, i.e., it is optimal for sensors to either transmit or not transmit with certainty depending on their channel states. We present a provably convergent stochastic approximation optimization algorithm to estimate the optimal transmit policy. Numerical studies illustrate the performance of the algorithm and the degenerate, non-randomized structure of the optimal transmission policy.

We present a new approach to radar pulse train analysis in electronic warfare. We consider an alternative to the classical time-of-arrival (TOA) histogram technique commonly used for extraction of complex pulse patterns. We derive a hidden Markov model for the radar word templates, and develop a modified version of the Viterbi algorithm to extract radar words from noisy and corrupted pulse sequences. We argue the advantages of this approach compared to the standard TOA histogram technique, and illustrate operation of the algorithm with computer simulation results.

We propose a novel concept of cross-layer effective bandwidth that characterizes the unified radio resource usage taking into account both physical layer linear minimum mean square error (LMMSE) receivers and varying statistical characteristics of the packet traffic in code division multiple access (CDMA) networks. Based on the concept of cross-layer effective bandwidth, we show that rich theories developed in traditional circuit-switched networks can be used to analyze various radio resource management schemes in packet CDMA networks. The effectiveness of the proposed approaches is demonstrated by numerical examples.

In this paper, quality of service (QoS) guarantees for multimedia traffic are provided by means of cross-layer optimization in code division multiple access (CDMA) networks. We develop optimal connection admission control (CAC) schemes with both physical layer signal-to-interference ratio (SIR) and network layer blocking probability QoS constraints. Packet traffic is modeled as a Markov modulated Poisson process (MMPP). We show that the cross-layer CAC problem in packet CDMA networks has a nearly complete decomposability structure, based on which we propose two CAC algorithms that require much less computation than some existing schemes and can have good approximation to the optimal solutions. The effectiveness of the proposed schemes is demonstrated by numerical examples.

This paper analyzes the tracking properties of the least mean squares (LMS) algorithm when the underlying parameter evolves according to a finite-state Markov chain with infrequent jumps. First, using perturbed Liapunov function methods, mean-square error estimates are obtained for the tracking error. Then using recent results on two-time-scale Markov chains, mean ordinary differential equation and diffusion approximation results are obtained. It is shown that a sequence of the centered tracking errors converges to an ordinary differential equation. Moreover, a suitably scaled sequence of the tracking errors converges weakly to a diffusion process. It is also shown that iterate averaging of the tracking algorithm results in optimal asymptotic convergence rate in an appropriate sense. Two application examples, analysis of the performance of an adaptive multiuser detection algorithm in a direct-sequence code-division multiple-access (DS/CDMA) system, and tracking analysis of the state of a hidden Markov model (HMM) with infrequent jumps, are presented.

High-speed downlink packet access (HSDPA) achieves high data rates and high spectral efficiency by using adaptive modulation and coding (AMC) schemes and employing multi-code operation of CDMA. In this paper we present opportunistic algorithms for scheduling HSDPA users and selecting modulation and coding schemes that exploit channel variations to increase the probability of an uninterrupted media play-out. First we introduce a discrete event model for HSDPA system to transform the scheduling problem for providing an uninterrupted play-out to a feasibility problem that considers short term and long term quality of service (QoS) constraints. A methodology for obtaining a feasible solution is then proposed by starting with a so called stable algorithm that satisfies the long term QoS constraints (if possible with any scheduling policy). Next, we present stochastic approximation algorithms that adapt the parameters of the stable algorithm in a way that a feasible point for the short term QoS is reached within the feasibility region of the long term QoS.

Next generation wireless code division multiple access (CDMA) networks are required to support packet multimedia traffic. This paper addresses the connection admission control problem for multi-service packet traffic, modeled as a Markov modulated Poisson process (MMPP) with the quality of service (QoS) requirements on both physical layer signal-to-interference (SIR) and network layer blocking probability. Optimal linear-programming-based algorithms are presented that take into account SIR outage probability constraints. By exploiting the MMPP traffic models and introducing a small SIR outage probability, the proposed algorithms can dramatically improve the network utilization. Numerical examples illustrating the performance of the proposed schemes are presented.

We present discrete stochastic optimization algorithms that adaptively learn the Nernst potential in membrane ion channels. The proposed algorithms dynamically control both the ion channel experiment and the resulting hidden Markov model (HMM) signal processor and can adapt to the time-varying behaviour of ion channels. One of the most important properties of the proposed algorithms are their self-learning capability - they spends most of the computational effort at the global optimizer (Nernst potential).

This paper presents discrete stochastic approximation (DSA) algorithms for time synchronization in OFDM systems. It is shown that the discrete stochastic approximation algorithms can be effectively used to achieve a significant reduction in computational complexity compared to brute force maximum-likelihood (ML) methods for OFDM synchronization. The most important property of the proposed algorithms is their recursive self-learning capability - most of the computational effort is spent at the global or a local optimizer of the objective function. An adaptive version of the discrete stochastic approximation algorithm is also presented for tracking time varying time delays and frequency offsets in time selective fading channels. Detailed numerical examples illustrate the performance gains of these DSA based synchronization algorithms.

The aim of this paper is to develop discrete stochastic approximation algorithms that adaptively optimize the spreading codes of users in a code-division multiple-access (CDMA) system employing linear minimum mean-square error (MMSE) receivers. The proposed algorithms are able to adapt to slowly time-varying channel conditions. One of the most important properties of the algorithms is their self-learning capability-they spend most of the computational effort at the global optimizer of the objective function. Tracking analysis of the adaptive algorithms is presented together with mean-square convergence. An adaptive-step-size algorithm is also presented for optimally adjusting the step size based on the observations. Numerical examples, illustrating the performance of the algorithms in multipath fading channels, show substantial improvement over heuristic algorithms.

An on-line Bayesian based multiple hypotheses detection algorithm is used in the detection/isolation of a new user in a multiuser CDMA environment. The algorithm makes use of user arrival rate information available at the system admission controller. Comparison by simulation between this algorithm and the Matrix CUSUM shows that, when such information is available, the new algorithm that incorporates this information can achieve better performance than the non-Bayesian approach.

Multisensor data fusion is one of the key evolving technologies that can be implemented on several architectures. Distributed sensor network architecture provides a good balance between cost, scalability and communication limits of links connecting multiple sensors. However, this architecture is prone to the problem of data incest. Data incest arises due to multiple usage of identical information as if it were independent information. In most cases, it will falsely increase the confidence of a biased overall estimate. It is a fundamental issue in the many-to-many sensor network configurations, where all network nodes are communicating with all nodes. This paper describes a fusion strategy which can be adopted for this distributed network structure that renders incest free estimates.

We derive stochastic control algorithms to achieve the optimal tradeoff between throughput and energy consumption for transmitting packets across a time varying wireless channel with memory. The channel state is not directly observed and hence transmission decisions must be based on ACK/NAK information provided over a feedback channel. By reformulating the problem as a Markovian search problem, we propose a conjecture that the optimal transmission control policies are threshold in nature. Threshold policies are computationally inexpensive to implement. Numerical simulations demonstrate the performance improvements that can be obtained using the optimal threshold policies as compared to heuristic algorithms.

The aim of this paper is to present discrete stochastic approximation algorithms for adaptively optimizing the spreading code of users in a CDMA system. The proposed algorithm can adapt to slowly time varying channel conditions. The most important property of the proposed algorithm is its self-learning capability - it spend most of the computational effort at the global minimizer of the objective function. A tracking analysis of the adaptive algorithms is also presented together with square convergence analysis. Numerical examples illustrate the performance of the algorithms in multipath fading channels.

Motivated by the developments on iterate averaging of recursive stochastic approximation algorithms and asymptotic analysis of sign-error algorithms for adaptive filtering, this work develops two-stage sign algorithms for adaptive filtering. The proposed algorithms are based on constructions of a sequence of estimates using large step sizes followed by iterate averaging. Our main effort is devoted to improving the performance of the algorithms by establishing asymptotic normality of a suitably scaled sequence of the estimation errors. The asymptotic covariance is calculated and shown to be the smallest possible. Hence, the asymptotic efficiency or asymptotic optimality is obtained. Then variants of the algorithm including sign-regressor procedures and constant-step algorithms are studied. The minimal window width of averaging is also dealt with. Finally, iterate-averaging algorithms for blind multiuser detection in direct sequence/code-division multiple-access (DS/CDMA) systems are proposed and developed, and numerical examples are examined.

The paper presents a low complexity discrete stochastic approximation algorithm for time and frequency synchronization in OFDM systems. The proposed technique can track the conditions of a slowly time varying channel where synchronization parameters, namely the symbol timing and frequency offset, vary slowly with time. The most important property of the proposed algorithm is its self-learning capability - it spends most of the computational effort at the global minimizer of the objective function. In particular, we show that the algorithm achieves an /spl epsiv/=(1-/spl rho/)/(1+/spl rho/) reduction in computational cost (in terms of complex multiplications to be performed), where /spl rho/=N/sub cp//N is the ratio between cyclic prefix length (N/sub cp/) and number of subcarriers (N) of the OFDM system (e.g. N=512 and N/sub cp/=64 gives /spl epsiv/=78%). Numerical examples illustrate the synchronization accuracy of the proposed technique in terms of symbol timing and frequency offset estimation errors.

A novel access control strategy for cellular DS-CDMA networks is proposed within the framework of Markov Decision Processes. This paper considers the scenario where users in the network are partitioned into two groups, realtime and non-realtime; and only non-realtime users may be “access controlled” as they are more delay tolerant. The transmission rate of non-realtime users are then regulated via time-division multiplexing to satisfy the QoS requirements. The ACS proposed is optimal because it maximises the transmission rate of non-realtime users while ensuring that QoS requirement of all users are satisfied.

This letter develops a sequential composite hypotheses test for detecting failure of a decision-directed recursive least square (RLS) adaptive multiuser detector (MUD) and convergence of a blind RLS (BLRS) MUD when used in the downlink of direct-sequence/code division multiple access (DS/CDMA) systems. Simulations are provided to demonstrate the effectiveness of the test and to characterize the SIR improvement achievable in a dynamic environment where the number of interferers is time-varying.

This paper is concerned with recursive algorithms for the estimation of hidden Markov models (HMMs) and autoregressive (AR) models under the Markov regime. Convergence and rate of convergence results are derived. Acceleration of convergence by averaging of the iterates and the observations are treated. Finally, constant step-size tracking algorithms are presented and examined.

This paper considers the call admission control problem for multi-service wireless CDMA cellular systems with buffering. The call admission problem is formulated as a semi-Markov decision process with constraints on the blocking probabilities and SIR. By using recent results in large random matrices, the SIR constraints incorporate multi-class voice/data services and fading channels. We show that the optimal call admission policy can be computed via a linear programming based algorithm.

Consider the hidden Markov model estimation problem where the realization of a single Markov chain is observed by a number of noisy sensors. The sensor scheduling problem for the resulting hidden Markov model is as follows: design an optimal algorithm for selecting at each time instant, one of the many sensors to provide the next measurement. Each measurement has an associated measurement cost. The problem is to select an optimal measurement scheduling policy, so as to minimize a cost function of estimation errors and measurement costs. The problem of determining the optimal measurement policy is solved via stochastic dynamic programming. An optimal finite dimensional algorithm is presented along with numerical results.

This paper illustrates the use of "averaging" to improve the convergence rate of adaptive sign regressor and sign error multiuser detectors. The ingenious concept of averaging was invented by Polyak (1990) - this paper analyses the performance of averaging in the sign error and sign regressor adaptive blind multiuser detection algorithms in DS/CDMA systems.

The task of polling a roaming mobile user in a cellular network to determine its location is known as paging and it requires the use of limited wireless resources. Current cellular mobile communication systems use a broadcast (blanket) paging strategy where all the cells in a location area are polled for the mobile station. This is wasteful in resources due to increased signalling load. We formulate the paging problem as an optimal search problem and derive efficient sequential paging strategies for roaming mobile users. Using the theory of partially observed Markov decision processes (POMDP) we design a smart distributor which sequentially pages roaming mobile users to minimise signalling load.

"track-before-detect" (TBD) is a target tracking technique where the data is processed over a number of frames before decisions on target existence are made. The aim of this paper is to use extreme value theory to analyse the performance of a dynamic programming based TBD algorithms. Asymptotic expressions are obtained for the false alarm and track detection probabilities using extremal analysis of limiting distributions. Apart from fitting the simulated results far more accurately than previous works in the TBD literature, our analysis does not require the unrealistic assumptions of independence and Gaussianity.

We develop an adaptive forgetting factor blind RLS algorithm for code-aided suppression of multiple access interference (MAI) and narrow-band interference (NBI) in DS/CDMA systems. The algorithm optimally adapts both the forgetting factor and the weight vector of the linear multiuser detector using the received measurements. Simulations show that the proposed algorithm is superior to the blind RLS algorithm in dynamic environments.

In this paper, we present a blind adaptive gradient (BAG) algorithm for code-aided suppression of multiple-access interference (MAI) and narrow-band interference (NBI) in direct-sequence/code-division multiple-access (DS/CDMA) systems. This BAG algorithm is based on the concept of accelerating the convergence of a stochastic gradient algorithm by averaging. This ingenious concept of averaging was invented by Polyak and Juditsky (1992)-this paper examines its application to blind multiuser detection and NBI suppression in DS/CDMA systems. We prove that BAG has identical convergence and tracking properties to recursive least squares (LMS) but has a computational cost similar to the least mean squares (LMS) algorithm-i.e., an order of magnitude lower computational cost than RLS. Simulations are used to compare our averaged gradient algorithm with the blind LMS and LMS schemes.

Estimation of the state levels of a discrete-time, finite-state Markov chain hidden in coloured Gaussian noise and subjected to unknown nonlinear distortion is considered. If the nonlinear distortion has almost linear behaviour for small values near zero or for large values, extreme value theory can be applied to the level estimation problem, resulting in simple estimation algorithms. The extreme value-based level estimator is computationally inexpensive and has potential applications in data measurement systems where inaccuracies are introduced by dead zones or saturation in sensor characteristics. The effectiveness of the new level estimator is demonstrated by way of computer simulations.

The multi-arm bandit problem is widely used in scheduling of traffic in broadband networks, manufacturing systems and robotics. This paper presents a finite dimensional optimal solution to the multi-arm bandit problem for hidden Markov models. The key to solving any multi-arm bandit problem is to compute the Gittins (1979, 1989) index. In this paper a finite dimensional algorithm is presented which exactly computes the Gittins index. Suboptimal algorithms for computing the Gittins index are also presented and experimentally shown to perform almost as well as the optimal method. Finally an application of the algorithms to tracking multiple targets with a single intelligent sensor is presented.

Consider the problem where pulse trains transmitted from a known number of sources are received on a single communications channel. These pulses are corrupted with noise. The deinterleaving problem is to determine which source contributed which pulse and the periods and phases of each source. This paper explores the performance of a number of deinterleaving algorithms. We propose an alternative to the existing forward dynamic programming (FDP) technique: simulated annealing (SA). It can use either the same cost function as for FDP, or an L/sub 1/ or L/sub 2/ norm output error cost function. We also investigate modelling the noise by heavy-tailed distributions, in addition to white Gaussian noise (WGN).

This paper presents a novel nonlinear filter and parameter estimator for narrow band interference suppression in code division multiple access spread-spectrum systems. As in the article by Rusch and Poor (1994), the received sampled signal is modeled as the sum of the spread-spectrum signal (modeled as a finite state independently identically distributed (i.i.d.) process-here we generalize to a finite state Markov chain), narrow-band interference (modeled as a Gaussian autoregressive process), and observation noise (modeled as a zero-mean white Gaussian process). The proposed algorithm combines a recursive hidden Markov model (HMM) estimator, Kalman filter (KF), and the recursive expectation maximization algorithm. The nonlinear filtering techniques for narrow-band interference suppression presented in Rusch and Poor and our proposed HMM-KF algorithm have the same computational cost. Detailed simulation studies show that the HMM-KF algorithm outperforms the filtering techniques in Rusch and Poor. In particular, significant improvements in the bit error rate and signal-to-noise ratio (SNR) enhancement are obtained in low to medium SNR. Furthermore, in simulation studies we investigate the effect on the performance of the HMM-KF and the approximate conditional mean (ACM) filter in the paper by Rusch and Poor, when the observation noise variance is increased. As expected, the performance of the HMM-KF and ACM algorithms worsen with increasing observation noise and number of users. However, HMM-KF significantly outperforms ACM in medium to high observation noise.

Consider the Hidden Markov model where the realization of a single Markov chain is observed by a number of noisy sensors. The sensor scheduling problem for the resulting Hidden Markov model is as follows: design an optimal algorithm for selecting at each time instant, one of the many sensors to provide the next measurement. Each measurement has an associated measurement cost. The problem is to select an optimal measurement scheduling policy, so as to minimize a cost function of the estimation errors and measurement costs. The problem of determining the optimal measurement policy is solved via stochastic dynamic programming. Numerical results are presented.

We present a finite dimensional iterative algorithm for optimal maximum a posteriori (MAP) state estimation of bilinear systems. Bilinear models are appealing in their ability to represent or approximate a broad class of nonlinear systems. We show that several bilinear models previously considered in the literature are special cases of the general bilinear model we propose. Our iterative algorithm for state estimation is based on the expectation-maximization (EM) algorithm and outperforms the widely used extended Kalman filter (EKF). Unlike the EKF our algorithm is an optimal (in the MAP sense) finite-dimensional solution to the state sequence estimation problem for bilinear models.

This paper presents algorithms for blind detection of equalisation errors when the communication channel is a finite impulse response (FIR) system with stochastic time-varying taps. The taps are assumed to evolve according to a finite-state, homogeneous Markov chain. Errors are detected by applying a binary hypothesis test to the innovations obtained from a hidden Markov model (HMM) filter. We present off-line and on-line error detection algorithms. These algorithms are verified experimentally in computer simulations.

This paper considers state estimation for a discrete-time hidden Markov model (HMM) when the observations are delayed by a random time. The delay process is itself modelled as a finite state Markov chain which allows an augmented state HMM to model the overall system. State estimation algorithms for the resultant HMM are then presented. The motivation for the model stems from the situation when distributed sensors transmit measurement over a connectionless packet switched communications network.

This paper presents a novel nonlinear estimation algorithm based on hidden Markov models for narrowband interference suppression in CDMA spread spectrum systems. The proposed algorithm combines a recursive hidden Markov model estimator, a Kalman filter and a recursive prediction error parameter estimation algorithm. It is shown that the proposed algorithm not only outperforms the nonlinear filtering techniques for narrowband interference suppression presented in Rusch and Poor (1994), but that it outperforms and has faster, more robust convergence properties than the cross-coupled expectation maximization based algorithm presented in Logothetis and Krishnamurthy.

We present an on-line test for blind detection of equalization errors in digital communication systems. The test is based on the observation that for linear time-invariant channels the relationship between the transmitted symbol estimates generated by the equalizer and the noisy channel output can be represented by an underlying linear time-invariant model if and only if the equalizer output sequence is not in error. The presence of equalization errors renders this relationship time-varying, whose occurrence is detected by the proposed on-line test. The test is obtained from a previously proposed off-line least squares test by essentially replacing the least squares algorithm with its recursive version.

The paper presents a quick and simplified aggregation method for a large class of Markov chain functionals based on the concept of stochastic complementation. Aggregation results in a reduction in the number of Markov states by grouping them into a smaller number of aggregated states, thereby producing a considerable saving on computational complexity associated with maximum likelihood parameter and state estimation for hidden Markov models. The importance of the proposed aggregation method stems from the ease with which Markov chains with a large number of states can be aggregated. Three Markov chain functionals which have widespread use are considered to illustrate the application of our aggregation method.

Equalisation errors result from discrepancies between transmitted symbols and their estimates at the channel equaliser output in a digital communication system. This paper presents an on-line test to detect the occurrence of equalisation errors without direct access to the channel input. The test draws on the observation that for linear time-invariant (LTI) channels the relationship between transmitted symbol estimates generated by the equaliser and the noisy channel output can be represented by an underlying linear time-invariant model if and only if no equalisation errors are present in the sequence of transmitted symbol estimates. The presence of equalisation errors renders this relationship time-varying, of which the occurrence is detected by the proposed on-line test using the recursive least squares (RLS) algorithm. Simulation studies corroborate the good detection performance of the test.

The paper presents a maximum likelihood (ML) blind channel equalisation algorithm based on the expectation-maximisation (EM) algorithm. We assume that the channel input sequence is a finite-state Markov chain and the channel output sequence is obtained from the continuous-time channel output by oversampling it at a rate higher than the channel input symbol rate, which leads to a fractionally-spaced channel equalisation problem. The objective of blind channel equalisation is to estimate the channel input symbols without explicit knowledge of the channel characteristics and the requirement of training data. The availability of multichannel outputs for the same channel input improves the reliability of the estimates. A reduced-cost blind equalisation algorithm which draws on aggregation by stochastic complementation is also proposed. A simulation example is presented to demonstrate the performance of the proposed algorithms.

A discrete time Poisson process whose rate evolves as the square of the state of a linear Gaussian dynamical system is studied. An optimal filter is derived, yielding real-time estimates of the Poisson rate. Also a suboptimal filter based on an Edgeworth series expansion is derived.

This paper develops a reduced-complexity online state sequence and parameter estimator for superimposed convolutional coded signals. Joint state sequence and parameter estimation is achieved by iteratively estimating the state sequence via a variable reduced-complexity Viterbi algorithm (VRCVA) and the model parameters via a recursive expectation maximization (EM) approach. The VRCVA is developed from a fixed reduced-complexity Viterbi algorithm (FRCVA). The FRCVA is a special case of the delayed decision-feedback sequence estimation (DDFSE) algorithm. The performance of online versions of the FRCVA, VRCVA, and the standard Viterbi algorithm (VA) are compared when they are used to estimate the state sequence as part of the reduced-complexity online state sequence and parameter estimator.

We consider the de-interleaving of N independent autoregressive (AR) processes from 1-bit quantized measurements. De-interleaving has applications in radar and signal detection. Other possible applications are computer communications and neural systems. The received signal (pulse train) is the superposition of N 1-bit quantized Gaussian AR processes observed in white Gaussian noise. The aim is to identify which sources are responsible for the observed noisy pulses. Furthermore, it is desired to obtain parameter estimates for the N sources. The proposed algorithm, (subject to model assumptions) optimally combines hidden Markov model and binary time series estimation techniques.

In this paper we propose algorithms for parameter estimation of fast-sampled homogeneous Markov chains observed in white Gaussian noise. Our algorithms are obtained by the robust discretization of stochastic differential equations involved in the estimation of continuous-time hidden Markov models (HMM's) via the EM algorithm. We present two algorithms: the first is based on the robust discretization of continuous-time filters that were recently obtained by Elliott to estimate quantities used in the EM algorithm; the second is based on the discretization of continuous-time smoothers, yielding essentially the well-known Baum-Welch re-estimation equations. The smoothing formulas for continuous-time HMM's are new, and their derivation involves two-sided stochastic integrals. The choice of discretization results in equations which are identical to those obtained by deriving the results directly in discrete time. The filter-based EM algorithm has negligible memory requirements; indeed, independent of the number of observations. In comparison the smoother-based discrete-time EM algorithm requires the use of the forward-backward algorithm, which is a fixed-interval smoothing algorithm and has memory requirements proportional to the number of observations. On the other hand, the computational complexity of the filter-based EM algorithm is greater than that of the smoother-based scheme. However, the filters may be suitable for parallel implementation. Using computer simulations we compare the smoother-based and filter-based EM algorithms for HMM estimation. We provide also estimates for the discretization error.

Krishnamurthy and Mareels presented a parameter estimation algorithm called the binary series estimation algorithm (BSEA) for Gaussian auto-regressive (AR) time series given 1-bit quantized noisy measurements. The present authors carry out an asymptotic analysis of the BSEA for Gaussian AR models. In particular, from a central limit theorem they obtain expressions for the asymptotic covariances of the parameter estimates. From this they: (1) Present an algorithm for estimating the order of an AR series from one-bit quantized measurements. (2) Theoretically they justify why BSEA can yield better estimates than the Yule-Walker methods in some cases.

We propose maximum-likelihood (ML) estimation schemes for nearly completely decomposable Markov chains (NCDMC) in white Gaussian noise. Aggregation techniques based on stochastic complementation are applied to reduce the dimension of the resulting hidden Markov model (HMM) and hence substantially reduce the computational costs of the estimation algorithms. We then present an aggregation based expectation maximization (EM) algorithm for estimating the parameters and states of the HMM.>

We consider the estimation of various Markov-modulated time series. We obtain maximum likelihood estimates of the time-series parameters including the Markov chain transition probabilities and the time-series coefficients using the expectation maximization (EM) algorithm. In addition, the recursive EM algorithm is used to obtain on-line parameter estimates. Simulation studies show that both algorithms yield satisfactory results.>