{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Exercises C\n",
"_Version: April 28, 2019, see_ [PyEcon.org](https://pyecon.org)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 1: Determinant of a matrix\n",
"Create a function that recursively calculates the determinant of a matrix $M \\in \\mathcal{R}^{n\\times n}$. The recursive definition is given by\n",
"\n",
"$$\\det(M) = \\sum_{j = 1}^n (-1)^{1 + j} \\cdot M_{1, j} \\cdot \\det(M_{-1, -j}),$$\n",
"\n",
"where $M_{-1, -j}$ denotes the matrix $M$ without the first row and the $j$th column.\n",
"\n",
"1. Create the determinant function.\n",
"2. Calculate the determinant of\n",
"$\n",
"M = \\begin{bmatrix}\n",
"1 & 4 & 8 \\\\\n",
"2 & 2 & 9\\\\\n",
"3 & 7 & 1\n",
"\\end{bmatrix}\n",
"$.\n",
"3. Compare your determinant function with `numpy.linalg.det()`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import numpy.linalg as nplin"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2: Inverse of a matrix\n",
"Build a function that computes the inverse of matrix $M$ using the _adjoint method_ and your determinant function from Exercise 1. An element $C_{ij}$ of $C$, the cofactor matrix of $M$, can be written as\n",
"\n",
"$$C_{ij} = (-1)^{i + j} \\cdot \\det(M_{-i,-j}),$$\n",
"\n",
"and the inverse can be calculated by\n",
"\n",
"$$M^{-1} = \\frac{1}{\\det(M)} \\cdot C',$$\n",
"\n",
"where $C'$, the transposed matrix $C$, is the so-called adjugate matrix of $A$.\n",
"\n",
"1. Create the inverse function.\n",
"2. Calculate the inverse of\n",
"$\n",
"M = \\begin{bmatrix}\n",
"1 & 4 & 8 \\\\\n",
"2 & 2 & 9\\\\\n",
"3 & 7 & 1\n",
"\\end{bmatrix}\n",
"$.\n",
"3. Compare your inverse function with `numpy.linalg.inv()`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 3: Applying and observing the eigendecomposition\n",
"\n",
"Consider the folowing matrix:\n",
"\n",
"$$\n",
"X = \\begin{bmatrix}\n",
"15.00 & 24.25 & 12.25 \\\\\n",
"24.25 & 44.75 & 32.50 \\\\\n",
"12.25 & 32.50 & 41.25 \n",
"\\end{bmatrix}\n",
"$$\n",
"\n",
"The eigendecomposition of a symmetric matrix is $X = E\\Lambda E'$, where $E$ is the matrix of the corresponding eigenvectors and $\\Lambda$ is the diagonal matrix of eigenvalues. In the case of a symmtric matrix, $E$ is orthogonal, i.e., $EE' = I$, where $I$ is the identitity matrix of appropriate dimensions.\n",
"\n",
"1. Determine the diagonal matrix of eigenvalues and the matrix of eigenvectors for $X$ with `numpy.linalg`.\n",
"1. From your results of the eigendecomposition use the formula above and recompute $X$. Compare your results.\n",
"1. Calculate $X^2$. The calculate $E \\Lambda^2 E'$. Compare your results. What do you observe?\n",
"1. Compute the inverse by $X = E \\Lambda^{-1} E'$ and compare it to the inverse of $X$, e.g., by employing `numpy.linalg.inv()`.\n",
"1. Compute $E_{(1)}' E_{(1)}$ and $E_{(1)} E_{(1)}'$, where $E_{(1)}$ represents the first column of matrix $E$.\n",
"1. Calculate $\\sum_{i = 1}^n \\Lambda_{ii} E_{(i)} E_{(i)}'$, where $n$ refers to the number of columns of $X$ and $\\Lambda_{ii}$ is the $i$th diagonal element of $\\Lambda$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 4: Password generation and encryption\n",
"1. Write a function that creates a password by randomly picking characters, i.e., letters, numbers, etc.\n",
"1. Modify your function and include an option so that the function generates passwords where each character is unique.\n",
"1. Encrypt and decrypt this text: \"MONTY PYTHON\"\n",
" 1. Use the function of 2. to generate a 27 digits password.\n",
" 1. Write an encoding function that you can use to encrypt uppercase letters texts and spaces.\n",
" 1. Write a decryption function for decoding the previously encrypted text.\n",
" \n",
" _Hints:_\n",
" * _You could use the modules random or numpy.random._\n",
" * _You might benefit from studying the Python library on string methods._"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import random"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 5: Simulation and estimation techniques\n",
"Simulate data from a random variable $Y$, which can be thought to be the level of production of some country, with the following properties:\n",
"\n",
"$Y \\sim \\mathcal{\\ln N}(\\mu,\\,\\sigma^{2})$,\n",
"\n",
"with\n",
"\n",
"$E(Y) = AK^{1-\\alpha}L^\\alpha$,\n",
"\n",
"where\n",
"\n",
"$A = 1$ (Technology),\n",
"\n",
"$K \\sim \\mathcal{U}(30, 50)$ (Capital),\n",
" \n",
"$L \\sim \\mathcal{U}(20, 40)$ (Labour).\n",
"\n",
"Note that $\\mu = \\ln E(Y) - \\sigma^{2} / 2$. See the Log-normal distribution for details.\n",
"\n",
"#### I. Simulate data\n",
"\n",
"1. Set a seed so that your results are reproducable and define the parameters $\\sigma^{2} = 0.5$ and $\\alpha = 0.7$.\n",
"1. Draw $n = 100000$ observations for $K$, $L$ and $Y$.\n",
"1. Build a data frame of the observed vectors $K$, $L$ and $Y$.\n",
"1. Add the logarithms of all columns to the dataset and name them $y$, $k$ and $l$.\n",
"\n",
"\n",
"#### II. Ordinary least squares (OLS) estimation\n",
"\n",
"Validate your simulation by conducting an OLS estimation with the logarithmized data:\n",
"\n",
"Estimate the linear regression model\n",
"\n",
"$$\n",
"\\boldsymbol{y} = X\\boldsymbol{\\beta} + \\boldsymbol{e},\n",
"$$\n",
"\n",
"where $X$ contains $\\boldsymbol{k}$ and $\\boldsymbol{l}$ as its columns as well as an intercept (a column of ones). $p$ is the number of columns of $X$.\n",
"\n",
"The OLS estimators are defined as\n",
"\n",
"$$\n",
"\\boldsymbol{b} = (X'X)^{-1}X'\\boldsymbol{y},\n",
"$$\n",
"\n",
"and\n",
"\n",
"$$\n",
"\\hat{\\sigma}^2 = \\frac{\\hat{\\boldsymbol{e}}'\\hat{\\boldsymbol{e}}}{n - p},\n",
"$$\n",
"\n",
"where $\\hat{\\boldsymbol{e}} = \\boldsymbol{y}-X\\boldsymbol{b}$.\n",
"\n",
"\n",
"#### III Non-linear estimation algorithm\n",
"\n",
"Implement the Newton-Raphson algorithm based on $ln Y = \\boldsymbol{y}$, i. e., using the normally distributed data. The algorithm proceeds as follows:\n",
"\n",
"$$\n",
"\\boldsymbol{\\theta}_{j+1} = \\boldsymbol{\\theta}_j - H^{-1}\\boldsymbol{s},\n",
"$$\n",
"\n",
"where $\\boldsymbol{\\theta} = [\\boldsymbol{\\beta}', \\sigma^2]'$ and $H = \\frac{\\delta^2 \\ln L}{\\delta \\boldsymbol{\\theta} \\delta \\boldsymbol{\\theta}'}$ and $\\boldsymbol{s} = \\frac{\\delta \\ln L}{\\delta \\boldsymbol{\\theta}}$ are the _Hessian matrix_ and the gradient (here _score_), i. e., the matrix of the second and the vector of the first derivatives of the target function.\n",
"\n",
"In this case, the target is the logarithmized likelihood function\n",
"\n",
"$$\n",
"\\ln L \\left(\\boldsymbol{\\theta}| \\boldsymbol{y}, X\\right) = -\\frac{n}{2}\\ln \\left(2\\pi\\right) -\\frac{n}{2}\\ln \\left(\\sigma^2 \\right) - \\frac{\\left(\\boldsymbol{y}-X\\boldsymbol{\\beta} \\right)'\\left(\\boldsymbol{y}-X\\boldsymbol{\\beta} \\right)}{2\\sigma^2},\n",
"$$\n",
"\n",
"with\n",
"\n",
"$$\n",
"H = \n",
"\\begin{bmatrix}\n",
"-\\frac{1}{\\sigma^2}X'X & -\\frac{1}{\\sigma^4}X'\\boldsymbol{e} \\\\\n",
"-\\frac{1}{\\sigma^4}\\boldsymbol{e}'X & \\frac{n}{2\\sigma^4} - \\frac{1}{\\sigma^6}\\boldsymbol{e}'\\boldsymbol{e}\n",
"\\end{bmatrix},\n",
"$$\n",
"\n",
"and\n",
"\n",
"$$\n",
"\\boldsymbol{s} = \n",
"\\begin{bmatrix}\n",
"\\frac{1}{\\sigma^2}X'\\boldsymbol{y} - \\frac{1}{\\sigma^2}X'X\\boldsymbol{\\beta} \\\\\n",
"- \\frac{n}{2\\sigma^2} + \\frac{1}{2\\sigma^4}\\boldsymbol{e}'\\boldsymbol{e}\n",
"\\end{bmatrix},\n",
"$$\n",
"\n",
"where $\\boldsymbol{e} = \\boldsymbol{y}-X\\boldsymbol{\\beta}$.\n",
"\n",
"* Start with some initial guess $\\boldsymbol{\\theta}_0 = (-0.3, 0.2, 0.8, 0.6)$.\n",
"* Make sure that the variance, i.e., the estimator for $\\theta_4 = \\sigma^2$, cannot turn negative in any iteration step.\n",
"* Stop the alogorithm if $\\text{abs}(\\boldsymbol{\\theta}_{j+1} - \\boldsymbol{\\theta}_j) < 0.00001 \\cdot \\boldsymbol{1}$.\n",
"* Compare your estimates obtained from the Newton-Raphson algorithm to the results of the analytical solution $\\boldsymbol{b}$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import numpy.linalg as nplin\n",
"import pandas as pd"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}