Sunday, January 11, 2015

My Solution to Decrypting a Ciphertext from Allan Poe's The Gold-Bug

The following ciphertext came from Edgar Allan Poe's The Gold-Bug.

53‡‡†305))6*;4826)4‡.)4‡);806*;48†8
¶60))85;;]8*;:‡*8†83(88)5*†;46(;88*96
*?;8)*‡(;485);5*†2:*‡(;4956*2(5*—4)8
¶8*;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡
1;48†85;4)485†528806*81(‡9;48;(88;4
(‡?34;48)4‡;161;:188;‡?;

It was generated using a simple substitution algorithm. It is nothing new, but I tried solving it without looking at a known solution.

To decrypt this message, try using the relative frequencies of the letters. The relative frequencies of the letters are as follows (letter frequency): 

8 0.167
; 0.132
4 0.093
) 0.078
‡ 0.074
* 0.069
5 0.059
6 0.054
( 0.044
† 0.039
1 0.034
0 0.029
2 0.025
9 0.025
3 0.020
: 0.020
? 0.015
¶ 0.010
. 0.005
— 0.005
] 0.005

The most frequently occurring letter in English is e. Therefore, assume that one of
8, ;, and 4 
stands for e.

ee is among the most common repeated letters. Therefore, try using the counts of
88, ;;, and 44: 

88 5
;; 1
44 0

Given the counts, assume
8 stands for e. 

Replace
8 by e, 
and the text now looks as follows:

53‡‡†305))6*the26)h‡.)h‡)te06*the†e
¶60))e5tt]e*t:‡*e†e3(ee)5*†th6(tee*96
*?te)*‡(the5)t5*†2:*‡(th956*2(5*—h)e
¶e*th0692e5)t)6†e)h‡‡t1(‡9the0e1te:e‡
1the†e5th)he5†52ee06*e1(‡9thet(eeth
(‡?3hthe)h‡t161t:1eet‡?t

The second most frequently occurring letter in English is t. Therefore, assume that one of
; and 4 
stands for t.

The most frequently occurring trigram in English is "the." Therefore, try using the counts of trigrams starting with
; or 4 
and ending with e:

;4e 7
;ee 1
;(e 1
;]e 1
4)e 1

Given the counts, assume
; stands for t and 4 stands for h. 

Replace
; by t and by h, 
and the text now looks as follows:

53‡‡†305))6*;h826)h‡.)h‡);806*;h8†8
¶60))85;;]8*;:‡*8†83(88)5*†;h6(;88*96
*?;8)*‡(;h85);5*†2:*‡(;h956*2(5*—h)8
¶8*;h069285);)6†8)h‡‡;1(‡9;h8081;8:8‡
1;h8†85;h)h85†528806*81(‡9;h8;(88;h
(‡?3h;h8)h‡;161;:188;‡?;

Based on English letter frequencies,
), ‡, *, 5, and 6 
are likely to stand for a, o, i, n, s, or r (sorted by frequency). Moreover, excluding th, he, and er, the most frequently occurring digrams in English are in and an, both of which end with n. Therefore, try finding the letter standing for n. To do so, try using the counts of digrams containing only
), ‡, *, 5, and 6: 

6* 5
5* 3
5) 3
)) 2
*‡ 2
‡‡ 2
)6 2
...(each of the rest has only one count) 

Given the counts and letter frequencies, assume
* stands for n, 6 stands for i, and 5 stands for a. 

Replace
* by n, 6 by i, and 5 by a, 
and the text now looks as follows:

a3‡‡†30a))inthe2i)h‡.)h‡)te0inthe†e
¶i0))eatt]ent:‡ne†e3(ee)an†thi(teen9i
n?te)n‡(thea)tan†2:n‡(th9ain2(an—h)e
¶enth0i92ea)t)i†e)h‡‡t1(‡9the0e1te:e‡
1the†eath)hea†a2ee0ine1(‡9thet(eeth
(‡?3hthe)h‡t1i1t:1eet‡?t

Excluding the, tha, and ent, the most frequently occurring trigram in English is "and." Therefore, try using the counts of trigrams starting with an to find the letter standing for d:

an† 2
an— 1

d's relative frequency in English text is approximately 0.043. Therefore, assume
† stands for d. 

Replace
† by d, 
and the text now looks as follows:

a3‡‡d30a))inthe2i)h‡.)h‡)te0inthede
¶i0))eatt]ent:‡nede3(ee)andthi(teen9i
n?te)n‡(thea)tand2:n‡(th9ain2(an—h)e
¶enth0i92ea)t)ide)h‡‡t1(‡9the0e1te:e‡
1thedeath)heada2ee0ine1(‡9thet(eeth
(‡?3hthe)h‡t1i1t:1eet‡?t

Go back to the list of
), ‡, *, 5, and 6 
and a, o, i, n, s, and r. Remove
*, 5, and 6 
and a, i, and n.
) and ‡ 
are likely to stand for o, s, or r. Among o, s, and r, o is often seen in pairs, and so is s, while r is not. Therefore, try using the counts of
)) and ‡‡: 

)) 2
‡‡ 2

Given the counts, assume that none of
) and ‡ 
stands for r.

Look at the first time when
)) or ‡‡ 
occurs:

a3‡‡d30a... 

Assume the first a is an article. Given
‡‡d, 
assume
‡ stands for o 
instead of s.

Replace
‡ by o and ) by s, 
and the text now looks as follows (with guessed spaces):

a 3ood 30ass in the 2isho.shoste0 in the de
¶i0sseatt]ent:onede3(ees and thi(teen9i
n?tesno(th east and 2:no(th9ain2(an—hse
¶enth0i92 east side shoot 1(o9the0e1te:eo
1 the deaths head a2ee0ine1(o9thet(eeth
(o?3h the shot 1i1t:1eeto?t

Look at
...thi(teen9i... 
Assume
thi(teen 
stands for thirteen - assume
( stands for r. 

Replace
( by r, 
and the text now looks as follows (with guessed spaces):

a 3ood 30ass in the 2isho.shoste0 in the de
¶i0sseatt]ent:onede3rees and thirteen 9i
n?tes northeast and 2: north 9ain2ran—hse
¶enth0i92 east side shoot 1ro9the0e1te:eo
1 the deaths head a2ee0ine1ro9thetreeth
ro?3h the shot 1i1t:1eeto?t

The most frequently occurring digram in English whose letters have not both be found is ou. Try using the counts of digrams starting with o:

o9 2
o? 2
o1 1
o. 1

Assume one of
9 or ? 
stands for u. Look at
...9ain2ran—hse... 
It is highly unlikely that
9 stands for u. 
Therefore, assume
? stands for u. 

Replace
? by u, 
and the text now looks as follows(with guessed spaces):

a 3ood 30ass in the 2isho.shoste0 in the de
¶i0sseatt]ent:onede3rees and thirteen 9inutes
northeast and 2: north 9ain2ran—hse
¶enth0i92 east side shoot 1ro9 the 0e1te:eo
1 the deaths head a2ee0ine1ro9 the
tree throu3h the shot 1i1t:1eetout

Look at
...throu3h... 
Assume
throu3h 
stands for through - assume
3 stands for g. 

Replace
3 by g, 
and the text now looks as follows (with guessed spaces):

a good g0ass in the 2isho.shoste0 in the de
¶i0sseatt]ent:one degrees and thirteen 9inutes
northeast and 2: north 9ain2ran—hse
¶enth0i92 east side shoot 1ro9the0e1te:eo1
the deaths head a2ee0ine1ro9
the tree through the shot 1i1t:1eetout

Look at
...9inutes... 
Assume
9inutes
stands for minutes - assume
9 stands for m. 

Replace
9 by m, 
and the text now looks as follows (with guessed spaces):

a good g0ass in the 2isho.shoste0 in the
de¶i0s seat t]ent: one degrees and thirteen minutes
northeast and 2: north main2ran—hse
¶enth0im2 east side shoot 1romthe0e1te:eo1
the deaths head a2ee0ine1rom
the tree through the shot 1i1t:1eetout

Look at
...one degrees... 
Based on grammar, assume some part of
t]ent: one
stands for a number. Assume it stands for twenty-one (- not included in the text) - assume
] stands for w and : stands for y. 

Replace
] by w and : by y, 
and the text now looks as follows (with guessed spaces):

a good g0ass in the 2isho.shoste0 in the
de¶i0s seat twentyone degrees and thirteen minutes
northeast and 2y northmain2ran—hse
¶enth0im2 east side shoot 1rom the 0e1t eye o1
the deaths head a2ee0ine 1rom
the tree through the shot 1i1ty1eetout

Assume
1rom 
stands for from - assume
1 stands for f. 
Replace
1 by f, 
and the text now looks as follows (with guessed spaces):

a good g0ass in the 2isho.shoste0 in the
de¶i0s seat twentyone degrees and thirteen minutes
northeast and 2y north main2ran—hse
¶enth0im2 east side shoot from the 0eft eye of
the deaths head a2ee0ine from
the tree through the shot fifty feet out

Assume
0eft 
stands for left - assume
0 stands for l. 
Replace
0 by l, 
and the text now looks as follows (with guessed spaces):

a good glass in the 2isho.shostel in the
de¶ils seat twentyone degrees and thirteen minutes
northeast and 2y north main 2ran—hse
¶enthlim2 east side shoot from the left eye of
the deaths head a2eeline from
the tree through the shot fifty feet out

Assume
de¶ils 
stands for devils - assume
¶ stands for v. 
Replace
¶ by v, 
and the text now looks as follows (with guessed spaces):

a good glass in the 2isho.shostel in the
devils seat twentyone degrees and thirteen minutes
northeast and 2y north main 2ran—h seventh
lim2 east side shoot from the left eye of
the deaths head a2eeline from
the tree through the shot fifty feet out

Given that there is "eye" in the text,
lim2 
is likely to stand for limb. Therefore, assume
2 stands for b. 

Replace
2 by b, 
and the text now looks as follows (with guessed spaces):

a good glass in the bisho.s hostel in the
devils seat twentyone degrees and thirteen minutes
northeast and by north main bran—h seventh
limb east side shoot from the left eye of
the deaths head a bee line from
the tree through the shot fifty feet out

Assume
bisho.s stands for bishops 
and
bran—h stands for branch - 
assume
. stands for p and — stands for c. 

Replace
. by p and — by c, 
and we obtain the decoded message:

A good glass in the bishop's hostel in the devil's seat twenty-one degrees and thirteen minutes northeast and by north main branch seventh limb east side shoot from the left eye of the death's head a bee line from the tree through the shot fifty feet out. 

Wednesday, April 9, 2014

MOOC Review: Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital

by Kuei-Ti Lu

Course Name:
Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital
Link:
https://www.coursera.org/course/images
Institution:
Duke University
Instructor:
Guillermo Sapiro

-----

I took a digital image processing course in my undergraduate study before taking this course, and this might affect how I view this course. Still, I learned more about partial differential equations (PDEs) in this course, which I had barely touched before taking this class.

Video Lectures:

The lengths of the videos varied. In the longer ones, there were often reminders of suggested break time, which were good for those who had little idea when to take a break.

Most materials were about the basic concepts, but in later part of the course, more math was was introduced. The math was more like optional materials considering little coverage of it in the quizzes. The materials covered spatial processing, image restoration, image segmentation, and image/video compression, which were the main topics for a typical image processing course. (Frequency domain processing was almost not mentioned at all.)

In addition to these common topics, geometric PDEs, image/video inpainting, and sparse modeling were touched. These required advanced math, but a student can skip these topics and still obtain the certificate for the course. However, those who had no trouble with math might find these materials good introductions to more advanced areas of studies.

At the end of the course was a brief introduction to medical imaging, which should be an interesting topic. Little technical material was covered for this topic (which is reasonable due to the nature of the field).

Quizzes:

The quiz problems were on the basic concepts, instead of the technical details, covered in the lectures. Multiple attempts could be made without penalty, and a student should be able to complete them without much technical background. The exceptions were those on PDEs, which required at least some qualitative analysis ability.

MATLAB:

Inside the quizzes, one could find optional programming exercises. These did not count toward the grade but could serve as good exercises. One could obtain a special edition of MATLAB for free for a limited period of time to work on these exercises (or simply play around with MATLAB, given the purpose was legal). These resources should be good for those who wanted to enhance their MATLAB skills.

Difficulty:

Except the PDEs, the course should be easy unless one was too far from having some technical knowledge.

Overall:

The course could serve as a survey on the digital image/video processing field. Students who wanted to learn more could also find resources through this course.

Miscellaneous:

One of the suggested textbooks was one I used when I took the digital image processing course in my undergraduate study. I read part of the textbook at that time and read more when taking this course. The textbook provides much detail for the first half of the course. It also has some topics not covered in this course.

Monday, March 31, 2014

MOOC Review: Computational Neuroscience

by Kuei-Ti Lu

Course Name: 
Computational Neuroscience
Link: 
https://www.coursera.org/course/compneuro
Institution: 
University of Washington
Instructors: 
Rajesh P. N. Rao, Adrienne Fairhall

-----

Videos: 

The total length of the videos per week was typical for a MOOC, but the breadth was large - the subject was interdisciplinary. The first week was an introduction to neurobiology; biology and chemistry were the main focus. However, the following weeks were mainly on mathematical/statistical models in neuroscience. Some of these involved signal processing; some information theory; some machine learning; and etc. Week 5 involved modeling neurons using circuits, which are mainly used in electrical engineering.

Because of the variety of the areas covered, one must have solid mathematics basics to understand the materials. Derivations beyond the prerequisites were done in the lectures, and only simple models were covered in the course.

The instructors spoke clearly, and slides as well as subtitles were provided. Following the lectures should not be a big issue for most students (provided that they have met the prerequisites).

Homework Quizzes: 

The quizzes followed the main topics in the videos. Some MATLAB programming was used for a few problems. For most such problems, one might have to read the comments in the code provided to know what code to write to meet the formats of the variables given by the code provided. Other than that, the programming part should not be difficult.

Supplementary Materials: 

Additional materials about the topics could be found (in the formats of texts, videos, and etc.). Moreover, math tutorials were provided by a community TA. so that people who had to learn or review the math used in the course had resources. MATLAB tutorials could also be found.

Difficulty: 

The difficulties might vary a lot for people of different backgrounds. For those from math, statistics, sciences, and engineering, most materials should not be problems. For those from biology and chemistry, this course might be quite challenging due to the math used in the course but not typically used in most areas in undergraduate biology and chemistry.

Overall: 

The course was a survey on computational neuroscience. The breadth of the topics was large, and therefore, those who liked to learn more in depth had to find other resources. Nevertheless, this course should serve as a good introduction. The course might also be interesting to those who like to apply math to different areas.

Saturday, March 22, 2014

MOOC Review: Introduction to Databases

by Kuei-Ti Lu

Course Name:
Introduction to Databases
Link:
https://class.stanford.edu/courses/Engineering/db/2014_1/about
Institution:
Stanford University
Instructor:
Jennifer Widom

-----

Before taking this course, I had learned SQL, and I took MongoDB for Java Developers when taking this course. The review might be influenced by these backgrounds.

Videos:

The lectures covered a broad range of topics related to databases. Some of them involved languages dealing with data, including SOL. The professor mainly used examples to teach the languages and their features. This teaching method should be good for those who learn better by example. For those who prefer learning by reading, just like me, the subtitle should help. Code was provided, and main points about each piece of code were given, too. Therefore, it was easy to refer to the code (instead of hurting eyes with code in the videos).

When explaining the examples, the professor introduced features of the languages and sometimes their weird phenomena. The flow of the examples was organized.

The professor's pronunciations were clear but maybe a little fast to those who were not familiar with English. Still, it should be easy to listen to what she said. (For those who needed help with English, check the subtitle.)

Some areas changed rapidly with time, so the professor simply covered the classic parts that should not change much. In the videos, she also noted which area might change. These helped students be aware of possible evolution of the database field.

Quizzes:

The quizzes covered the concepts covered in the videos. The questions usually changed per attempt. Most of them required using multiple concepts but were not beyond the lectures' levels.

Exercises:

The exercises required using the languages covered in the lectures. There were core sets and challenge sets. The core sets required applying the main concepts covered in the lectures while the challenge ones required applying the advanced concepts covered and extra knowledge (that could be found online). They were not difficult, given the difficulties of the lectures. However, one had to pay attention to the type of environment and features supported (such as Postgres v.s. MySQL). Such difference was covered in the lectures, which was good.

Exams:

The exam questions were like those in the quizzes and multiple-choice versions of the exercises. The length was more than needed (for a typical student). It was good for those who preferred doing problems slowly.

Difficulty:

Although there were lots of topics covered, given the materials covered in the lectures, the course was not difficult. Little related background was needed, but one definitely had to have clear logic.

Miscellaneous:

There were staff and other students helping on the discussion forums - help was available.

Optional readings could be found - good for the reading-type learners.

Overall:

Videos and online assessments were combined well in this course, supplementing each other. The level of detail covered in the materials was just right and self-contained. Extra learning materials, such as extra problems and readings, could be found on the website. The quality of the course, in my opinion, was high.

Sunday, March 16, 2014

MOOC Review: Cryptography I

Course Name:
Cryptography I
Link:
https://www.coursera.org/course/crypto
Institution:
Stanford University
Instructor:
Dan Boneh

-----

Some Personal Experience:

I have taken this course twice. The last time was in 2012, when I was still working toward my Bachelor's degree. I was busy with the schoolwork and had little time working on the course, but I still tried to at least learn the concepts. I did not complete any programming assignment except one and did not take the final. The result is:

The above is the certificate for the session back that time. Although the result met my personal goal at that time, it can clearly be seen that improvement can be made.

As a result, I took the course again. The result looks more brilliant than that in 2012. This time, I completed all programming assignments and took the final. The percentage I got for the course is now 91.7 %, with distinction (the new certificate can be found at https://drive.google.com/folderview?id=0B53jbj-6Ew8QNEtMbDJUbUdfSlk&usp=sharing).

Lectures:

The lectures for the two sessions I have taken are similar. The materials covered are similar. Ciphers (including some stream ciphers and block ciphers) and attacks were introduced. How to and how not to use the ciphers, as well as why, were covered. Some message integrity mechanisms were introduced, which were combined with block ciphers for authenticated encryption. Attacks on message integrity and incorrect use of authenticated encryption mechanisms were covered.

The flow for the ciphers and attacks was quite similar through the course, so it was easy to get used to the lecture flow. Something more out of the flow was the introduction to the number theory that would be used for public key encryption, which certainly could not follow the mechanism-attack flow (because the number theory is not a cipher at all).

The most difficult part, in my opinion, was the math involved, especially the number theory, but math is almost always cute in my opinion, so I did not have any issue with it throughout the course.

As for the professor, his pronunciation was clear, so with the captions, there was no issue for me to get what he said.

There were lecture slides to view online or download, which is convenient for visual learners.

Problem Sets and Final:

The problems sets included both multiple choice and non-multiple-choice problems. Usually, math was used to examine security of certain usages of ciphers. The problems usually required thinking (instead of simply memorizing and pick). However, since they were based on the lectures, it was not difficult to answer them if one understands well the materials covered.

The types of problems in the final was similar to those in the problem sets.

Programming Assignments:

They extended from the lectures. Most were about attacking (virtually) on something that was known broken in terms of security. One could choose the language he/she liked for the assignments. For the number theory programming assignment, some special algorithms were the tasks. The programming assignments, like the problem sets, were not difficult if one understands the materials covered. The instruction sometimes contained useful information. The most tricky part, in my opinion, was familiarizing oneself with the libraries of the language used. (DO NOT implement your own cipher.) However, using the Internet to find the documentation and other informational articles or discussions, one should be able to use those libraries in terms of completing the assignments.

For the number theory programming assignment, I used Java to make use of BigInteger class and encountered one issue, which I solved (I wrote about this in another article: http://csdspnest.blogspot.com/2014/03/bigintegersqrt.html).

Discussion Forums:

As in other MOOCs, discussion forums are often helpful. There were other students sharing useful information such as proving certain probability in the lectures that the professor did not prove in the lectures.

Summary:

The course was not very different from other MOOCs in terms of teaching methods. The video quality and quality of materials were fine.

(I do not recommend this course to anyone who does not have any programming knowledge unless the person does not plan to complete the programming assignments.)

Friday, March 14, 2014

Compute the Inverse Gamma PDF, CDF, and iCDF in MATLAB Using Built-In Functions for the Gamma Distribution

I wrote about computing the inverse Gamma PDF and CDF in MATLAB using the known formula. For something I am working on, I have to compute the inverse CDF (iCDF) for the inverse Gamma distribution, which is not an easy task. As a result, I was thinking about using the built-in gampdf, gamcdf, and gaminv functions to compute the inverse Gamma PDF, CDF, and iCDF.

PDF


Given a random variable (RV) Y ~ Gamma(a, 1/b), define the transformation
$g(Y) = 1/Y$
and let
$X = g(Y) = 1/Y$.

Based on the definitions, X ~ Inv-Gamma(a, b). Because the transformation is invertible, the PDF for X, denoted by
$P_{X}(x)$ 
can be represented using the PDF for Y, denoted by 
$P_{Y}(y)$: 
$P_{X}(x) = \frac1{|dx/dy|}P_{Y}(y)\large|_{y = g^{-1}(x)}$. 
This leads to
$P_{X}(x) = y^2P_{Y}(y)\large|_{y = g^{-1}(x)} = P_{Y}(\frac1x)/x^2$. 

Therefore, in MATLAB, the inverse Gamma PDF for x for a shape parameter a and scale parameter b can be computed using gampdf(y,a,1/b)./(x.^2), or gampdf(1./x,a,1/b)/(x.^2).

A function can be created for this so that the similar code does not have to be rewritten every time when computing the PDF:

function [ Y ] = inversegampdfgam( X,A,B )
%inversegampdfgam Inverse gamma probability density function.
%   Y = inversegampdfgam(X,A,B) returns the inverse gamma probability
%   density function with shape and scale parameters A and B, respectively,
%   at the values in X.

%Y = B^A/gamma(A)*X.^(-A-1).*exp(-B./X);
Y = gampdf(1./X,A,1/B)./(X.^2);

end

Compare the results with those from computing the inverse Gamma PDF directly by finding the absolute difference:


In the figure above, the vertical axis represents the absolute difference between the results obtained using the formula and those obtained using gampdf. It can be seen that the difference is small (possibly resulting from estimation) and negligible.

CDF


Given a random variable (RV) Y ~ Gamma(a, 1/b), let
$X = 1/Y$.
Based on the definitions, X ~ Inv-Gamma(ab). 

For X ≤ x, it follows that 1/Y ≤ 1/y, which leads to y ≤ Y. As a result, the probability for X ≤ x is equal to that of y ≤ Y. Therefore, the CDF for an inverse Gamma distribution can be computed using the iCDF for a Gamma distribution. In MATLAB, the inverse Gamma CDF for x for a shape parameter a and scale parameter b can then be computed using 1 - gamcdf(y,a,1/b), or 1 - gamcdf(1./x,a,1/b).

A function can be created for this so that the similar code does not have to be rewritten every time when computing the CDF:

function [ P ] = inversegamcdfgam( X,A,B )
%inversegamcdfgam Inverse gamma cumulative distribution function.
%   Y = inversegamcdfgam(X,A,B) returns the inverse gamma cumulative
%   distribution function with shape and scale parameters A and B,
%   respectively, at the values in X. The size of P is the common size of
%   the input arguments. A scalar input functions is a constant matrix of
%   the same size as the other inputs.

%P = gammainc(B./X,A,'upper');
P = 1 - gamcdf(1./X,A,1/B);

end

Compare the results with those from computing the inverse Gamma CDF directly by finding the absolute difference:


In the figure above, the vertical axis represents the absolute difference between the results obtained using the formula and those obtained using gamcdf. It can be seen that the difference is small (possibly resulting from estimation) and negligible.

iCDF


Based on the results for the CDF, the iCDF for the inverse Gamma distribution can be computed using the iCDF for the Gamma distribution.

Given a random variable (RV) Y ~ Gamma(a, 1/b), let
$X = g(Y) = 1/Y$.
Based on the definitions, X ~ Inv-Gamma(ab).

Denote the CDF for X by F(x|a, b) and that for Y by F(y|a, 1/b), a being the shape parameter for X and b the scale parameter. It is known that
$F(x|a, b) = 1 - F(y|a, 1/b)$. 

Based on this, given 1 - F(x|a, b), the iCDF value for F(y|a, 1/b) is y, which is 1/x. Therefore, given the CDF value p, shape parameter a, and scale parameter b, the corresponding inverse Gamma RV x can be found in MATLAB using 1./gaminv(1-p,a,1/b).

A function can be created for this so that the similar code does not have to be rewritten every time when computing the PDF:

function [ X ] = inversegaminv( P,A,B )
%inversegaminv Inverse of the inverse gamma cumulative distribution
%function (cdf).
%   X = inversegaminv(P,A,B) returns the inverse cdf for the inverse gamma
%   distribution with shape A and scale B, evaluated at the values in P.
%   The size of X is the common size of the input arguments. A scalar input
%   functions is a constant matrix of the same size as the other inputs.

X = 1./gaminv(1 - P,A,1./B);

end

Given a set of CDF values, compare the CDF values for the iCDF results:


In the figure above, the vertical axis represents the absolute difference between the given CDF values and the CDF values computed using the formula for the iCDF results for the given CDF values. It can be seen that the difference is small (possibly resulting from estimation) and negligible.

-----

The above has not been peer-reviewed, but I will continue the project I am working on using the above information for now. If it is wrong, I will definitely see something wrong for the project I am working on (this is not a project that will cause any harm, so it is fine for me to continue for now).

Any constructive feedback will be appreciated. 

Wednesday, March 12, 2014

Compute Inverse Gamma PDF and CDF in MATLAB

Although MATLAB does not have built-in functions for the PDF and CDF of the inverse gamma distribution, the two functions can be implemented in MATLAB easily using the known formula.

PDF

The PDF of the inverse gamma distribution for a random variable (RV) x is
a: shape parameter
b: scale parameter
Γ(•): gamma function.

The gamma function can be computed in MATLAB using the gamma function.

The above PDF formula can be implemented as

function [ Y ] = inversegampdf( X,A,B )
%inversegampdf Inverse gamma probability density function.
%   Y = inversegampdf(X,A,B) returns the inverse gamma probability density
%   function with shape and scale parameters A and B, respectively, at the
%   values in X. The size of Y is the common size of the input arguments. A
%   scalar input functions is a constant matrix of the same size as the
%   other inputs.

Y = B^A/gamma(A)*X.^(-A-1).*exp(-B./X);

end

Examples of the results of the above function are shown in this figure:


You can compare the results with those on Wikipedia.

CDF

The CDF of the inverse gamma distribution for a random variable (RV) x is
a: shape parameter
b: scale parameter.

The numerator is the upper incomplete gamma function, which in MATLAB can be computed using the gammainc function.

The above CDF formula can be implemented in MATLAB as

function [ P ] = inversegamcdf( X,A,B )
%inversegamcdf Inverse gamma cumulative distribution function.
%   Y = inversegamcdf(X,A,B) returns the inverse gamma cumulative
%   distribution function with shape and scale parameters A and B,
%   respectively, at the values in X. The size of P is the common size of
%   the input arguments. A scalar input functions is a constant matrix of
%   the same size as the other inputs.

P = gammainc(B./X,A,'upper');

end

Examples of the results of the above function are shown in this figure:


You can compare the results with those on Wikipedia.