#itila

[itwasallsohazy]

So people threw gold at itila to make him go away. Why can't people do this to me?

[thebidden]

Life in high-dimensional spaces (ITILA)

Points that are uniformly distributed in a sphere in N-space, where N is large, are likely to be near the surface.

The volume of a sphere in n-space is $V_Nr^N$ where $V_N$ is the appropriate constant for each N.  ($k_2$ is $\pi$, $k_3$ is $\frac43\pi$, $k_4$ is $\frac12\pi^2$)

In exercise 2.20, MacKay asks the reader to determine what portion of a n-sphere is near the surface, if the points are evenly distributed.  This is just the volume of a sphere of radius $r$, minus the volume of a sphere of radius $r-\epsilon$, divided by the volume of the first sphere, or $\frac{V_Nr^N - V_N(r-\epsilon)^N}{V_Nr^N}$

Everything associated with $V_Nr^N$ drops out, leaving $\frac{r^N-(r-\epsilon)^N}{r^N}$, this simplifies to $1 - (1 - \frac\epsilon r)^N$.

MacKay asks the reader to calculate this faction for three values of $N$ - 2, 10 and 1,000; and two values of $\frac\epsilon r$ - 0.01 and 0.5.

I wrote a short Python program to calculate these.  The source code is here.

Results:

2 dimensions, e/r = 0.01; fraction = 0.0199

2 dimensions, e/r = 0.5; fraction = 0.75

10 dimensions, e/r = 0.01; fraction = 0.0956179249912

10 dimensions, e/r = 0.5; fraction = 0.9990234375

1000 dimensions, e/r = 0.01; fraction = 0.999956828753

1000 dimensions, e/r = 0.5; fraction = 1.0

[thebidden]

MacKay's ITILA: Exercise 2.16 - 100 dice

Exercise 2.16 asks the reader to calculate the probability distribution of 100 ordinary dice throws, sketch the distribution and calculate the mean and standard deviation.

From the central limit theorem, the distribution is roughly normal (although discrete).  It's easy to estimate the expected value, variance and standard deviation.

$E[100 dice] = 100 E[1 die] = 100 [\frac72] = 350$

$Var[100 dice] = 100 Var[1 die] = 100 [\frac{35}{12}] = 291\frac23$

$Std Dev[100 dice] = \sqrt{Var[100 dice]} = \sqrt{291\frac23} \approx 17.078$

What does the probability distribution look like?  Here's a sketch:

Source code to generate this using pylab is here:

[thebidden]

MacKay's ITILA: Exercise 1.4

As background, Mackay introduces the (7,4) Hamming Code, and shows that the because the Hamming coee is linear, it can be written in matrices.  The transmitted codeword $t$ is obtained from the source $s$ by a linear operation, $t = G^{T}s$ where $G$ is the generator matrix of the code.

$G^{T} = \begin{bmatrix} 1 & 0 & 0 & 0\\\ 0 & 1 & 0 & 0 \\\ 0 & 0 & 1 & 0 \\\ 0 & 0 & 0 & 1 \\\1 & 1 & 1 & 0 \\\ 0 & 1 & 1 & 1 \\\ 1 & 0 & 1 & 1\end{bmatrix}$

The encoding operation uses modular arithmetic: 1 + 1 = 0, 0 + 1 = 1

$G^T$ is a the identity matrix $I_4$ set with a matrix $P$ (the bottom three rows of $G^T$).  $G^T = \begin{bmatrix} I_4 \\\ P\end{bmatrix}$.

Defining $H$, the parity-check matrix: $H = \begin{bmatrix}P & I_3\end{bmatrix}$

Exercise 1.4 asks the student to confirm that all the codewords $t = G^{T}s$ satisfy $Ht = \begin{bmatrix} 0 \\\ 0 \\\ 0\end{bmatrix}$.

I did this in Python using NumPy to handle matrices, writing functions to multiply and add matrices using the modular arithmetic approach mentioned above (presumably someone else has already written these with error handling, but I couldn't find them quickly), and another one to handle syndrome decoding.  The source code is here.  The source code also solves Exercise 1.5 and also addresses Exercise 1.8 (though 1.8 is addressed in an ugly way).

[thebidden]

MacKay's Introduction to Information Theory, Inference and Learning Algorithms

Working my way through this.  Purchased the text, which is also available online at http://www.inference.phy.cam.ac.uk/mackay/itila/book.html.  I'm going to post my answers to questions which aren't answered in the book on this site.  May take me a while to do it.