Entropy of an infinite sequence?
up vote
0
down vote
favorite
Does an infinite sequence always have finite entropy? For example, doesn't $a_n=n$, the sequence of non-negative integers, have very low entropy? It feels like all "well-defined" sequences ought to have low entropy because there's very little surprise about the next element.
sequences-and-series information-theory entropy
|
show 2 more comments
up vote
0
down vote
favorite
Does an infinite sequence always have finite entropy? For example, doesn't $a_n=n$, the sequence of non-negative integers, have very low entropy? It feels like all "well-defined" sequences ought to have low entropy because there's very little surprise about the next element.
sequences-and-series information-theory entropy
1
In what sense are you assigning entropy to a sequence? I am writing an answer assuming that the sequence is representative of a string of outputs of a random process (and as such, the entropy of such a process is independent of the order of the symbols involved).
– probably_someone
Nov 18 at 16:38
@probably_someone I don't exactly know. It feels like the entropy of a system is related to how "difficult" it is to describe it in closed form. So I think anything you write will be helpful for my understanding
– Matt Thomas
Nov 18 at 16:48
It might be useful to familiarize yourself with what the quantitative definition of entropy actually is, then. The Wikipedia page has a decent treatment of it.
– probably_someone
Nov 18 at 16:49
1
Depends on what question you're trying to ask, and what your definition of a "system" is. The quantitative definition of entropy involves the output of a stochastic process, i.e. one that exhibits random behavior and is described by a set of probabilities of producing a particular output. If this does not describe what you think a system is, then entropy may not be the quantity that describes what you want to measure.
– probably_someone
Nov 18 at 17:32
1
Your example of $a_n = n$ suggests the concept that you want is closer to Kolmogorov complexity (en.wikipedia.org/wiki/Kolmogorov_complexity). This is finite for any computable sequence but you might regard it as being infinite for all uncomputable sequences.
– Qiaochu Yuan
Nov 18 at 21:44
|
show 2 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Does an infinite sequence always have finite entropy? For example, doesn't $a_n=n$, the sequence of non-negative integers, have very low entropy? It feels like all "well-defined" sequences ought to have low entropy because there's very little surprise about the next element.
sequences-and-series information-theory entropy
Does an infinite sequence always have finite entropy? For example, doesn't $a_n=n$, the sequence of non-negative integers, have very low entropy? It feels like all "well-defined" sequences ought to have low entropy because there's very little surprise about the next element.
sequences-and-series information-theory entropy
sequences-and-series information-theory entropy
asked Nov 18 at 16:21
Matt Thomas
1666
1666
1
In what sense are you assigning entropy to a sequence? I am writing an answer assuming that the sequence is representative of a string of outputs of a random process (and as such, the entropy of such a process is independent of the order of the symbols involved).
– probably_someone
Nov 18 at 16:38
@probably_someone I don't exactly know. It feels like the entropy of a system is related to how "difficult" it is to describe it in closed form. So I think anything you write will be helpful for my understanding
– Matt Thomas
Nov 18 at 16:48
It might be useful to familiarize yourself with what the quantitative definition of entropy actually is, then. The Wikipedia page has a decent treatment of it.
– probably_someone
Nov 18 at 16:49
1
Depends on what question you're trying to ask, and what your definition of a "system" is. The quantitative definition of entropy involves the output of a stochastic process, i.e. one that exhibits random behavior and is described by a set of probabilities of producing a particular output. If this does not describe what you think a system is, then entropy may not be the quantity that describes what you want to measure.
– probably_someone
Nov 18 at 17:32
1
Your example of $a_n = n$ suggests the concept that you want is closer to Kolmogorov complexity (en.wikipedia.org/wiki/Kolmogorov_complexity). This is finite for any computable sequence but you might regard it as being infinite for all uncomputable sequences.
– Qiaochu Yuan
Nov 18 at 21:44
|
show 2 more comments
1
In what sense are you assigning entropy to a sequence? I am writing an answer assuming that the sequence is representative of a string of outputs of a random process (and as such, the entropy of such a process is independent of the order of the symbols involved).
– probably_someone
Nov 18 at 16:38
@probably_someone I don't exactly know. It feels like the entropy of a system is related to how "difficult" it is to describe it in closed form. So I think anything you write will be helpful for my understanding
– Matt Thomas
Nov 18 at 16:48
It might be useful to familiarize yourself with what the quantitative definition of entropy actually is, then. The Wikipedia page has a decent treatment of it.
– probably_someone
Nov 18 at 16:49
1
Depends on what question you're trying to ask, and what your definition of a "system" is. The quantitative definition of entropy involves the output of a stochastic process, i.e. one that exhibits random behavior and is described by a set of probabilities of producing a particular output. If this does not describe what you think a system is, then entropy may not be the quantity that describes what you want to measure.
– probably_someone
Nov 18 at 17:32
1
Your example of $a_n = n$ suggests the concept that you want is closer to Kolmogorov complexity (en.wikipedia.org/wiki/Kolmogorov_complexity). This is finite for any computable sequence but you might regard it as being infinite for all uncomputable sequences.
– Qiaochu Yuan
Nov 18 at 21:44
1
1
In what sense are you assigning entropy to a sequence? I am writing an answer assuming that the sequence is representative of a string of outputs of a random process (and as such, the entropy of such a process is independent of the order of the symbols involved).
– probably_someone
Nov 18 at 16:38
In what sense are you assigning entropy to a sequence? I am writing an answer assuming that the sequence is representative of a string of outputs of a random process (and as such, the entropy of such a process is independent of the order of the symbols involved).
– probably_someone
Nov 18 at 16:38
@probably_someone I don't exactly know. It feels like the entropy of a system is related to how "difficult" it is to describe it in closed form. So I think anything you write will be helpful for my understanding
– Matt Thomas
Nov 18 at 16:48
@probably_someone I don't exactly know. It feels like the entropy of a system is related to how "difficult" it is to describe it in closed form. So I think anything you write will be helpful for my understanding
– Matt Thomas
Nov 18 at 16:48
It might be useful to familiarize yourself with what the quantitative definition of entropy actually is, then. The Wikipedia page has a decent treatment of it.
– probably_someone
Nov 18 at 16:49
It might be useful to familiarize yourself with what the quantitative definition of entropy actually is, then. The Wikipedia page has a decent treatment of it.
– probably_someone
Nov 18 at 16:49
1
1
Depends on what question you're trying to ask, and what your definition of a "system" is. The quantitative definition of entropy involves the output of a stochastic process, i.e. one that exhibits random behavior and is described by a set of probabilities of producing a particular output. If this does not describe what you think a system is, then entropy may not be the quantity that describes what you want to measure.
– probably_someone
Nov 18 at 17:32
Depends on what question you're trying to ask, and what your definition of a "system" is. The quantitative definition of entropy involves the output of a stochastic process, i.e. one that exhibits random behavior and is described by a set of probabilities of producing a particular output. If this does not describe what you think a system is, then entropy may not be the quantity that describes what you want to measure.
– probably_someone
Nov 18 at 17:32
1
1
Your example of $a_n = n$ suggests the concept that you want is closer to Kolmogorov complexity (en.wikipedia.org/wiki/Kolmogorov_complexity). This is finite for any computable sequence but you might regard it as being infinite for all uncomputable sequences.
– Qiaochu Yuan
Nov 18 at 21:44
Your example of $a_n = n$ suggests the concept that you want is closer to Kolmogorov complexity (en.wikipedia.org/wiki/Kolmogorov_complexity). This is finite for any computable sequence but you might regard it as being infinite for all uncomputable sequences.
– Qiaochu Yuan
Nov 18 at 21:44
|
show 2 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
I think it makes sense if the terms of your series are all positive and the series converges.
For example if $A=sum_{n=1}^infty a_n$, then you can define the probability distribution $p_n=a_n/A$. Hence, using the entropy definition $S=-sum_{n=1}^infty p_nln p_n$, which is the standard definition of statistical mechanics divided by the Boltzmann constant $k_B$. For example, we could define then the entropy of Riemann's zeta function $zeta(s)=sum_{n=1}^inftyfrac{1}{n^s}$. Using the probability distribution $p_n(s)=1/(zeta(s)n^s)$, we obtain the "entropy" of the
zeta function:
begin{align}
S(s) &= frac{1}{zeta(s)}sum_{n=1}^inftyfrac{1}{n^s}ln(zeta(s)n^s)=lnzeta(s)+frac{s}{zeta(s)}sum_{n=1}^inftyfrac{ln n}{n^s}=lnzeta(s)-frac{s}{zeta(s)}zeta'(s)\
&=lnzeta(s)-sfrac{dlnzeta(s)}{ds}
end{align}
This is called the zeta distribution.
See here:
https://en.wikipedia.org/wiki/Zeta_distribution
Another example is the Poisson distribution, which you can obtain from the
expansion of $e^{lambda t}$. The probability distribution you get from this
is $p_n=frac{e^{-lambda t}(lambda t)^n}{n!}$.
add a comment |
up vote
1
down vote
Your question is a little vague.
In the context of the Shannon entropy, one natural and usual measure of the "rate of information" of an infinite sequence (more aptly: of a discrete time stochastic process) is the entropy rate:
$$H_r = lim_{nto infty} frac{H(X_1,X_2 , cdots H_n)}{n}$$
... if the limit exists, of course. Notice also that this is not the information of a single full sequence, but a normalized expected value.
Typically, if $H_r >0$, then the entropy of the infinite sequence is also infinite.
In particular, if the sequence is produced by a stationary memoryless source (independent symbols with stationary distribution) then $H(X_1,X_2 , cdots H_n)=n H(X_1)$ and $H_r = H(X_1)$
A little more general: for a stationary first order Markov process, $H_r = H(X_2 mid X_1)$
If each symbol is totally predictable from the previous one, then $H_r=0$.
In your case, your sequence is not only predictable but also deterministic, hence $H_r=0$
This is not the end of the story, though. Because the Shannon entropy requires a probabilistic setting, and sometimes that does not seem very adequate. The typical example: which is the entropy rate of $X_n=$ digits of the decimal expansion of $pi$?
For an alternative approach to defining the "average information" of a sequence (and hence some alternative "entropy"), using an operational (computational) instead of probabilistic setting, you might look into Kolmogorov complexity
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I think it makes sense if the terms of your series are all positive and the series converges.
For example if $A=sum_{n=1}^infty a_n$, then you can define the probability distribution $p_n=a_n/A$. Hence, using the entropy definition $S=-sum_{n=1}^infty p_nln p_n$, which is the standard definition of statistical mechanics divided by the Boltzmann constant $k_B$. For example, we could define then the entropy of Riemann's zeta function $zeta(s)=sum_{n=1}^inftyfrac{1}{n^s}$. Using the probability distribution $p_n(s)=1/(zeta(s)n^s)$, we obtain the "entropy" of the
zeta function:
begin{align}
S(s) &= frac{1}{zeta(s)}sum_{n=1}^inftyfrac{1}{n^s}ln(zeta(s)n^s)=lnzeta(s)+frac{s}{zeta(s)}sum_{n=1}^inftyfrac{ln n}{n^s}=lnzeta(s)-frac{s}{zeta(s)}zeta'(s)\
&=lnzeta(s)-sfrac{dlnzeta(s)}{ds}
end{align}
This is called the zeta distribution.
See here:
https://en.wikipedia.org/wiki/Zeta_distribution
Another example is the Poisson distribution, which you can obtain from the
expansion of $e^{lambda t}$. The probability distribution you get from this
is $p_n=frac{e^{-lambda t}(lambda t)^n}{n!}$.
add a comment |
up vote
1
down vote
I think it makes sense if the terms of your series are all positive and the series converges.
For example if $A=sum_{n=1}^infty a_n$, then you can define the probability distribution $p_n=a_n/A$. Hence, using the entropy definition $S=-sum_{n=1}^infty p_nln p_n$, which is the standard definition of statistical mechanics divided by the Boltzmann constant $k_B$. For example, we could define then the entropy of Riemann's zeta function $zeta(s)=sum_{n=1}^inftyfrac{1}{n^s}$. Using the probability distribution $p_n(s)=1/(zeta(s)n^s)$, we obtain the "entropy" of the
zeta function:
begin{align}
S(s) &= frac{1}{zeta(s)}sum_{n=1}^inftyfrac{1}{n^s}ln(zeta(s)n^s)=lnzeta(s)+frac{s}{zeta(s)}sum_{n=1}^inftyfrac{ln n}{n^s}=lnzeta(s)-frac{s}{zeta(s)}zeta'(s)\
&=lnzeta(s)-sfrac{dlnzeta(s)}{ds}
end{align}
This is called the zeta distribution.
See here:
https://en.wikipedia.org/wiki/Zeta_distribution
Another example is the Poisson distribution, which you can obtain from the
expansion of $e^{lambda t}$. The probability distribution you get from this
is $p_n=frac{e^{-lambda t}(lambda t)^n}{n!}$.
add a comment |
up vote
1
down vote
up vote
1
down vote
I think it makes sense if the terms of your series are all positive and the series converges.
For example if $A=sum_{n=1}^infty a_n$, then you can define the probability distribution $p_n=a_n/A$. Hence, using the entropy definition $S=-sum_{n=1}^infty p_nln p_n$, which is the standard definition of statistical mechanics divided by the Boltzmann constant $k_B$. For example, we could define then the entropy of Riemann's zeta function $zeta(s)=sum_{n=1}^inftyfrac{1}{n^s}$. Using the probability distribution $p_n(s)=1/(zeta(s)n^s)$, we obtain the "entropy" of the
zeta function:
begin{align}
S(s) &= frac{1}{zeta(s)}sum_{n=1}^inftyfrac{1}{n^s}ln(zeta(s)n^s)=lnzeta(s)+frac{s}{zeta(s)}sum_{n=1}^inftyfrac{ln n}{n^s}=lnzeta(s)-frac{s}{zeta(s)}zeta'(s)\
&=lnzeta(s)-sfrac{dlnzeta(s)}{ds}
end{align}
This is called the zeta distribution.
See here:
https://en.wikipedia.org/wiki/Zeta_distribution
Another example is the Poisson distribution, which you can obtain from the
expansion of $e^{lambda t}$. The probability distribution you get from this
is $p_n=frac{e^{-lambda t}(lambda t)^n}{n!}$.
I think it makes sense if the terms of your series are all positive and the series converges.
For example if $A=sum_{n=1}^infty a_n$, then you can define the probability distribution $p_n=a_n/A$. Hence, using the entropy definition $S=-sum_{n=1}^infty p_nln p_n$, which is the standard definition of statistical mechanics divided by the Boltzmann constant $k_B$. For example, we could define then the entropy of Riemann's zeta function $zeta(s)=sum_{n=1}^inftyfrac{1}{n^s}$. Using the probability distribution $p_n(s)=1/(zeta(s)n^s)$, we obtain the "entropy" of the
zeta function:
begin{align}
S(s) &= frac{1}{zeta(s)}sum_{n=1}^inftyfrac{1}{n^s}ln(zeta(s)n^s)=lnzeta(s)+frac{s}{zeta(s)}sum_{n=1}^inftyfrac{ln n}{n^s}=lnzeta(s)-frac{s}{zeta(s)}zeta'(s)\
&=lnzeta(s)-sfrac{dlnzeta(s)}{ds}
end{align}
This is called the zeta distribution.
See here:
https://en.wikipedia.org/wiki/Zeta_distribution
Another example is the Poisson distribution, which you can obtain from the
expansion of $e^{lambda t}$. The probability distribution you get from this
is $p_n=frac{e^{-lambda t}(lambda t)^n}{n!}$.
edited Nov 20 at 12:12
answered Nov 20 at 2:01
minmax
48518
48518
add a comment |
add a comment |
up vote
1
down vote
Your question is a little vague.
In the context of the Shannon entropy, one natural and usual measure of the "rate of information" of an infinite sequence (more aptly: of a discrete time stochastic process) is the entropy rate:
$$H_r = lim_{nto infty} frac{H(X_1,X_2 , cdots H_n)}{n}$$
... if the limit exists, of course. Notice also that this is not the information of a single full sequence, but a normalized expected value.
Typically, if $H_r >0$, then the entropy of the infinite sequence is also infinite.
In particular, if the sequence is produced by a stationary memoryless source (independent symbols with stationary distribution) then $H(X_1,X_2 , cdots H_n)=n H(X_1)$ and $H_r = H(X_1)$
A little more general: for a stationary first order Markov process, $H_r = H(X_2 mid X_1)$
If each symbol is totally predictable from the previous one, then $H_r=0$.
In your case, your sequence is not only predictable but also deterministic, hence $H_r=0$
This is not the end of the story, though. Because the Shannon entropy requires a probabilistic setting, and sometimes that does not seem very adequate. The typical example: which is the entropy rate of $X_n=$ digits of the decimal expansion of $pi$?
For an alternative approach to defining the "average information" of a sequence (and hence some alternative "entropy"), using an operational (computational) instead of probabilistic setting, you might look into Kolmogorov complexity
add a comment |
up vote
1
down vote
Your question is a little vague.
In the context of the Shannon entropy, one natural and usual measure of the "rate of information" of an infinite sequence (more aptly: of a discrete time stochastic process) is the entropy rate:
$$H_r = lim_{nto infty} frac{H(X_1,X_2 , cdots H_n)}{n}$$
... if the limit exists, of course. Notice also that this is not the information of a single full sequence, but a normalized expected value.
Typically, if $H_r >0$, then the entropy of the infinite sequence is also infinite.
In particular, if the sequence is produced by a stationary memoryless source (independent symbols with stationary distribution) then $H(X_1,X_2 , cdots H_n)=n H(X_1)$ and $H_r = H(X_1)$
A little more general: for a stationary first order Markov process, $H_r = H(X_2 mid X_1)$
If each symbol is totally predictable from the previous one, then $H_r=0$.
In your case, your sequence is not only predictable but also deterministic, hence $H_r=0$
This is not the end of the story, though. Because the Shannon entropy requires a probabilistic setting, and sometimes that does not seem very adequate. The typical example: which is the entropy rate of $X_n=$ digits of the decimal expansion of $pi$?
For an alternative approach to defining the "average information" of a sequence (and hence some alternative "entropy"), using an operational (computational) instead of probabilistic setting, you might look into Kolmogorov complexity
add a comment |
up vote
1
down vote
up vote
1
down vote
Your question is a little vague.
In the context of the Shannon entropy, one natural and usual measure of the "rate of information" of an infinite sequence (more aptly: of a discrete time stochastic process) is the entropy rate:
$$H_r = lim_{nto infty} frac{H(X_1,X_2 , cdots H_n)}{n}$$
... if the limit exists, of course. Notice also that this is not the information of a single full sequence, but a normalized expected value.
Typically, if $H_r >0$, then the entropy of the infinite sequence is also infinite.
In particular, if the sequence is produced by a stationary memoryless source (independent symbols with stationary distribution) then $H(X_1,X_2 , cdots H_n)=n H(X_1)$ and $H_r = H(X_1)$
A little more general: for a stationary first order Markov process, $H_r = H(X_2 mid X_1)$
If each symbol is totally predictable from the previous one, then $H_r=0$.
In your case, your sequence is not only predictable but also deterministic, hence $H_r=0$
This is not the end of the story, though. Because the Shannon entropy requires a probabilistic setting, and sometimes that does not seem very adequate. The typical example: which is the entropy rate of $X_n=$ digits of the decimal expansion of $pi$?
For an alternative approach to defining the "average information" of a sequence (and hence some alternative "entropy"), using an operational (computational) instead of probabilistic setting, you might look into Kolmogorov complexity
Your question is a little vague.
In the context of the Shannon entropy, one natural and usual measure of the "rate of information" of an infinite sequence (more aptly: of a discrete time stochastic process) is the entropy rate:
$$H_r = lim_{nto infty} frac{H(X_1,X_2 , cdots H_n)}{n}$$
... if the limit exists, of course. Notice also that this is not the information of a single full sequence, but a normalized expected value.
Typically, if $H_r >0$, then the entropy of the infinite sequence is also infinite.
In particular, if the sequence is produced by a stationary memoryless source (independent symbols with stationary distribution) then $H(X_1,X_2 , cdots H_n)=n H(X_1)$ and $H_r = H(X_1)$
A little more general: for a stationary first order Markov process, $H_r = H(X_2 mid X_1)$
If each symbol is totally predictable from the previous one, then $H_r=0$.
In your case, your sequence is not only predictable but also deterministic, hence $H_r=0$
This is not the end of the story, though. Because the Shannon entropy requires a probabilistic setting, and sometimes that does not seem very adequate. The typical example: which is the entropy rate of $X_n=$ digits of the decimal expansion of $pi$?
For an alternative approach to defining the "average information" of a sequence (and hence some alternative "entropy"), using an operational (computational) instead of probabilistic setting, you might look into Kolmogorov complexity
edited Nov 20 at 14:14
answered Nov 19 at 23:29
leonbloy
39.8k645106
39.8k645106
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003742%2fentropy-of-an-infinite-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
In what sense are you assigning entropy to a sequence? I am writing an answer assuming that the sequence is representative of a string of outputs of a random process (and as such, the entropy of such a process is independent of the order of the symbols involved).
– probably_someone
Nov 18 at 16:38
@probably_someone I don't exactly know. It feels like the entropy of a system is related to how "difficult" it is to describe it in closed form. So I think anything you write will be helpful for my understanding
– Matt Thomas
Nov 18 at 16:48
It might be useful to familiarize yourself with what the quantitative definition of entropy actually is, then. The Wikipedia page has a decent treatment of it.
– probably_someone
Nov 18 at 16:49
1
Depends on what question you're trying to ask, and what your definition of a "system" is. The quantitative definition of entropy involves the output of a stochastic process, i.e. one that exhibits random behavior and is described by a set of probabilities of producing a particular output. If this does not describe what you think a system is, then entropy may not be the quantity that describes what you want to measure.
– probably_someone
Nov 18 at 17:32
1
Your example of $a_n = n$ suggests the concept that you want is closer to Kolmogorov complexity (en.wikipedia.org/wiki/Kolmogorov_complexity). This is finite for any computable sequence but you might regard it as being infinite for all uncomputable sequences.
– Qiaochu Yuan
Nov 18 at 21:44