On Mon, 27 Mar 2017 12:32:24 +0300, Evgeny Filatov wrote:
> On 25.03.2017 19:12, Tim Wescott wrote:
>>
>> Actually, where Shannon's argument gets lazy is in sticking with the
>> volume argument: I'm trying to plot the cumulative probability density
>> per radius, or at least an approximation. The "volume concentrating"
>> property is valid, and the fact that the cumulative probability
>> function "hardens" with increasing dimension seems to be true, but
>> Shannon's argument about the link between the volume being concentrated
>> on the edge and the cumulative probability function hardening is just
>> hand-waving -- at least in his 1948 paper.
>>
>>
> Wow! For a while I imagined that you were writing a popular article
> about Shannon's theorem and were looking for some simple visual guides.
> But now I see that your goal is actually hacking into it.
<<snip>>
Actually, I _am_ interested in making a popular video about it. I think
that showing a graphic of a cross-section of the spheres, appropriately
scaled, hardening as the dimension gets bigger, will be a powerful way of
explaining why just a few symbols worth of delay in your code doesn't
come close to getting you down to the channel limit, and why there are
codes out there with thousands of symbols of delay.
--
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work! See my website if you're interested
http://www.wescottdesign.com
Reply by Evgeny Filatov●March 27, 20172017-03-27
On 25.03.2017 19:12, Tim Wescott wrote:
>
> Actually, where Shannon's argument gets lazy is in sticking with the
> volume argument: I'm trying to plot the cumulative probability density
> per radius, or at least an approximation. The "volume concentrating"
> property is valid, and the fact that the cumulative probability function
> "hardens" with increasing dimension seems to be true, but Shannon's
> argument about the link between the volume being concentrated on the edge
> and the cumulative probability function hardening is just hand-waving --
> at least in his 1948 paper.
>
Wow! For a while I imagined that you were writing a popular article
about Shannon's theorem and were looking for some simple visual guides.
But now I see that your goal is actually hacking into it.
I'm not sure if that's any help, but have you been possibly looking into
polar codes? They claim to asymptotically achieve the channel capacity;
and in that facility are a valuable object for researchers.
E.g., polar codes are _very_ briefly reviewed in "Trellis and Turbo
Coding" by Schlegel and Perez. A couple of major references from that
book (that I hope to read someday):
Arikan 2009, http://ieeexplore.ieee.org/abstract/document/5075875/
Raymond and Gross 2014, http://ieeexplore.ieee.org/document/6876199/
Gene
Reply by Tim Wescott●March 26, 20172017-03-26
On Sun, 26 Mar 2017 07:28:28 -0400, Randy Yates wrote:
> Tim Wescott <tim@seemywebsite.com> writes:
>
>> Hmm. Brute force, but it might work.
>
> Of course it won't help a bit if you're trying to evaluate it at the
> negative integers..
Not needed. One of the insights that I wanted to share is just how
slowly the spheres harden with increasing dimension, and the
corresponding growth in delay if you want to get really close to
achieving the channel capacity.
--
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work! See my website if you're interested
http://www.wescottdesign.com
Reply by Randy Yates●March 26, 20172017-03-26
Tim Wescott <tim@seemywebsite.com> writes:
> Hmm. Brute force, but it might work.
Of course it won't help a bit if you're trying to
evaluate it at the negative integers..
>
> On Sat, 25 Mar 2017 16:19:17 -0400, Randy Yates wrote:
>
>> Tim,
>>
>> Have you considered using the Gnu MP library to extend the dynamic range
>> of your gamma function?
>>
>> Tim Wescott <seemywebsite@myfooter.really> writes:
>>
>>> So, I'm toying with Shannon's capacity theorem, trying to graph out the
>>> "sphere hardening" effect that he cites as the basis of the principle.
>>>
>>> I can see, intuitively, how the whole notion that the volume of a
>>> sphere is concentrated in a thin shell works, but when I try to
>>> calculate actual numbers I start running into numerical difficulties at
>>> dimensions of around 150 or 200.
>>>
>>> Even with a 150-dimensional sphere, as the sphere radius increases, the
>>> transition in the cumulative probability function of a signal not being
>>> within the sphere vs. the signal being inside the sphere is fairly
>>> gradual.
>>>
>>> I want to make some visual aids that show the sphere hardening up as
>>> the dimensions get higher -- can anyone point me to math for
>>> calculating this that does not involve calculating the gamma function
>>> (which is what's blowing up in my face)?
>>>
>>> Thanks.
>>>
>>> (And yes, this is badly stated -- low blood sugar and a persistent cold
>>> means that right now my fingers are being directed by a large lump of
>>> trembling snot, not a cohesive collection of brain cells. Aim your
>>> "well asked question" gun at this posting and fire away -- I'll try to
>>> clarify as I go.)
Hmm. Brute force, but it might work.
On Sat, 25 Mar 2017 16:19:17 -0400, Randy Yates wrote:
> Tim,
>
> Have you considered using the Gnu MP library to extend the dynamic range
> of your gamma function?
>
> Tim Wescott <seemywebsite@myfooter.really> writes:
>
>> So, I'm toying with Shannon's capacity theorem, trying to graph out the
>> "sphere hardening" effect that he cites as the basis of the principle.
>>
>> I can see, intuitively, how the whole notion that the volume of a
>> sphere is concentrated in a thin shell works, but when I try to
>> calculate actual numbers I start running into numerical difficulties at
>> dimensions of around 150 or 200.
>>
>> Even with a 150-dimensional sphere, as the sphere radius increases, the
>> transition in the cumulative probability function of a signal not being
>> within the sphere vs. the signal being inside the sphere is fairly
>> gradual.
>>
>> I want to make some visual aids that show the sphere hardening up as
>> the dimensions get higher -- can anyone point me to math for
>> calculating this that does not involve calculating the gamma function
>> (which is what's blowing up in my face)?
>>
>> Thanks.
>>
>> (And yes, this is badly stated -- low blood sugar and a persistent cold
>> means that right now my fingers are being directed by a large lump of
>> trembling snot, not a cohesive collection of brain cells. Aim your
>> "well asked question" gun at this posting and fire away -- I'll try to
>> clarify as I go.)
--
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work! See my website if you're interested
http://www.wescottdesign.com
Reply by Randy Yates●March 25, 20172017-03-25
Tim,
Have you considered using the Gnu MP library to extend the
dynamic range of your gamma function?
Tim Wescott <seemywebsite@myfooter.really> writes:
> So, I'm toying with Shannon's capacity theorem, trying to graph out the
> "sphere hardening" effect that he cites as the basis of the principle.
>
> I can see, intuitively, how the whole notion that the volume of a sphere
> is concentrated in a thin shell works, but when I try to calculate actual
> numbers I start running into numerical difficulties at dimensions of
> around 150 or 200.
>
> Even with a 150-dimensional sphere, as the sphere radius increases, the
> transition in the cumulative probability function of a signal not being
> within the sphere vs. the signal being inside the sphere is fairly
> gradual.
>
> I want to make some visual aids that show the sphere hardening up as the
> dimensions get higher -- can anyone point me to math for calculating this
> that does not involve calculating the gamma function (which is what's
> blowing up in my face)?
>
> Thanks.
>
> (And yes, this is badly stated -- low blood sugar and a persistent cold
> means that right now my fingers are being directed by a large lump of
> trembling snot, not a cohesive collection of brain cells. Aim your "well
> asked question" gun at this posting and fire away -- I'll try to clarify
> as I go.)
If you want to avoid the gamma functions, maybe you can just rely on the relationship between volume and surface area, which is simply S=n*V, assuming an n-dimensional ball (and its (n-1)-dimensional spherical surface) with radius 1. The volume in a very thin shell of thickness d is then roughly d*S = d*n*V, which is clearly going to be a bigger fraction of V the larger n gets.
(see e.g. https://en.wikipedia.org/wiki/N-sphere#Volume_and_surface_area for derivation and other possibly useful formulas.)
-Ethan
Reply by ●March 25, 20172017-03-25
On Sat, 25 Mar 2017 11:12:01 -0500, Tim Wescott <tim@seemywebsite.com>
wrote:
>On Sat, 25 Mar 2017 14:13:51 +0300, Evgeny Filatov wrote:
>
>> On 24.03.2017 22:11, Tim Wescott wrote:
>>> So, I'm toying with Shannon's capacity theorem, trying to graph out the
>>> "sphere hardening" effect that he cites as the basis of the principle.
>>>
>>> I can see, intuitively, how the whole notion that the volume of a
>>> sphere is concentrated in a thin shell works, but when I try to
>>> calculate actual numbers I start running into numerical difficulties at
>>> dimensions of around 150 or 200.
>>>
>>> Even with a 150-dimensional sphere, as the sphere radius increases, the
>>> transition in the cumulative probability function of a signal not being
>>> within the sphere vs. the signal being inside the sphere is fairly
>>> gradual.
>>>
>>> I want to make some visual aids that show the sphere hardening up as
>>> the dimensions get higher -- can anyone point me to math for
>>> calculating this that does not involve calculating the gamma function
>>> (which is what's blowing up in my face)?
>>>
>>> Thanks.
>>>
>>> (And yes, this is badly stated -- low blood sugar and a persistent cold
>>> means that right now my fingers are being directed by a large lump of
>>> trembling snot, not a cohesive collection of brain cells. Aim your
>>> "well asked question" gun at this posting and fire away -- I'll try to
>>> clarify as I go.)
>>>
>>>
>> Tim, although I'm lazy and haven't followed the derivation you are
>> looking at, however, I also doesn't seem to grasp your problems. With
>> the risk of stating the obvious, here's how I would approach it.
>>
>> Suppose you have an N-dimensional sphere of radius r, and want to know
>> how much of its volume is concentrated in the outer shell lying between,
>> say, radii (1-alpha)*r and r, where alpha is small.
>>
>> You know that the volume of an N-dimensional sphere of radius r is given
>> by V_N = C_N * r^N, where C_N is some function of N. But since you only
>> need to know the fraction of the total volume occupied by the outer
>> shell, you don't even need to know C_N, because it's canceled off (along
>> with r):
>>
>> [ V_N(r) - V_N((1-alpha)*r) ] / V_N(r) = 1 - (1-alpha)^n
>>
>> Which could be further simplified, assuming alpha << 1, as 1 -
>> exp(-alpha*N).
>>
>> I've plotted the fraction of the outer shell volume to the total sphere
>> volume for alpha = 0.01, just to see the approximation is fair:
>>
>> http://i.imgur.com/nkyaPh4.png
>
>Actually, where Shannon's argument gets lazy is in sticking with the
>volume argument: I'm trying to plot the cumulative probability density
>per radius, or at least an approximation. The "volume concentrating"
>property is valid, and the fact that the cumulative probability function
>"hardens" with increasing dimension seems to be true, but Shannon's
>argument about the link between the volume being concentrated on the edge
>and the cumulative probability function hardening is just hand-waving --
>at least in his 1948 paper.
Heresy!
;)
This sort of thing is partly why I personally like the practical
approach better.
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
Reply by Tim Wescott●March 25, 20172017-03-25
On Sat, 25 Mar 2017 14:13:51 +0300, Evgeny Filatov wrote:
> On 24.03.2017 22:11, Tim Wescott wrote:
>> So, I'm toying with Shannon's capacity theorem, trying to graph out the
>> "sphere hardening" effect that he cites as the basis of the principle.
>>
>> I can see, intuitively, how the whole notion that the volume of a
>> sphere is concentrated in a thin shell works, but when I try to
>> calculate actual numbers I start running into numerical difficulties at
>> dimensions of around 150 or 200.
>>
>> Even with a 150-dimensional sphere, as the sphere radius increases, the
>> transition in the cumulative probability function of a signal not being
>> within the sphere vs. the signal being inside the sphere is fairly
>> gradual.
>>
>> I want to make some visual aids that show the sphere hardening up as
>> the dimensions get higher -- can anyone point me to math for
>> calculating this that does not involve calculating the gamma function
>> (which is what's blowing up in my face)?
>>
>> Thanks.
>>
>> (And yes, this is badly stated -- low blood sugar and a persistent cold
>> means that right now my fingers are being directed by a large lump of
>> trembling snot, not a cohesive collection of brain cells. Aim your
>> "well asked question" gun at this posting and fire away -- I'll try to
>> clarify as I go.)
>>
>>
> Tim, although I'm lazy and haven't followed the derivation you are
> looking at, however, I also doesn't seem to grasp your problems. With
> the risk of stating the obvious, here's how I would approach it.
>
> Suppose you have an N-dimensional sphere of radius r, and want to know
> how much of its volume is concentrated in the outer shell lying between,
> say, radii (1-alpha)*r and r, where alpha is small.
>
> You know that the volume of an N-dimensional sphere of radius r is given
> by V_N = C_N * r^N, where C_N is some function of N. But since you only
> need to know the fraction of the total volume occupied by the outer
> shell, you don't even need to know C_N, because it's canceled off (along
> with r):
>
> [ V_N(r) - V_N((1-alpha)*r) ] / V_N(r) = 1 - (1-alpha)^n
>
> Which could be further simplified, assuming alpha << 1, as 1 -
> exp(-alpha*N).
>
> I've plotted the fraction of the outer shell volume to the total sphere
> volume for alpha = 0.01, just to see the approximation is fair:
>
> http://i.imgur.com/nkyaPh4.png
Actually, where Shannon's argument gets lazy is in sticking with the
volume argument: I'm trying to plot the cumulative probability density
per radius, or at least an approximation. The "volume concentrating"
property is valid, and the fact that the cumulative probability function
"hardens" with increasing dimension seems to be true, but Shannon's
argument about the link between the volume being concentrated on the edge
and the cumulative probability function hardening is just hand-waving --
at least in his 1948 paper.
--
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work! See my website if you're interested
http://www.wescottdesign.com