Questions tagged [entropy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
530 views

Entropy and Information Gain for multi attributes

Is there any way that for specific dataset I can measure entropy and information gain for two or more attributes together? Let's say we have the following dataset: $\begin{array}{cccccc|c} x1 & ...
user avatar
  • 51
0 votes
0 answers
72 views

Is it possible for a [futuristic] computer to contain the information of the whole universe?

(This is a question of information theory, data compression and entropy, so I believe it fits CS forum) Does the fact that the computer itself is a part of the universe make it logically impossible ...
user avatar
  • 71
1 vote
0 answers
136 views

What is the relationship between entropy rate and quantization?

I have a totally random source of signal data that looks like a typical normal distribution. I've included an image as I like pictures:- The source has a mean of 0, and a standard deviation of 1. ...
user avatar
  • 1,582
1 vote
0 answers
162 views

Compression of gaussian variables

Say I have 2 Gaussian sources X and Y. They are generated with mutivariate gaussian distribution with ...
user avatar
  • 21
1 vote
1 answer
307 views

Higher order empirical entropy is not the entropy of the empirical distribution?

Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $...
user avatar
  • 984
0 votes
1 answer
334 views

Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?

I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved). I have a set X of 4 bit source vectors called x. They all have ...
user avatar
  • 127
3 votes
1 answer
130 views

Finding the dichotomy that maximizes information gain for a classifier?

Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let $$H(C) = H(C, \Omega, P) = ...
user avatar
  • 374
3 votes
1 answer
257 views

Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $...
user avatar
  • 374
2 votes
1 answer
190 views

Can Von Neumann bit extraction be made more efficient?

I want to develop a previous question regarding Von Neumann debiasing /randomness extraction. The typical solution (as posted) is to take pairs of throws and output a bit based on a comparison of ...
user avatar
  • 1,582
2 votes
1 answer
170 views

Kraft's inequality and Shannon's noiseless coding theorem for an encoding

A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley. Does there exist a compact instantaneous binary encoding ...
user avatar
  • 91
1 vote
0 answers
82 views

Approximate conditional entropy

Given a set of random variables $X = \{x_1, x_2, \dots, x_n\}$. If the conditional entropy for all $Y \subset X - \{X_i\}$ where $|Y| \leq 5$. How to approximate conditional entropy when $|Y| = 10$ ...
user avatar
  • 19
3 votes
1 answer
125 views

Extracting Randomness from Mouse Acceleration

I'm working on trying to make an "entropy pool" that will be fed as input into an RNG (as in, ex, Fortuna). In order to do so, I need to take various collected data and extract as much entropy as ...
user avatar
  • 751
0 votes
1 answer
90 views

Numerical example of theoretical diff file size using Kullback Leibler?

I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ Wikipedia. Can anyone point me to a numerical example of ...
user avatar
  • 1,582
7 votes
2 answers
218 views

How best to statistically verify random numbers?

Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the ...
user avatar
4 votes
2 answers
230 views

Measuring the information of a document?

I'd like to measure how much information a document $D$ contains. Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know ...
user avatar
1 vote
0 answers
121 views

Can file entropy be predictable?

I am working on some lossless compression topic and looking on any resources or prior studies on lossless file entropy predictability. Assuming we know type of the file (we can tell its belongs to ...
user avatar
  • 111
1 vote
2 answers
54 views

Amount of information in scaled-down images

Does an image that is scaled down lose more Information when calculating averages of pixels rather than selecting single pixels? One way to scale down an image is to replace 2x2 pixel blocks with ...
user avatar
  • 111
1 vote
0 answers
120 views

Find minimum conditional entropy

Task : Given $X$ random variables. Find out the minimum conditional entropy for a variable $x_i \in X$ when $x_i$ is conditioned upon any combination $k$ remaining variables. Find $min(Entropy (x_i | ...
user avatar
5 votes
1 answer
2k views

Computing Von Neumann Entropy Efficiently

The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as ...
user avatar
  • 5,722
12 votes
2 answers
2k views

Is there a generalization of Huffman Coding to Arithmetic coding?

In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional ...
user avatar
  • 6,061
1 vote
0 answers
51 views

Approach to data compression with unknown patterns [closed]

Let's say I have a file with symbols of an alphabet [0,N-1], N around 50. The actual data is a file with a lot of lines, each containing 100 of these symbols. I want to compress this data. By doing a ...
user avatar
3 votes
1 answer
89 views

Maximum entropy probability distribution among Solomonoff priors

If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words. But, the pmf isn't completely determined until we fix a universal Turing ...
user avatar
  • 315
3 votes
2 answers
589 views

How to extract randomness from a file?

I have a generator of files with approximately 7 bits /byte entropy. The files are about 30KB each in length. I'd like to use these as sources of entropy to generate random numbers. Theoretically I ...
user avatar
  • 1,582
10 votes
1 answer
3k views

How to practically measure entropy of a file?

I'm trying to measure now much non redundant (actual) information my file contains. Some call this the amount of entropy. Of course there is the standard p(x) log{p(x)}, but I think that Shannon was ...
user avatar
  • 1,582
3 votes
2 answers
911 views

Why Shannon's Entropy is said to be a measure of information?

I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need ...
user avatar
  • 339
13 votes
4 answers
8k views

Compression of Random Data is Impossible?

A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
user avatar
2 votes
1 answer
131 views

Entropy notation: What does this mean?

If you look at page 13 of the lecture slides here there is this line $H(Y) = H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha))$ I don't really understand what the term on right hand side is. At first I ...
user avatar
  • 171
2 votes
1 answer
45 views

Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new ...
user avatar
  • 121
2 votes
1 answer
200 views

Is a very long plain text password harder to crack than a short complicated password? [closed]

Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters?
user avatar
6 votes
1 answer
1k views

Mutual information intuition

I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent. ...
user avatar
  • 183
0 votes
0 answers
82 views

Entropy of residuals and noise

Relation of Entropy and SNR : Based on this question and answer, I had another question that struck me and I am curious to know, if somebody can shed some light, on the following situation: $y= ...
user avatar
21 votes
2 answers
6k views

How does an operating system create entropy for random seeds?

On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random ...
user avatar
2 votes
1 answer
268 views

Relationship between message entropy and complexity of the best algorithm

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages? E.g. linear search problem. We have an ordered set of incomparable ...
user avatar
5 votes
1 answer
403 views

Conceptual question about entropy and information

Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
user avatar
3 votes
0 answers
143 views

How to compare conditional entropy and mutual information?

I am solving a problem of information theory. The problem reads, Consider a stationary memoryless channel specified by the channel matrix $T = \begin{pmatrix}1-q&q\\r&1-r\end{pmatrix}$. ...
user avatar
  • 131
32 votes
7 answers
2k views

Is there a connection between the halting problem and thermodynamic entropy?

Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem. A TM is an abstract concept of a machine (or engine if ...
user avatar
  • 929
40 votes
7 answers
5k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
user avatar
6 votes
1 answer
1k views

Showing that the entropy of i.i.d. random variables is the sum of entropies

The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\{\sigma_{1},...,\sigma_{k}\}$) is given by $H(Y)=-\sum\limits_{i=1}^{k}P(Y=\sigma_{i})\;\log(P(Y=\sigma_{i}))$. For a ...
user avatar
  • 984
7 votes
2 answers
2k views

Compressing normally distributed data

Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
user avatar
4 votes
0 answers
375 views

Is there a relationship between graph entropy and node entropy?

Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of ...
user avatar
  • 141
5 votes
2 answers
849 views

Estimate entropy, based upon observed frequency counts

Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the ...
user avatar
  • 140k
5 votes
2 answers
543 views

How do computers compute?

This is a kind of follow-up to a question I asked on superuser, where I asked for the definitions of a 'distinghuisable state' and a 'memory cell'. My questions where properly answered, but I was ...
user avatar
  • 151
10 votes
1 answer
2k views

Constrainted Optimization Problem in Matrix Entropy

I have a constrainted optimization problem in the (Shannon) matrix entropy $\mathtt{(sum(entr(eig(A))))}$. The matrix $A$ can be written as the sum of rank 1 matrices of the form $[v_i\,v_i^T]$ where $...
user avatar
  • 103
0 votes
1 answer
273 views

Notions of information content and randomness of binary square matrix

We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings. For ...
user avatar
18 votes
2 answers
960 views

What's harder: Shuffling a sorted deck or sorting a shuffled one?

You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (...
user avatar
  • 4,009
7 votes
1 answer
739 views

Shannon Entropy to Min-Entropy

In many papers I've read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the ...
user avatar
  • 123
5 votes
1 answer
2k views

Pointwise mutual information vs. Mutual information?

I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. ...
user avatar
  • 305
3 votes
1 answer
1k views

Why is the Shannon entropy 0.94 in this example?

Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$. I must find the ...
user avatar
  • 1,547
2 votes
1 answer
197 views

Increasing entropy of random walk

Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by $$H(\pi)=-\sum_{v \in ...
user avatar
  • 283
9 votes
1 answer
1k views

Rényi entropy at infinity or min-entropy

I'm reading a paper that refers to the limit as n goes to infinity of Rényi entropy. It defines it as ${{H}_{n}}\left( X \right)=\dfrac{1}{1-n} \log_2 \left( \sum\limits_{i=1}^{N}{p_{i}^{n}} \right)$. ...
user avatar