Lab1_Introduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Καλώς ήρθατε 1ο στο εικονικό εργαστήριο!\n",
    "\n",
    "Σκοπός αυτού του εργαστηρίου είναι να εξοικειωθείτε με το περιβάλλον (Python, Jupyter Notebook) και εν συνεχεία να εφαρμόσετε τις γνώσεις που αποκτήσατε (προγραμματιστικές και θεωρητικές) για να λύσετε μια άσκηση.\n",
    "Για να ολοκληρώσετε το εργαστήριο, ακολουθήστε τις οδηγίες στα κελιά κειμένου και εκτελέστε τα κελιά κώδικα για να δείτε τα αποτελέσματα.\n",
    "\n",
    "Η αρίθμηση των ασκήσεων είναι η ίδια με αυτή του [βιβλίου](https://repository.kallipos.gr/handle/11419/6003)\n",
    "\n",
    "\n",
    "## simple_markov_chain_lib\n",
    "\n",
    "Αρχικά θα πρέπει να εξοικιωθείτε με την *βιβλιοθήκη* **`simple_markov_chain_lib`**. Η βιβλιοθήκη αυτή περιέχει τον *προσομοιωτή* πεπερασμένων μαρκοβιανών αλυσίδων **`markov_chain`**. \n",
    "\n",
    "Σε αυτό το εργαστήριο θα μάθετε πως να τον χρησιμοποιείτε. Συγκεκριμένα θα εστιάσουμε σε 2 λειτουργίες:\n",
    "\n",
    "1. Πως να δημιουργήσετε μια καινούργια αλυσίδα\n",
    "2. Πώς να προσομοιώσετε τα βήματα της αλυσίδας στον χώρο καταστάσεων\n",
    "\n",
    "Φροντίστε το αρχείο **`simple_markov_chain_lib`** να βρίσκεται στον ίδιο φάκελο με το παρόν notebook.\n",
    "Δεν χρειάζεται να κατανοήσετε τον κώδικα που περιέχει, καθώς αυτό απαιτεί κάποια εμπειρία με Python (και αντικειμενοστραφή προγραμματισμό). Θα τον χρησιμοποιήσουμε απλά σαν βιβλιοθήκη που προσωμοιώνει μαρκοβιανές αλυσίδες.\n",
    "\n",
    "Παρόλα αυτά, αν έχετε κάποια οικειότητα με την Python, αξίζει να τον ανοίξετε και να ρίξετε μια ματία και ειδικά στις \"εσωτερικές μεθόδους\" `_partial_sums` και `_next_state` (η κάτω παύλα `_` στην αρχή δηλώνει ότι είναι εσωτερικές μέθοδοι και δεν πρέπει να καλούνται από το χρήστη). Οι 2 αυτές μέθοδοι υλοποιούν την γεννήτρια τυχαίων αριθμών που περιγράφεται στην **άσκηση 10**. Μπορείτε να επεξεργαστείτε τον κώδικα μέσω του browser από την κεντρική σελίδα ([Home](/tree)) ή πατώντας αυτό το [link](/edit/simple_markov_chain_lib/__init__.py). \n",
    "\n",
    "Θα ξεκινήσουμε με ένα παράδειγμα (άσκηση 17) και στη συνέχεια θα αναλύσουμε τι κάνει.\n",
    "\n",
    "### Άσκηση 17\n",
    "\n",
    "Το παρακάτω κελί προσομοιώνει τα πρώτα τα 10 βήματα μιας αλυσίδας που κινείται στον χώρο καταστάσεων \n",
    "$X = \\{0, 1, 2, 3, 4\\}$ με πίνακα πιθανοτήτων μετάβασης:\n",
    "\n",
    "$$\n",
    "P = \n",
    "\\begin{pmatrix}\n",
    "0   & 1/2 & 1/2 &  0  & 0 \\\\\n",
    "1/3 &  0  &  0  & 2/3 & 0 \\\\\n",
    "0   &  0  &  1  &  0  & 0 \\\\\n",
    "1/2 &  0  &  0  & 1/2 & 0 \\\\\n",
    "0   &  0  &  0  &  0  & 1 \n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "και αρχική κατανομή: \n",
    "\n",
    "$$ \\pi_0 = (1, 0, 0, 0, 0 ) $$\n",
    "\n",
    "Δηλαδή η αλυσίδα ξεκινάει από την κατάσταση 0 (1ή γραμμή) με πιθανότητα 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from simple_markov_chain_lib import markov_chain  # import markov chain simulator\n",
    "\n",
    "# Transition Table\n",
    "markov_table = {\n",
    "    0: {1: .5, 2: .5},  # from state 0 we move to state 1 with prob 0.5 and to state 2 with 0.5\n",
    "    1: {0: 1/3, 3: 2/3},\n",
    "    2: {2: 1.},\n",
    "    3: {0: .5, 3: .5},\n",
    "    4: {4: 1.}\n",
    "}\n",
    "\n",
    "# Initial Distribution\n",
    "init_dist = {0: 1.}  # we start from state 0 with probability 1\n",
    "\n",
    "mc = markov_chain(markov_table, init_dist)\n",
    "\n",
    "mc.start()\n",
    "print(\"At time {} the chain is in state {}\".format(mc.steps, mc.running_state))\n",
    "for i in range(10):\n",
    "    mc.move()\n",
    "    print(\"At time {} the chain is in state {}\".format(mc.steps, mc.running_state))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Δοκιμάστε να τρέξετε το προηγούμενο κελί μερικές φορές (`Ctrl + Enter` ή επιλέξτε με κλικ το κελί και στη συνέχεια >>Cell και Run Cells). Δείτε πως αλλάζουν τα αποτελέσματα.\n",
    "\n",
    "\n",
    "## Εξήγηση\n",
    "\n",
    "Στη πρώτη γραμμή απλά εισάγουμε τον προσομοιωτή `markov_chain` στο περιβάλλον εργασίας μας.\n",
    "\n",
    "```python\n",
    "# import markov chain simulator\n",
    "from simple_markov_chain_lib import markov_chain  \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Δημιουργία καινούργιας μακροβιανής αλυσίδας\n",
    "\n",
    "Στις επόμενες γραμμές δημιουργούμε την αλυσίδα Markov που περιγράφεται στην εκφώνηση.\n",
    "Για να το κάνουμε αυτό χρειάζεται να δώσουμε στον προσομοιωτή 2 ορίσματα:\n",
    "\n",
    "1. `markov_table`: Ο πίνακας πιθανοτήτων μετάβασης της αλυσίδας και\n",
    "2. `init_dist` (προαιρετικά): η αρχική κατανομή της αλυσίδας.\n",
    "\n",
    "#### Πίνακας Πιθανοτήτων Μετάβασης (`markov_table`)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "```python\n",
    "# Transition Table\n",
    "markov_table = {\n",
    "    0: {1: .5, 2: .5},\n",
    "    1: {0: 1/3, 3: 2/3},\n",
    "    2: {2: 1.},\n",
    "    3: {0: .5, 3: .5},\n",
    "    4: {4: 1.}\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Επειδή συχνά οι πίνακες μετάβασεις είναι \"αραιοί\", τις περισσότερες φορές\n",
    "δεν γράφουμε όλες τις καταστάσεις αλλά μόνο τις μη μηδενικές.\n",
    "Κάθε \"εσωτερικό\" λεξικό (`dict`) περιγράφει μία συνάρτηση μάζας πιθανότητα (*σ.μ.π*) ως εξής:\n",
    "\n",
    "* `key` = κατάσταση (δεν χρειάζεται να είναι αριθμός)\n",
    "* `value` = πιθανότητα (πρέπει να είναι αριθμός στο διάστημα $[0, 1]$)\n",
    "\n",
    "όσες καταστάσεις **δεν** περιέχονται στο λεξικό θεωρείται ότι έχουν μηδενική πιθανότητα.\n",
    "Ο χώρος καταστάσεων ορίζεται από τα κλειδία του \"εξωτερικού\" λεξικού (στο παράδειγμά μας `0, 1, 2, 3, 4`).\n",
    "\n",
    "#### Αρχική κατανομή (`init_dist`)\n",
    "\n",
    "Η αρχική κατανομή ορίζεται κατα παρόμοιο τρόπο σαν *σ.μ.π*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "```python\n",
    "# Initial Distribution\n",
    "init_dist = {0: 1.}  # we start from state 0 with probability 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Δημιουργία νέας αλυσίδας\n",
    "\n",
    "Με αυτά τα ορίσματα μπορούμε να δημιουργήσουμε μία νέα μαρκοβιανή αλυσίδα ως εξής:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "```python\n",
    "mc = markov_chain(markov_table, init_dist)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Τυχαίος Περίπατος στο Χώρο Καταστάσεων\n",
    "\n",
    "#### Εκκίνηση\n",
    "\n",
    "Τώρα που έχουμε την αλυσίδα μπορούμε να αρχίσουμε να εξερευνούμε τον χώρο των καταστάσεων.\n",
    "Για αρχή πρέπει να ξεκινήσουμε τον περίπατο μας. Αυτό γίνεται με την εντολή **`start`**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mc.start()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Αφού ξεκινήσουμε τον περίπατο μπορούμε να ρωτήσουμε την αλυσίδα μας 2 πληροφορίες:\n",
    "\n",
    "1. **`steps`**: Σε ποιο βήμα βρίσκεται (το $n$ στο $\\{X_n\\}_{n \\in \\mathbb{N}_0}$)\n",
    "2. **`running_state`**: Σε ποιά κατάσταση βρίσκεται ($X_n$)\n",
    "\n",
    "Τρέχοντας το επόμενο κελί θα δείτε σε ποιο βήμα είναι η αλυσιδα"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "mc.steps\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Όπως αναμέναμε η αλυσίδα δεν έχει κουνηθεί ακόμα οπότε 0 βήματα έχουν παρέλθει.)\n",
    "\n",
    "Το επόμενο κελί θα μας αποκαλύψει σε ποιά κατάσταση είναι η αλυσίδα"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mc.running_state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(και πάλι καμία έκπληξη καθώς η αλυσίδα ξεκινά από την κατάσταση `0` με πιθανότητα `1.0`)\n",
    "\n",
    "#### Βηματισμός\n",
    "\n",
    "Για να περιπλανηθούμε στο χώρο πρέπει να δώσουμε την εντολή **`move`**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mc.move()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Αυτή η εντολή επαυξάνει το χρόνο (`steps`) κατά ένα"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mc.steps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "και μεταβιβάζει την αλυσίδα σε μία από τις πιθανές καταστάσεις μετάβασης"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mc.running_state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Περίπατος\n",
    "\n",
    "Επομένως ο παρακάτω κώδικας προσομοιώνει τα 10 πρώτα βήματα της αλυσίδας:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mc.start()\n",
    "for i in range(10):\n",
    "    print(\"At time {} the chain is in state {}\".format(mc.steps, mc.running_state))\n",
    "    mc.move()\n",
    "\n",
    "print(\"At time {} the chain is in state {}\".format(mc.steps, mc.running_state))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Κάθε φορά που εκτελείτε το παραπάνω κελί, η αλυσίδα επανεκκινεί (`mc.start`) τυπώνει (`print`) το βήμα και την κατάσταση και στη συνέχεια εκτελεί 10 βήματα (`mc.move`) τυπώνοντας κάθε φορά το βήμα και την κατάσταση.\n",
    "\n",
    "Παρατηρήστε ότι δεν χρειάζεται να δήλωσουμε που τελειώνει ο επαναληπτικός βρόγχος `for`.\n",
    "Μια από τις πιο σημαντικές ιδιομορφίες της Python είναι να χρησιμοποιεί την στοίχιση (4 κενά εδώ) \n",
    "για να καταλάβει που τελειώνει κάθε μπλόκ κώδικα. Έτσι αναγκάζει τον χρήστη να γράφει ευανάγνωστο κώδικα!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Παραδοτέο\n",
    "\n",
    "1. Δημιουργήστε ένα νέο notebook (`File > New Notebook > Python 3`). \n",
    "2. Δημιουργήστε ένα κελί κώδικα και τροποποιήστε εκεί τον κώδικα που είδαμε ώστε να προσομοιώσετε τα 20 πρώτα βήματα της αλυσίδας που περιγράφεται στην **άσκηση 11** του βιβλίου. \n",
    "3. Τρέξτε τον κώδικά σας ώστε να φανούν τα 20 πρώτα βήματα της αλυσίδας. \n",
    "4. Προσθέστε ένα κελί κειμένου και γράψτε ένα μήνυμα, ό,τι θέλετε. \n",
    "5. Στη συνέχεια σώστε αυτό το Notebook επιλέγοντας `>>File` και `Download as HTML`. \n",
    "6. Ονομάστε το αρχείο `xxx_Lab1.ipynb`, βάζοντας το επίθετό σας όπου `xxx`. \n",
    "6. Ανεβάστε αυτό το αρχείο στο mycourses **μέχρι την Παρασκευή 10/3**.\n",
    "\n",
    "(**Bonus tip**: Οι καταστάσεις δεν είναι κατ' ανάγκη αριθμοί. Μπορεί να είναι και συμβολοσειρές, π.χ. `ABC`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}