Probing Capacity

Himanshu Asnani, Haim H. Permuter, Tsachy Weissman

TL;DR

This paper introduces the concept of Probing Capacity, which characterizes the maximum rate of reliable communication when both the transmitter and receiver must pay a "cost" to acquire channel state information. The authors demonstrate a surprising "cut-off" phenomenon: in many scenarios, an encoder can achieve the maximum possible communication rate by probing only a small fraction of the channel states, rather than monitoring them constantly.

What Problem Does This Paper Address?

In traditional information theory, channel state information (CSI)—knowledge about the environment's impact on a signal—is typically assumed to be either perfectly known or completely unknown. However, in real-world systems like wireless sensors or satellite links, acquiring CSI isn't free; it requires energy, bandwidth, or time.

The authors address the gap between theoretical "free" information and practical "costly" information. They model the acquisition of CSI as a series of actions taken by the encoder (transmitter) and decoder (receiver). By imposing a cost constraint on these actions, they seek to find the optimal balance: how should a system spend its limited "probing budget" to maximize the data transmission rate?

Methods

The authors utilize a Discrete Memoryless Channel (DMC) framework where the channel state sequence is i.i.d. (independent and identically distributed). The core of their approach involves:

  • Action-Dependent Probing: The encoder chooses whether to "probe" the state based on the message it wants to send. Similarly, the decoder can take actions based on the channel output it receives.
  • Cost Constraints: They define a cost function $\Lambda(A)$ for actions and a total budget $\Gamma$. The system must stay within this budget on average.
  • Information-Theoretic Mapping: A key contribution is proving an equivalence between this "probing" framework and previous models of "channels with action-dependent states." This allows them to leverage and extend existing capacity theorems to their new setting.
  • Coding Schemes: They employ techniques like Rate-Splitting and Multiplexing to achieve capacity. For example, the encoder might split a message into two parts: one that dictates the probing action and another that carries the actual data.
The system model where the encoder takes actions to observe partial state information.

Datasets

As a theoretical information theory paper, no external datasets were used. The authors evaluated their findings using several canonical numerical examples:

  • Binary State Channels: Simple models with "on/off" states.
  • Dirty Paper Coding (DPC): A continuous channel model where the state represents known interference.
  • Fading Channels: Modeling wireless environments where signal strength fluctuates.

Key Insights and Ideas

  • The "To Observe or Not to Observe" Trade-off: The paper formalizes the intuition that you don't always need to know everything about the channel to communicate effectively.
  • The Cut-off Phenomenon: Perhaps the most striking insight is that the capacity-vs-cost curve often flattens out. In one binary example, probing only 20% of the states allowed the system to reach the same capacity as probing 100% of the time. This suggests significant potential for energy savings in sensor networks.
  • Sub-optimality of Naive Time-Sharing: A common engineering approach is "time-sharing"—randomly choosing to probe or not. The authors prove that their joint coding and probing strategy is strictly superior to simple time-sharing.
  • Decoder Probing as a Relay Problem: They show that when the decoder takes actions to acquire state information, the problem becomes mathematically equivalent to a relay channel with "infinite lookahead," a complex but well-studied problem in network information theory.
The generalized model where both the encoder and decoder take actions to acquire state information.

Key Results

  • Capacity Characterization: The authors provide exact mathematical formulas (Theorems 1, 2, and 4) for the Probing Capacity under various conditions (encoder-only probing, causal vs. non-causal information, and joint encoder-decoder probing).
  • Numerical Verification: In a "Learning to Write on Dirty Paper" scenario, the proposed power-splitting scheme significantly outperformed the time-sharing bound, especially at low probing budgets.
  • Fading Channels: For fading channels with adaptive power control, they demonstrated that even a small amount of encoder probing (informed by the decoder) leads to substantial gains in achievable rate compared to having no encoder CSI.

Limitations and Future Work

The authors acknowledge several open questions:

  • Memory: The current work assumes i.i.d. states. Real-world channels often have "memory" (states are correlated over time), which would significantly complicate the action logic.
  • Past-Dependent Actions: What happens if the decision to probe now depends on what we learned from probing in the past? This feedback loop could potentially increase capacity further.
  • Sampling vs. Feedback: The authors suggest exploring the trade-offs between taking actions to sample the state versus taking actions to receive feedback from the other end of the link.

Summary updated

Abstract

We consider the problem of optimal probing of states of a channel by transmitter and receiver for maximizing rate of reliable communication. The channel is discrete memoryless (DMC) with i.i.d. states. The encoder takes probing actions dependent on the message. It then uses the state information obtained from probing causally or noncausally to generate channel input symbols. The decoder may also take channel probing actions as a function of the observed channel output and use the channel state information thus acquired, along with the channel output, to estimate the message. We refer to the maximum achievable rate for reliable communication for such systems as the “Probing Capacity”. We characterize this capacity when the encoder and decoder actions are cost constrained. To motivate the problem, we begin by characterizing the trade-off between the capacity and fraction of channel states the encoder is allowed to observe, while the decoder is aware of channel states. In this setting of `to observe or not to observe' state at the encoder, we compute certain numerical examples which exhibit a pleasing phenomenon, where encoder can observe a relatively small fraction of states and yet communicate at maximum rate, i.e., rate when observing states at encoder is not cost constrained.
BibTeX
@article{asnani2011probing,
  author = {Himanshu Asnani and Haim H. Permuter and Tsachy Weissman},
  title = {{Probing Capacity}},
  journal = {IEEE Trans. Information Theory},
  year = {2011},
  doi = {10.1109/tit.2011.2162089},
}

Loading related content...

Figure