Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [it.information-theory]

Questions in Information Theory

207 questions
Filter by
Sorted by
Tagged with
36 views

### Channel Capacity & Dependency Graph

In a communication channel, $\{ X_i \}_{i=1}^n$ are inputs and $\{ Y_i \}_{i=1}^n$ are the corresponding outputs. We represent the dependency relations by a graph with $2n$ nodes (one for each $X_i$ ...
37 views

### Feature selection problem under promise

Are there well used examples of feature selection problem where the problem is defined under certain promise? Let's say the task is to select the minimum number of features such that the mutual ...
1 vote
40 views

### Practical Applications of Information Algebras

I've started reading Information Algebras, Kohlas (the Wikipedia may give you the gist) and I am curious as to whether any ideas from this theory/book could be practically implemented, perhaps as some ...
1 vote
78 views

### Detecting Erroneous Corrections

A block code $C$, with minimum distance $d$ can be used to: Detect $d - 1$ errors Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors However, the above usually assumes that the number of errors that are ...
24 views

### Is it accurate to describe a computer as a dynamic memory state?

is this an accurate statement? And where can I find out more about these topics? At any point in time a computer is holding a memory state. Because the computer is moving in various ways we can call ...
1 vote
122 views

### Relation Between Different Definitions of Information Distance

I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance.&...
100 views

### Maximum theoretical compression ratio for real-valued data

Given a sequence of $N$ real-valued vectors $\mathbf{v_1}, \mathbf{v_2}, ..., \mathbf{v_N}$, each of dimension $d$, do any of the below bounds exist? The minimum number of real-valued vectors of ...
1 vote
41 views

### Why the measure of information complexities for passive and active learning are increasing in research communities?

I am a PhD student working on the theory of active learning. Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
1 vote
121 views

### Information Bottleneck - Calculating the Mutual information between the Labels and the Features [closed]

I am trying to understand the Nonlinear Information Bottlecneck paper along with their implementation, but I am confused as to what is actually being calculated in the Mutual information $(I(Y, M))$ ...
57 views

### Does Co-occurrence Information Differ Qualitatively From Shannon and Algorithmic Information?

In Distributed Computation as Hierarchy Michael Manthey argues that co-occurrence of indistinguishables (critical for quantum theory) supplies spatial information that qualitatively differs from both ...
23k views

### Which is the limit of lossless compression data? (if there exists such a limit)

Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression. So far, the only source I ...
4k views

### Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
990 views

### Can the mutual information of a "cell" be negative?

Please forgive me if this is not the right Stack Exchange (I also posted it at Cross Validated). Please also forgive me for inventing terms. For discrete random variables X and Y, the mutual ...
51 views

### Can information, eg. Shannon Entropy, be considered an absolute value?

This question is a distillation of my question here: How do I calculate the information content of a mass spectrum? Using a theoretical instrument that makes perfect measurements of fundamental ...
1 vote
218 views

### How much information does it take to specify, not each member of a group, but any one member?

It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ ...
65 views

### How do I calculate the information content of a mass spectrum?

Ions in a mass spectrum are represented using two independent values for the mass-to-charge ratio [m/z] of the ion and it's relative abundance. Here's an example for caffeine from HMDB: https://hmdb....
49 views

### Looking for information on Information Theory applied to image pixelation

I'm in seventh grade and am doing a science project about how age and gender affects people's ability to recognize pixelated images. For background research I have been reading about information ...
23 views

### Modelling channels without specifying input alphabets

The standard mathematical model of a communication channel is that of a stochastic matrix $(C(x|a))_{a \in A, x \in X}$, where $A$ is the input alphabet and $X$ the output alphabet. This definition ...
1 vote
214 views

### Uniqueness of the distribution maximizing the channel capacity

Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$....
1 vote
92 views

### Generalizing Fano's inequality

Fano's inequality says the following: Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
182 views

68 views

### meaning of "algorithms that do not resample points" in the algorithms that do not resample points theorem

The No Free Lunch theorems for search and optimization demonstrate that for search/optimization problems in a limited search space, where the points being searched through are not resampled, the ...
1 vote
173 views

### Can theoretical computer science be combined with mechanism and information design and applications in financial markets

I am considering to take a position as a phd student in a computer science department. I am a mathematician with a master degree in finance and my research interests are mainly focused in game theory. ...
260 views

### Maximize the mutual information between 2 discrete random variables

I have two random variables $X$ and $Y$. $X$ follows Poisson-Binomial distribution with parameters $\{q_1, \ldots, q_k\}$. Thus, $X$ can take values in the set $\{0,1,\ldots,k\}$. $Y$ is a binary ...
88 views

### Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
2k views

### Where does the information in a fractal come from?

When I view a fractal such as the Mandelbrot, my first thought is, where did this interesting picture come from. For a picture of this complexity, the information that generated this picture must be ...
160 views

### "Looking for help understanding a proof by Gossner (1998)."

Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
1 vote
113 views

### Does any physical process constitute a "computation"? [closed]

I am trying to sharpen the convex hull of what seems like a (surprisingly) stubborn concept to enclose based on answers here, as well as conversations with others, around the nature of what actually ...
241 views

### Upper bound on the expected number of correct bits via a "lossy compression"

Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm ...
358 views

### Information and Coding Theory Texts

I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...
208 views

### Does this notion of entropy have a name?

Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching ...
3k views

### Efficiently computable variants of Kolmogorov complexity

Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features: It corresponds to an intuition of giving strings with patters or ...
1 vote
56 views

### sophistication or logical depth to detect intelligent extra-terrestrial species

From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
1 vote
127 views

### Deterministic one way communication complexity for message with arbitrary length

Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message. I have been looking into ...
173 views

### Error in entropy properties in Mathematical Theory of Cryptography by Claude E. Shannon

I am reading this classic paper by Claude E. Shannon and I think there may be a couple of errors in his description of the properties of Entropy/Uncertainty. The screenshot shown at the bottom of this ...
446 views

118 views

### Why isn’t information-probability relationship linear? [closed]

I am completely new to information theory. I was learning about information content but couldn’t make sense of why the relationship between information content and probability isn’t linear? And why it ...
226 views

### Converting a Bernoulli to a Gaussian

It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a "...
15 views

### Capacity of spike-based neuronal code

Assume that a neuronal population $A$ is connected to a neuronal population $B$ by a bunch of synapses - one-directional channels that propagate spikes. For simplicity assume that the current ...
201 views

### Generating $k$ random bits from a pdf with entropy $H(p) = k$

All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it. So can we formalize this as follows? Suppose I can only sample from my distribution,...
1 vote
85 views

### Difference between a lossy encoder and a noisy channel in Information Theory

$S \to X \to Y \to \hat{S}$ $\text{source} \to \text{input} \to \text{output} \to \text{target}$ In information theory introductory books, an encoder is usually defined as a deterministic function \$f:\...