We study the \emph{Online Bookmaking} problem, where a bookmaker dynamically updates betting odds on the possible outcomes of an event. In each betting round, the bookmaker can adjust the odds based on the cumulative betting behavior of gamblers, aiming to maximize profit while mitigating potential loss. We show that for any event and any number of betting rounds, in a worst-case setting over all possible gamblers and outcome realizations, the bookmaker’s optimal loss is the largest root of a simple polynomial. Our solution shows that bookmakers can be as fair as desired while avoiding financial risk, and the explicit characterization reveals an intriguing relation between the bookmaker’s regret and Hermite polynomials. We develop an efficient algorithm that computes the optimal bookmaking strategy: when facing an optimal gambler, the algorithm achieves the optimal loss, and in rounds where the gambler is suboptimal, it reduces the achieved loss to the \emph{optimal opportunistic} loss, a notion that is related to subgame perfect Nash equilibrium. The key technical contribution to achieve these results is an explicit characterization of the \emph{Bellman-Pareto frontier}, which unifies the dynamic programming updates for Bellman’s value function with the multi-criteria optimization framework of the Pareto frontier in the context of vector repeated games.

In online betting, the bookmaker can update the payoffs it offers on a particular event many times before the event takes place, and the updated payoffs may depend on the bets accumulated thus far. We study the problem of bookmaking with the goal of maximizing the return in the worst-case, with respect to the gamblers' behavior and the event's outcome. We formalize this problem as the Optimal Online Bookmaking game, and provide the exact solution for the binary case. To this end, we develop the optimal bookmaking strategy, which relies on a new technique called bi-balancing trees, that assures that the house loss is the same for all decisive betting sequences, where the gambler bets all its money on a single outcome in each round.

We consider reward systems defined as iterative decision-making processes, where a player selects an action from the unit interval, and the environment responds by choosing a reward function from a known set of functions. The goal of the player is to accumulate rewards that exceed a given threshold in minimal time, and the performance is measured via regret with respect to an optimal player who knows the entire sequence of reward functions in advance. The central challenge lies in the dynamical nature of the reward system: each time step may involve a different reward function, requiring the player’s policy to adapt over time and making the regret an infinite-letter optimization problem. Our main result is an explicit expression for the optimal regret in the case of two linear reward functions that have opposing slopes. Moreover, we show that the optimal regret is achieved by a piecewise-constant action sequence, where both the transition times and action values exhibit special structural properties. These properties seem fundamental and may extend to classes of nonlinear reward functions. Finally, we highlight the implications of our solution in the context of communication, particularly, in characterizing the capacity of arbitrarily varying channels (AVCs) under competitive performance criteria.

We consider the problem of remotely stabilizing a linear dynamical system. In this setting, a sensor co-located with the system communicates the system's state to a controller over a noisy communication channel with feedback. The objective of the controller (decoder) is to use the channel outputs to estimate the vector state with finite zero-delay mean squared error (MSE) at the infinite horizon. It has been shown in [1] that for a vector Gauss-Markov source and either a single-input multiple-output (SIMO) or a multiple-input single-output (MISO) channel, linear codes require the minimum capacity to achieve finite MSE. This paper considers the more general problem of linear zero-delay joint-source channel coding (JSCC) of a vector-valued source over a multiple-input multiple-output (MIMO) Gaussian channel with feedback. We study sufficient and necessary conditions for linear codes to achieve finite MSE. For sufficiency, we introduce a coding scheme where each unstable source mode is allocated to a single channel for estimation. Our proof for the necessity of this scheme relies on a matrix-algebraic conjecture that we prove to be true if either the source or channel is scalar. We show that linear codes achieve finite MSE for a scalar source over a MIMO channel if and only if the best scalar sub-channel can achieve finite MSE. Finally, we provide a new counter-example demonstrating that linear codes are generally sub-optimal for coding over MIMO channels.

This paper presents a data-driven methodology for estimating capacity regions in multi-user communication scenarios, focusing on channels with discrete alphabets, both with and without feedback. Prior research has successfully utilized neural networks for estimating capacity regions in continuous domains. However, the shift to discrete alphabets introduces a significant challenge due to the lack of end-to-end differentiability of the joint model. To tackle this issue, we first formulate the optimization problem of the causally conditioned directed information rate as a decentralized Markov decision process (MDP). Building on this formulation, we introduce a tractable optimization procedure specifically designed to estimate rate pairs that lie on the boundary of the capacity region. In addressing the inherent complexity of the MDP state space, we employ a reinforcement learning (RL) algorithm to learn optimal policies. We demonstrate the performance of our methodology by applying it to various communication scenarios, including the two-way channel and the multiple access channel (MAC). The results showcase the adaptability and performance of the proposed RL-based framework in estimating capacity regions without explicit knowledge of the underlying channel model, whether there is feedback or not.

Arbitrary varying channels (AVC) are used to model communication settings in which a channel state may vary arbitrarily over time. Their primary objective is to circumvent statistical assumptions on channel variation. Traditional studies on AVCs optimize rate subject to the worst-case state sequence. While this approach is resilient to channel variations, it may result in low rates for state sequences that are associated with relatively good channels. This paper addresses the analysis of AVCs through the lens of competitive analysis, where solution quality is measured with respect to the optimal solution had the state sequence been known in advance. Our main result demonstrates that codes constructed by a single input distribution do not achieve optimal competitive performance over AVCs. This stands in contrast to the single-letter capacity formulae for AVCs, and it indicates, in our setting, that even though the encoder cannot predict the subsequent channel states, it benefits from varying its input distribution as time proceeds.

In this paper, we investigate the capacity of finite-state channels (FSCs) in the presence of delayed feedback. We show that the capacity of a FSC with delayed feedback can be computed as that of a new FSC with instantaneous feedback and an extended state. Consequently, graph-based methods to obtain computable upper and lower bounds on the delayed feedback capacity of unifilar FSCs are proposed. Based on these methods, we establish that the capacity of the trapdoor channel with delayed feedback of two time instances is given by$\log _{2}\left ({\frac {3}{2}}\right )$. In addition, we derive an analytical upper bound on the delayed feedback capacity of the binary symmetric channel with a no consecutive ones input constraint. This bound also serves as a novel upper bound on its non-feedback capacity, which outperforms all previously known bounds. Lastly, we demonstrate that feedback does improve the capacity of the dicode erasure channel.

We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a significant loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens ofcompetitive analysis. The main idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that adapt to the channel at use, we consider rateless codes with a fixed number of message bits and random decoding times. We propose two competitive metrics: the competitive ratio between the expected rates of the two codes, and a regret defined as the difference between the expected rates. The competitive ratio, for instance, provides a percentage guarantee on the expected rate of the designed code when compared to the rate of the clairvoyant code that knows the channel at hand. Our main results are single-letter expressions for the optimalcompetitive-ratioandregret, expressed as a max-min or minmax optimization. Several examples illustrate the benefits of the competitive analysis approach to code design compared to the compound channel.

We consider finite-state channels (FSCs) with feedback and state information known causally at the encoder. This setting is quite general and includes: a memoryless channel with i.i.d. state (the Shannon strategy), Markovian states that include look-ahead (LA) access to the state and energy harvesting. We characterize the feedback capacity of the general setting as the directed information between auxiliary random variables with memory to the channel outputs. We also propose two methods for computing the feedback capacity: (i) formulating an infinite-horizon average-reward dynamic program; and (ii) a single-letter lower bound based on auxiliary directed graphs called$Q$-graphs. We demonstrate our computation methods on three examples. In the first example, we introduce a channel with LA and establish a closed-form, analytic lower bound on its feedback capacity. Furthermore, we extend the channel with general parameters, and derive numerical lower bounds for each parameter. In the second example, we show that the mentioned methods achieve the feedback capacity of known unifilar FSCs such as the Ising channel. Finally, in the last example, we generalize the Ising channel such that the state is stochastically dependent on the input, and investigate its feedback capacity.

In this paper, we introduce a data-driven methodology for estimating capacity regions of continuous channels in multi-user communication systems. Computing capacity regions is a long standing open problem, even in simple communication scenarios. Nevertheless, it is often possible to represent their capacity regions as the limit of an optimization problem (a multi-letter expression). In many cases, these multi-letter expressions can be expressed in terms of directed information (DI) rates. Accordingly, our approach utilizes neural networks to estimate capacity regions, leveraging the recent introduction of the directed information neural estimator (DINE). The main idea of our methodology involves training DINE-based models using samples of channel inputs and outputs, and using these models to estimate the DI rate terms that are intrinsic to the studied capacity region. To estimate the capacity region rates, we optimize the DI rates over the involved input distributions which are parameterized by a neural distribution transformer (NDT), and execute an alternating maximization procedure between the NDT models and DINE-based models until convergence is achieved. The methodology is suitable for the case where the channel is treated as a "black-box" and the designer can only gather observations of its inputs and outputs, lacking any knowledge of the explicit channel model. The performance of our proposed algorithm is shown via several well-known settings, including the Gaussian two-way channel and the two-user Gaussian multiple-access channel with and without feedback.

We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens of competitive analysis. The idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that can adapt to the channel at use, we consider rateless codes with a fixed number of information bits and random decoding times. We propose two competitive metrics: the competitive ratio between the decoding times of the two codes, and a regret defined as the difference between the expected rates. Our main results are single-letter expressions for the competitive-ratio and the regret, expressed as a max-min or min-max optimization. Several examples illustrate our results and the benefits of the competitive analysis approach to code design.

Finding a computable expression for the feedback capacity of channels with colored Gaussian, additive noise is a long standing open problem. In this paper, we solve this problem in the scenario where the channel has multiple inputs and multiple outputs (MIMO) and the noise process is generated as the output of a time-invariant state-space model. Our main result is a computable expression for the feedback capacity in terms of a finite-dimensional convex optimization. The solution to the feedback capacity problem is obtained by formulating the finite-block counterpart of the capacity problem as a sequential convex optimization problem which leads in turn to a single-letter upper bound. This converse derivation integrates tools and ideas from information theory, control, filtering and convex optimization. A tight lower bound is realized by optimizing over a family of time-invariant policies thus showing that time-invariant inputs are optimal even when the noise process may not be stationary. The optimal time-invariant policy is used to construct a capacity-achieving and simple coding scheme for scalar channels, and its analysis reveals an interesting relation between a smoothing problem and the feedback capacity expression.

We show that the trapdoor channel’s capacity with delayed feedback of two time-instances is given by\begin{equation*}{\text{C}}_2^{{\text{fb}}} = {\log _2}(3/2).\end{equation*}This demonstrates that the feedback capacity degrades sharply even with a single time-instance delay of the channel outputs. The capacity result is established by showing that the delayed feedback capacity can be formulated as a capacity problem with instantaneous feedback and an extended state. Consequently, graph-based methods can be applied to obtain new computable upper and lower bounds on the capacity, which are shown to coincide for the trapdoor channel.

We consider the feedback capacity of a MIMO channel whose channel output is given by a linear state-space model driven by the channel inputs and a Gaussian process. The generality of our state-space model subsumes all previous studied models such as additive channels with colored Gaussian noise, and channels with an arbitrary dependence on previous channel inputs or outputs. The main result is a computable feedback capacity expression that is given as a convex optimization problem subject to a detectability condition. We demonstrate the capacity result on the auto-regressive Gaussian noise channel, where we show that even a single time-instance delay in the feedback reduces the feedback capacity significantly in the stationary regime. On the other hand, for large regression parameters, the feedback capacity can be achieved with delayed feedback. Finally, we show that the detectability condition is satisfied for scalar models and conjecture that it is true for MIMO models.

We propose a new method to compute the feedback capacity of unifilar finite state channels (FSCs) with memory using reinforcement learning (RL). The feedback capacity was previously estimated using its formulation as a Markov decision process (MDP) with dynamic programming (DP) algorithms. However, their computational complexity grows exponentially with the channel alphabet size. Therefore, we use RL, and specifically, its ability to parameterize value functions and policies with neural networks, to evaluate numerically the feedback capacity of channels with a large alphabet size. The outcome of the RL algorithm is a numerical lower bound on the feedback capacity, which is used to reveal the structure of the optimal solution. The structure is modeled by a graph-based auxiliary random variable that is utilized to derive an analytic upper bound on the feedback capacity with the duality bound. The capacity computation is concluded by verifying the tightness of the upper bound by testing whether it is Bahl-Cocke-Jelinek-Raviv (BCJR) invariant. We demonstrate this method on the Ising channel with an arbitrary alphabet size. For an alphabet size smaller than or equal to 8, we derive the analytic solution of the capacity. Next, the structure of the numerical solution is used to deduce a simple coding scheme that achieves the feedback capacity and serves as a lower bound for larger alphabets. For an alphabet size greater than 8, we present an upper bound on the feedback capacity. For an asymptotically large alphabet size, we present an asymptotic optimal coding scheme.

We consider finite-state channels (FSCs) where the channel state is stochastically dependent on the previous channel output. We refer to these as Noisy Output is the STate (NOST) channels. We derive the feedback capacity of NOST channels in two scenarios: with and without causal state information (CSI) available at the encoder. If CSI is unavailable, the feedback capacity is$C_{\text {FB}}= \max _{P(x|y')} I(X;Y|Y')$, while if it is available at the encoder, the feedback capacity is$C_{\text {FB-CSI}}= \max _{P(u|y'),x(u,s')} I(U;Y|Y')$, where$U$is an auxiliary RV with finite cardinality. In both formulas, the output process is a Markov process with stationary distribution. The derived formulas generalize special known instances from the literature, such as where the state is i.i.d. and where it is a deterministic function of the output.$C_{\text {FB}}$and$C_{\text {FB-CSI}}$are also shown to be computable via convex optimization problem formulations. Finally, we present an example of an interesting NOST channel for which CSI available at the encoder does not increase the feedback capacity.

We consider the problem of filtering in linear state-space models (e.g., the Kalman filter setting) through the lens of regret optimization. Specifically, we study the problem of causally estimating a desired signal, generated by a linear state-space model driven by process noise, based on noisy observations of a related observation process. We define a novel regret criterion for estimator design as the difference of the estimation error energies between a clairvoyant estimator that has access to all future observations (a so-called smoother) and a causal one that only has access to current and past observations. The regret-optimal estimator is the causal estimator that minimizes the worst-case regret across all bounded-energy noise sequences. We provide a solution for the regret filtering problem at two levels. First, an horizon-independent solution at the operator level is obtained by reducing the regret to the well-known Nehari problem. Secondly, our main result for state-space models is an explicit estimator that achieves the optimal regret. The regret-optimal estimator is represented as a finite-dimensional state-space whose parameters can be computed by solving three Riccati equations and a single Lyapunov equation. We demonstrate the applicability and efficacy of the estimator in a variety of problems and observe that the estimator has average and worst-case performances that are simultaneously close to their optimal values.

Finding a computable expression for the feedback capacity of channels with non-white Gaussian, additive noise is a long standing open problem. In this paper, we solve this problem in the scenario where the channel has multiple inputs and multiple outputs (MIMO) and the noise process is generated as the output of a state-space model (a hidden Markov model). The main result is a computable characterization of the feedback capacity as a finite-dimensional convex optimization problem. Our solution subsumes all previous solutions to the feedback capacity including the auto-regressive moving-average (ARMA) noise process of first order, even if it is a non-stationary process. The capacity problem can be viewed as the problem of maximizing the measurements' entropy rate of a controlled (policy-dependent) state-space subject to a power constraint. We formulate the finite-block version of this problem as a sequential convex optimization problem, which in turn leads to a single-letter and computable upper bound. By optimizing over a family of time-invariant policies that correspond to the channel inputs distribution, a tight lower bound is realized. We show that one of the optimization constraints in the capacity characterization boils down to a Riccati equation, revealing an interesting relation between explicit capacity formulae and Riccati equations.

We consider the use of the well-known dual capacity bounding technique for deriving upper bounds on the capacity of indecomposable finite-state channels (FSCs) with finite input and output alphabets. In this technique, capacity upper bounds are obtained by choosing suitable test distributions on the sequence of channel outputs. We propose test distributions that arise from certain graphical structures called Q-graphs. As we show in this paper, the advantage of this choice of test distribution is that, for the important sub-classes of unifilar and input-driven FSCs, the resulting upper bounds can be formulated as a dynamic programming (DP) problem, which makes the bounds tractable. We illustrate this for several examples of FSCs, where we are able to solve the associated DP problems explicitly to obtain capacity upper bounds that either match or beat the best previously reported bounds. For instance, for the classical trapdoor channel, we improve the best known upper bound of 0.661 (due to Lutz (2014)) to 0.584, shrinking the gap to the best known lower bound of 0.572, all bounds being in units of bits per channel use.

The stabilization of unstable dynamical systems using rate-limited feedback links is investigated. In the scenario of a constant-rate link and a noise with unbounded support, the fundamental limit of communication is known, but no simple algorithm to achieve it exists. The main challenge in constructing an optimal scheme is to fully exploit the communication resources while occasionally signaling the controller that a special operation needs to be taken due to a large noise observation. In this work, we present a simple and explicit algorithm that stabilizes the dynamical system and achieves the fundamental limits of communication. The new idea is to use a constrained quantizer in which certain patterns of sequences are avoided throughout the quantization process. These patterns are preserved to signal the controller that a zoom-out operation should be initiated due to large noise observation. We show that the constrained quantizer has a negligible effect on the rate, so it achieves the fundamental limit of communication. Specifically, the rate-optimal algorithm is shown to stabilize any β-moment of the state if the noise has a bounded absolute (β + ε)-moment for some ε > 0 regardless of the other noise characteristics.

We consider finite state channels (FSCs) with feedback and state known causally at the encoder. This setting is general and includes both a channel with a Markovian state in which the state is input-independent, but also many other cases where the state is input-dependent such as the energy harvesting model. We characterize the capacity as a multi-letter expression that includes auxiliary random variables with memory. We derive a single-letter computable lower bound based on auxiliary directed graphs that are used to provide an auxiliary structure for the channel outputs and are called Q-graphs. This method is implemented for binary energy-harvesting model with a unitsized battery and the noiseless channel, whose exact capacity has remained an open problem. We identify a structure of Q-graphs, with achievable rates that outperform the best achievable rates known in the literature.

The capacity of unifilar finite-state channels in the presence of feedback is investigated. We derive a new evaluation method to extract graph-based encoders with their achievable rates, and to compute upper bounds to examine their performance. The evaluation method is built upon a recent methodology to derive simple bounds on the capacity using auxiliary directed graphs. While it is not clear whether the upper bound is convex, we manage to formulate it as a convex optimization problem using transformation of the argument with proper constraints. The lower bound is formulated as a non-convex optimization problem, yet, any feasible point to the optimization problem induces a graph-based encoder. In all examples, the numerical results show near-tight upper and lower bounds that can be easily converted to analytic results. For the non-symmetric trapdoor channel and binary fading channels (BFCs), new capacity results are established by computing the corresponding bounds. For all other instances, including the Ising channel, the near-tightness of the achievable rates is shown via a comparison with corresponding upper bounds. Finally, we show that any graph-based encoder implies a simple coding scheme that is based on the posterior matching principle and achieves the lower bound.

In this paper, we propose a novel method to compute the feedback capacity of channels with memory using reinforcement learning (RL). In RL, one seeks to maximize cumulative rewards collected in a sequential decision-making environment. This is done by collecting samples of the underlying environment and using them to learn the optimal decision rule. The main advantage of this approach is its computational efficiency, even in high dimensional problems. Hence, RL can be used to estimate numerically the feedback capacity of unifilar finite state channels (FSCs) with large alphabet size. The outcome of the RL algorithm sheds light on the properties of the optimal decision rule, which in our case, is the optimal input distribution of the channel. These insights can be converted into analytic, single-letter capacity expressions by solving corresponding lower and upper bounds. We demonstrate the efficiency of this method by analytically solving the feedback capacity of the well-known Ising channel with a ternary alphabet. We also provide a simple coding scheme that achieves the feedback capacity.

In this paper, we study the capacity of unifilar finite-state channels. We derive upper bounds that are based on the dual capacity bounding technique using test distributions with memory on directed Q-graphs. The bounds hold for any choice of graph-based test distribution and result in a multi-letter expression. The computability of the upper bound is shown via a novel dynamic programming formulation that can be efficiently evaluated. We further show that the bounds can be simplified to simple single-letter expressions by solving the corresponding Bellman equation explicitly. In particular, for the Ising and Trapdoor channels, we provide simple analytic upper bounds which outperform all previous bounds from the literature.

The multiple access channel (MAC) with degraded message sets and feedback is considered. We show that feedback does not increase the capacity region of this setting, and present a capacity-achieving coding scheme. The coding scheme is inspired by the posterior matching principle for the memoryless channel, but for two transmitters. It is shown that the recursive design of the transmitters and decoder is also maintained in this multiuser setting, leading to a constructive and simple coding scheme. It is interesting to note that the weak transmitter performs its encoding with respect to the decoder's belief as expected, but the strong encoder performs its encoding with respect to the weak encoder's belief and not the decoder's belief. To the best of our knowledge, this is the first matching scheme for a multi-user setting with finite alphabets and feedback.

This paper investigates graph-based encoders for the unifilar finite-state channel (FSC) with feedback. A recent paper introduced the Q-graph as a tool for the recursive quantization of channel outputs on a directed graph. The Q- graph approach yielded single-letter lower and upper bounds on the feedback capacity of unifilar FSCs, termed here Q-LB and Q-UB, respectively. The current paper provides two computable optimization problems for the Q-LB and the Q-UB. The first, for the Q-LB, aims to find the graph-based encoder with the highest achievable rate. Specifically, for a structured cooperation between the encoder and the decoder, that is given by a particular Q-graph, the optimization problem maximizes the Q-LB over all input distributions. The resultant graph-based encoder from the optimization problem has a corresponding posterior matching scheme that achieves the Q-LB. The second optimization problem provides a formulation of the Q-UB as a convex optimization problem. Numerical results of the Q-LB and the Q-UB are presented for the Ising channel and a simplified version of a fading channel. The numerical results are then translated into analytical expressions for graph-based encoders and their achievable rates.

In this paper, a general binary-input binary-output channel is investigated in the presence of feedback and input constraints. The feedback capacity and the optimal input distribution of this setting are calculated for the case of an $(1,\infty )$ -RLL input constraint, that is, the input sequence contains no consecutive ones. These results are obtained via explicit solution of an equivalent dynamic programming optimization problem. A simple coding scheme is designed based on the principle of posterior matching, which was introduced by Shayevitz and Feder for memoryless channels. The posterior matching scheme for our input-constrained setting is shown to achieve capacity using two new ideas: history bits, which captures the memory embedded in our setting, and message-interval splitting, which eases the analysis of the scheme. Additionally, in the special case of an S-channel, we give a very simple zero-error coding scheme that is shown to achieve capacity. For the input-constrained binary symmetric channel, we show using our capacity formula that feedback increases capacity when the cross-over probability is small.

The input-constrained binary erasure channel (BEC) with strictly causal feedback is studied. The channel input sequence must satisfy the (0, k)-runlength limited (RLL) constraint, i.e., no more than k consecutive `0's are allowed. The feedback capacity of this channel is derived for all k ≥ 1, and is given by C(0,k)fb(ε) = max ε̅H2(δ0)+Σi=1k-1(εi+1H2(δi) Πm=0i-1δm)/1+Σi=0k-1(ε̅i+1Πm=0iδm) where ε is the erasure probability, ε̅ = 1 - ε and H2(·) is the binary entropy function. The maximization is only over δk-1, while the parameters δifor i ≤ k - 2 are straightforward functions of δk-1. The lower bound is obtained by constructing a simple coding for all k ≥ 1. It is shown that the feedback capacity can be achieved using zero-error, variable length coding. For the converse, an upper bound on the non-causal setting, where the erasure is available to the encoder just prior to the transmission, is derived. This upper bound coincides with the lower bound and concludes the search for both the feedback capacity and the non-causal capacity. As a result, non-causal knowledge of the erasures at the encoder does not increase the feedback capacity for the (0, k)-RLL input-constrained BEC. This property does not hold in general: the (2, ∞)-RLL input-constrained BEC, where every `1' is followed by at least two `0's, is used to show that the feedback capacity can be strictly smaller than the non-causal capacity.

A binary-input binary-output (BIBO) channel is investigated in the presence of feedback and input constraints. The feedback capacity and the optimal input distribution of this setting are presented for the case where the input sequence contains no consecutive ones. A simple coding scheme is designed based on the principle of posterior matching, which was introduced by Shayevitz and Feder for memoryless channels. The posterior matching scheme for our input-constrained setting is shown to achieve capacity using two new ideas: which captures the memory embedded in the setting, and splitting, which simplifies the scheme analysis. Additionally, in the special case of an S-channel, we give a very simple zero-error coding scheme that achieves capacity.

This paper studies the problem of the distributed compression of correlated sources with an action-dependent joint distribution. This class of problems is, in fact, an extension of the Slepian-Wolf model, but where cost-constrained actions taken by the encoder or the decoder affect the generation of one of the sources. The purpose of this paper is to study the impact of actions on the achievable rates. In particular, two cases where transmission occurs over a rate-limited link are studied; case A for actions taken at the decoder and case B where actions are taken at the encoder. A complete single-letter characterization of the set of achievable rates is given in both cases. Furthermore, a network coding setup for the case where actions are taken at the encoder is investigated. The sources are generated at different nodes of the network and are required at a set of terminal nodes, yet transmission occurs over a general, acyclic, directed network. For this setup, generalized cut-set bounds are derived, and a full characterization of the set of achievable rates using single-letter expressions is provided. For this scenario, random linear network coding is proved to be optimal, even though this is not a classical multicast problem. In addition, two binary examples are investigated and demonstrate how actions taken at different nodes of the system have a significant effect on the achievable rate region, when compared with a naive time-sharing strategy.

A single-letter upper bound on the feedback capacity of a unifilar finite-state channel is derived. The upper bound is tight for all cases where the feedback capacity is known. Its efficiency is also demonstrated by direct application of the bound on the dicode erasure channel, which results in a new capacity result. The bound is based on a new technique, called the Q-contexts mapping, where the channel outputs are recursively quantized to a finite set, called the contexts set.

The input-constrained erasure channel with feedback is considered, where the binary input sequence contains no consecutive ones, i.e., it satisfies the (1, ∞)-RLL constraint. We derive the capacity for this setting, which can be expressed as Cε= max0≤ p≤0.5((1-ε)Hb(p))/(1+(1-ε)p) , where ε is the erasure probability and Hb(·) is the binary entropy function. Moreover, we prove that a priori knowledge of the erasure at the encoder does not increase the feedback capacity. The feedback capacity was calculated using an equivalent dynamic programming (DP) formulation with an optimal average-reward that is equal to the capacity. Furthermore, we obtained an optimal encoding procedure from the solution of the DP, leading to a capacity-achieving, zero-error coding scheme for our setting. DP is, thus, shown to be a tool not only for solving optimization problems, such as capacity calculation, but also for constructing optimal coding schemes. The derived capacity expression also serves as the only non-trivial upper bound known on the capacity of the input-constrained erasure channel without feedback, a problem that is still open.

The input-constrained erasure channel with feedback is considered, where the input sequence contains no consecutive 1's, i.e. the (1, ∞)-RLL constraint. The capacity is calculated using an equivalent dynamic program, which shows that the optimal average reward is equal to the capacity. The capacity can be expressed as Hb(p) Cϵ= max0≤p≤1(Hb(p))/(p+(1/1-ε)) , where ϵ is the erasure probability and Hb(·) is the binary entropy. This capacity also serves as an upper bound on the capacity of the input-constrained erasure channel without feedback, a problem that is still open.

This work studies the problem of distributed compression of correlated sources with an action-dependent joint distribution. This class of problems are in fact extensions of the Slepian-Wolf model, but where cost-constrained actions affect the generation of one of the sources. A network setup is investigated for the case where actions are taken at the encoder. The first source is available at a node in the network, this node can take actions which affect the generation of the other source which is available at different node in the network. Transmission occurs over a general, acyclic, directed network and both sources are required in a set of terminal nodes. The purpose of this work is to study the implications of actions on the set of achievable rates. For this network, generalized cut-set bounds are derived, and a full characterization of the set of achievable rates using single-letter expressions is provided, showing how actions affect the achievable region in a non-trivial manner. Random linear network coding is proved to be optimal in this setup, even though this is not a classical multicast problem. As a special case of this network we study a multi-user setup with two encoders and one decoder, each source is available to one encoder and transmission occurs over rate-limited link. The optimal rate region for this case is characterized, and calculated for a binary example.