RPi Stream

In a previous post I described setting up an RPi Zero and camera to stream video over the internet. This is obviously a very valuable thing to do, for example, if you have cats and love them so much that you just want to be able to see them all the time. However, the method that I used, which involved a home network-based server, port-forwarding, and dynamic DNS is one that I was never entirely comfortable with from a security POV.

After some thought and reading on the subject, I finally discovered a ready-made solution to the problem – YouTube!

YouTube allows users with a verified account (a process which, for some reason, takes all of 24 hours) to stream apparently unlimited video at absolutely no cost. There are obviously some limitations, which are tl;dr, but generally look pretty reasonable AFAICT.

First things first.

You’ll need an RPi (I used a 3B+ for this exercise, but I’m sure a Zero or anything else would be fine) an up-to-date version of Raspian (although I suspect this might work with other forms of RPi linux).

In the terminal, do this:


sudo update
sudo -y dist-upgrade


Plug in your camera. This requires some care. Look closely at the ribbon and the sockets on the board and the camera. There is a small plastic retaining clip on each socket that you need to gently pull up/out to open the socket. Slide the ribbon cable into the socket and close the clip. Make sure the shiny contacts are facing in the right direction to make proper contact with the socket. Look at these images to get a better idea. (If your camera doesn't work, this is the first thing you need to check.) Note that there are two similar sockets on the RPi 3B+ board - one is labeled "display" (the one at the end), and the other is labeled "camera" (the one closer to the middle of the board).

Now make sure your camera is working. Turn it on. The easiest way to do that is to go to "Preferences" and "Interfaces" in the main pull-down menu on the GUI and activate the camera. (You may also need to enable I2C.)

Next run the following command:


raspistill -a 12 -vf -hf -t 0 -k -w 640 -h 480 -o pistill.jpg


-a 12 gives you a date stamp, -vf -hf flips the camera image vertically and horizontally, -t 0 -k allows you to take a picture by hitting the ENTER button, and then exit the raspistill program by hitting "x" followed by ENTER. -w 640 -h 480 sets the width and height of the image in pixels. You can experiment with all of these. An introduction to the two basic camera applications, raspistill and raspivid, and some of their command line options, can be found here.

After you execute the command, hit ENTER (to record an image), and the press "x" followed by ENTER (to exit the program), the file pistill.jpg should be in your /home/[yourusername]/ directory waiting for you to look at it. If it's not there, go through the steps above again, taking special care to be certain that the camera is correctly plugged in to the board. (If you plugged it in to the "display" connector, it definitely won't work.)

Once you're sure your camera is working, you'll need to have an active Google Account and a YouTube Channel. Google should be able to provide adequate instructions for this. After that's taken care of, go to YouTube Studio and follow the prompts to stream. This is not perfectly intuitive, but even I was able to figure it out, so you should be able to as well. Just take a look at my channel here to get an idea of how this works. The first screen you'll see when you go to the YouTube Studio with your own account is the main dashboard. Click on "Videos," then on "Live." You'll be prompted to verify your account, and you'll need to wait another 24 hours before you can start streaming. From here the steps are more or less intuitive if you follow the prompts.

At a certain point in the process you will be provided with a streaming URL and a "secret key." Save these in a file where you can easily access and copy-paste them. You'll need them for the next steps.

Note: if all of this looks confusing, take a look at these pages here and here to get a better understanding of the process of setting this up. However, I would suggest *not* using the streaming commands that these pages provide. I had a little trouble getting them to work, and so I will provide a slightly different one that worked for me below.

One you have your camera working and your YouTube Account set-up for streaming, go ahead and start the live stream reception in Youtube Studio. Then point your camera at something and execute the following command at the terminal prompt:


raspivid -o - -t 0 -fps 25 -g 50 -rot 180 -n -a 12 -b 6000000 | ffmpeg -re -ar 44100 -ac 2 -acodec pcm_s16le -f s16le -ac 2 -i /dev/zero -f h264 -thread_queue_size 256 -i - -vcodec copy -acodec aac -ab 128k -strict experimental -f flv rtmp://a.rtmp.youtube.com/live2/[yoursecretkey]


Note that you need to copy and paste your secret key after the last backslash. Leave out the square brackets; just paste the key. Also note that this command string is really long; if you want to you can try putting this in a bash script either with the secret key hard-coded in the script, or with a $arg[1] variable that you supply to the script when you execute it. I won't go into all the details of that here, but if you'd like to learn about shell scripts,  Norm Matloff's brief introduction to these is a great place to start. Just don't forget to put #!/bin/bash at the top of the script file. Also don't forget to make the file executable like this:


sudo chmod +x [yourshellscript].sh


And, when you execute the script, do it like this:


./[yourshellscript].sh


You'll need the dot-slash in front in order for the OS to recognize it as a command.

I should also point out that the critical difference between this command and the others provided in the links above is the option "-thread_queue_size 256" without which you will probably get an error (I did). So try the command string I provided first. The links are helpful, however, if you want to learn a little more about raspivid and some of the command options.

If everything works like it's supposed to, then in a few minutes you should be streaming.

Go here to see a recorded stream that I made (YouTube will supposedly record up to 12 hours of live streamed video, which is astonishing).

Now, if you want to get really fancy, you can actually embed your stream (either live or recorded or both) in a web page. Just don't put it in a web page that you're hosting in your own home network server. At least, not unless you are very knowledgeable about web security and know exactly what you are doing. The better option, IMHO, is to use a cloud server like Heroku. Eventually, that's exactly what I plan to do, but Heroku requires a little more familiarity with git than I have right now, so (ironically) I found it easier to use my already existing web page on GitHub. I won't explain the details of how to establish a GitHub (or Heroku) account here; it's pretty easy, and both services provide web site hosting and pretty straight-forward instructions for how to set up a web page. (They're also our favorite price.)

I'll just add that in order to create a web page it helps to know something about how to use and write html. I like Mozilla's tutorial on html basics. Note that with a GitHub page you can either use straight html or a simplified version called Markdown (or md). All this html and md stuff is probably going to require a little work on your part, but you really only need to get the basics in order to get started. You can take a look at the internals of my web page on GitHub to get some pointers. Note that there is a little file called "_config.yml" here that is not normally present in the directory for a typical html web page. This is a configuration file for Jekyll which GitHub uses to build your site. Don't worry too much about this; you can ignore it for now. The point is that if, like me, you use GitHub to host your site, GitHub and Jekyll will impose some limitations, and also require you to modify your use of html a little bit. It will also be a little quirky compared to a normal html page. For example, you can only build a static site (no PHP) , and you need to *not* use the normal <DOCTYPE html> tag in the index file. (When you look at my code, you'll notice that it's there, for future use with Heroku, but it's commented out.)

So, if you've made it this far, let me show you the way I embed my Youtube live stream and recorded streams.

This for the live stream:


&tl;a title="Youtube Livestream" href="https://www.youtube.com/embed/live_stream?channel=[yourYouTubechannelcode]">&tl;img src="luxlivebutton.jpg" alt="Livestream" />&tl;/a>

You need your YouTube channel code for this (again, leave off the square brackets). You can find this right after "studio.youtube.com/channel/" in the url for the YouTube Studio Dashboard page.

For a previously recorded stream, use this code in your page:


&tl;a title="Youtube Video" href="[yourvideostreamURL]">&tl;img src="luxvideobutton.jpg" alt="Video" />&tl;/a>

In this case, you will need to use the URL for the previously recorded video stream. You can actually see a recorded stream here of a little polyhedral light sculpture; you can also access the same stream (and a live stream when it's active) through my GitHub web page.

Note that for the streams I have created little buttons to click on; this is pretty easy to do if you use Gimp or something like it to create graphics. These files are in the web page directory if you want to see them.

Just one more thing:

This entire description presupposes that you're doing this with a Pi connected to a keyboard and a monitor. But that's not how I did it. It's actually easier, I think, to SSH from a laptop to a Pi, and then work in both simultaneously. What I did was connect my laptop to the Pi via SSH and VNC (in order to have access to the Pi GUI) through an SSH tunnel. That's really a topic for another post. But it did facilitate the process a little for me because I could work on YouTube and GitHub with the laptop, and take care of the camera-related processes on the Pi. Note that if you want to do it this way, you need to make sure that SSH and VNC are also enabled (along with the camera and I2C) in the Pi configuration, accessible through "Preferences" and "Interfaces." You can do this through the command line as well, in which case you don't really need VNC or the GUI at all, although I find it more convenient to do some things that way.

So, there you have it. If you're interested in seeing the full html code for my page, you can easily view it in my my GitHub repository; embedding it here is a fairly laborious process, so I'll leave it up to you to find it.

Good luck!

Security

This should by no means be considered an expert guide to web security; it is just a summary of my efforts to protect my own network, given my interest in building a web camera (mainly to watch cats). Here’s what I’ve learned.

It occurred to me that forwarding open ports to the Internet might pose a security issue.

I found the following steps offered some reassurance and were relatively simple
to implement.

ufw

Uncomplicated Firewall (UFW) allows ports to be closed on the device.

sudo apt install ufw
sudo ufw allow 22
#SSH, for control and configuration on the LAN

sudo ufw allow 5900
#VNC, best used through an SSH tunnel (5900:127.0.0.1:5900)

sudo ufw allow 8081
#camera

sudo ufw allow 8080
#camera configuration in browser (optional)

#all other ports are disabled by default with ufw,
#port must be either allowed, or can be turned off
#with "deny "

sudo ufw enable
sudo ufw status

Fail2ban

Fail2ban blocks IP addresses that display suspicious activity, i.e., multiple
failed attempted to log in.

sudo apt install fail2ban
sudo nano /etc/fail2ban/jail.local

This creates a file that will supercede the default settings. The most hackable
ports will presumably be 22 (SSH) and 46 (VNC).

Add the following to jail.local

[ssh]
enabled = true
port = ssh
filter = sshd
logpath = /var/log/auth.log
maxretry = 3
bantime = -1

This will permanently ban any ip address that fails to login after 3 ties
(you can modify this).

Configure VNC and Motion

I’m not aware of any way to use fail2ban to ban failed VNC login attempts
(or failed attempts of 8080 and 8081), but you can configure VNC to accept only localhost logins (do this with the “Options -> Expert” menu by setting “localhost” to “True” in the RealVNC VNC Server). Presumably 8081 (camera)and 8081 (camera control) can be made less vulnerable by using a strong password
for access, which can be set in the /etc/motion/motion.conf file.

sudo nano /etc/motion/motion.conf

Look for the “Live Stream Server” section. Set up these options:

# The mini-http server listens to this port for requests (default: 0 = disabled)
stream_port 8081

# Quality of the jpeg (in percent) images produced (default: 50)
stream_quality 50

# Output frames at 1 fps when no motion is detected and increase to the
# rate given by stream_maxrate when motion is detected (default: off)
stream_motion off

# Maximum framerate for stream streams (default: 1)
stream_maxrate 50

# Restrict stream connections to localhost only (default: on)
stream_localhost off

# Limits the number of images per connection (default: 0 = unlimited)
# Number can be defined by multiplying actual stream rate by desired number of seconds
# Actual stream rate is the smallest of the numbers framerate and stream_maxrate
stream_limit 0

# Set the authentication method (default: 0)
# 0 = disabled
# 1 = Basic authentication
# 2 = MD5 digest (the safer authentication)
stream_auth_method 2

# Authentication for the stream. Syntax username:password
# Default: not defined (Disabled)
stream_authentication username:password

Similarly, look for “HTTP Based Control”, and set the following options:

# TCP/IP port for the http server to listen on (default: 0 = disabled)
webcontrol_port 8080

# Restrict control connections to localhost only (default: on)
webcontrol_localhost on

# Output for http server, select off to choose raw text plain (default: on)
webcontrol_html_output on

# Authentication for the http based control. Syntax username:password
# Default: not defined (Disabled)
webcontrol_authentication username:password

This ensures that you can a.) only login to the webcontrol page (port 8080) on
the host device, and b.) you must use a username:password pair to actually
access the video stream. It also gives the option of sending you authentication
credentials using the MD5 message-digest algorithm, which apparently has some
vulnerabilities, but may possibly be better than nothing.

So, there you are. All RasPi ports except for 22, 5900, 8081 and 8080 are closed by ufw; fail2ban scans attempts to log in to the SSH server (which shouldn’t be accessible anyway, except over the LAN), VNC is disabled for everything except VNC tunneling through SSH, and the router only forwards 8081 to the web. Stream and webcontrol pages are password protected.

That’s as tight as I could get it with my limited knowledge of network security,
but it seems much better than a wide open server.

In addition to protecting my camera server, I used UFW to lock all the ports on my laptop, as well as Fail2Ban to protect against hacking on port 22 (SSH). It’s also a good idea to use strong passwords.

See this reference for a more complete discussion of the security considerations for a RasPi camera server:
https://www.raspberrypi.org/documentation/configuration/security.md

RasCam

Note: This works with Raspbian GNU/Linux 9.1 (stretch) and Raspberry Pi zero.

These instructions should make it possible to connect a RasPi-compatible camera to a RasPi Zero and stream video on the local network and internet (with suitable configuration).

Attach and enable camera

Attach camera to RasPi using 15/22 pin ribbon cable. Prepare using the following
commands.

sudo apt-get update
sudo apt-get dist-upgrade
sudo raspi-config
# In this menu, or in the GUI option, enable the camera
reboot

# Test your camera !
raspistill -o cam.jpg

Install and configure motion software


sudo apt-get install motion
# Careful, on the v4l2 it's an 'L', not the number 1
sudo modprobe bcm2835-v4l2

sudo nano /etc/modules
# at the end of the file, add this line :
bcm2835-v4l2

sudo nano /etc/default/motion
# in this file, search for start_motion_daemon and activate it
# start_motion_daemon=yes

sudo cp /etc/motion/motion.conf /etc/motion/motion.conf.bak
sudo nano /etc/motion/motion.conf
# Allow motion to run the daemon we've set earlier
daemon on
# Set the logfile (important to debug motion if you webservers crashes)
logfile /tmp/motion.log
# we want to be able to access the stream outside off the Pi's localhost
stream_localhost off
# disable pictures and movies saving
output_pictures off
ffmpeg_output_movies off
# set the framerate of the stream (100 for higher quality)
framerate 100
# set the width and height of your video (defaults 640, 480)
width 640
height 480
# webcontrol port 8080 by default (access some controls through http)
webcontrol_port 8080
# stream port 8081 by default (access streaming video through http)
stream_port 8081
# careful ! don't set the stream_port just like the webcontrol port
# Optional: add this line in the file for password protection of webcontrol
webcontrol_authentication username:password

sudo service motion start

Open browser, http://localhost:8081

Attach RasPi to local network and router


# will open the network configuration file
# alternately, use the desktop GUI
sudo nano /etc/network/interfaces

#add the following
auto lo
iface lo inet loopback
iface eth0 inet dhcp

allow-hotplug wlan0
auto wlan0

iface wlan0 inet dhcp
wpa-ssid "Your Network SSID"
wpa-psk "Your Password"

sudo service networking reload

Obtain IP address for host and router


ifconfig
#gets ip address for RasPi ("inet addr")

route -n
#gets address for default gateway (internal)
#To obtain external address, use a service such as
# https://portforward.com/networking/routers_ip_address.htm
#This will be useful in setting up DDNS (see below).

Open browser, http://:8081

DDNS

Register ddns account and install ddns client (follow instructions below).
https://www.noip.com/
https://www.noip.com/support/knowledgebase/installing-the-linux-dynamic-update-client/

# To confirm the service is running properly
sudo noip2 ­-S

Connect to router and configure port forwarding.

Set static ip address


sudo nano /etc/dhcpcd.conf

#add to file:

interface eth0

static ip_address=192.168.0.10/24
static routers=192.168.0.1
static domain_name_servers=192.168.0.1

interface wlan0

static ip_address=192.168.0.200/24
static routers=192.168.0.1
static domain_name_servers=192.168.0.1

#interface = This defines which network interface you are setting
#the configuration for.
#static ip_address = This is the IP address that you want to set your device to.
#(Make sure you leave the /24 at the end)
#static routers = This is the IP address of your gateway
#(probably the IP address or your router)
#static domain_name_servers = This is the IP address of your DNS
#(probably the IP address of your router; can also add Google DNS 8.8.8.8).
#You can add multiple IP addresses here separated with a single space.

reboot Pi
(You may also need to reboot router)

In browser, https://.ddns.net:8081

Networking

This project required me to improve my understanding of networking. There are
two sites that I found particularly helpful listed among the references
below.

References:

https://www.bouvet.no/bouvet-deler/utbrudd/building-a-motion-activated-security-camera-with-the-raspberry-pi-zero

https://pimylifeup.com/raspberry-pi-webcam-server/

https://hackernoon.com/spy-your-pet-with-a-raspberry-pi-camera-server-e71bb74f79ea

https://hackernoon.com/how-to-access-your-raspberry-pi-camera-from-anywhere-544ab9e5bacc

https://motion-project.github.io/index.html

https://www.noip.com/

https://www.noip.com/support/knowledgebase/installing-the-linux-dynamic-update-client/

https://portforward.com/networking/routers_ip_address.htm

Click to access NetIntro.pdf

https://opensource.com/business/16/8/introduction-linux-network-routing

端的只今の一念より外はこれなく候

This is a line from Hagakure by Yamamoto Tsunetomo. The Hagakure is usually referred to as The Way of the Samurai, or something li ke that, but a literal translation would be more like, “In the Shadow of Leaves”, which I think is more beautiful.

端的只今の
一念より外はこ
これなく候

Tanteki tadaima no
ichinen yori hoka wa
kore naku sōrō

Which means, more or less:

There is surely nothing
other than the single purpose
of the present moment.

(Note that the words have been rearranged for grammatical reasons.)

Even though it’s not 5-7-5, it still has the feeling and rhythm of a haiku for me, and it really distills very nicely, I think, the spirit of zen.

The Hagakure, BTW, is the book that Ghost Dog reads (and gives to the little girl) in Jim Jarmusch’s film of the same name.

Wine

I don’t drink wine anymore; having finished cat-assisted rehab, I now just drink lots coffee. But I’m still interested in the subject and was particularly curious about a data-set that I happened to encounter in my efforts to learn more about Python and statistics.

I’ll try to provide more details later on, but I was so excited about these results that I decided to go ahead and put up a rough ASAP.

Turns out, that with a little Pythonification and linear regression, you can find out some interesting things about wine.

This is what you get when you look at something like about 130k(!) wines:

wineplotscoredistLR

The wines are scored by a professional wine-taster, or sommelier, or something. The first graph shows the distribution of scores, which, to my untrained eye, looks suspiciously like a so-called “normal” (or Gaussian) curve. The graph next to it is an attempt to find the best fit for a linear relationship (if there is one) between the scores and the prices of these fine products. Turns out the lowest price is $4 (like what you might get at Trader Joe’s) and the highest is in excess of $3000 (Yikes!).

But look at that graph – the numbers are all over the place, and there doesn’t seem to be a well-defined relationship at all, at least not at first. After looking at it a couple of times, I thought to myself, “well, what about a logarithmic transformation – why not!”

logLRwine

So there you have it. There’s a bit of spread, but to me it certainly does look like the prices go up exponentially as the wine-taster’s scores increase. Something to think about, I guess.

(Note: If you check out the links above, be advised that the code provided on the web pages doesn’t work the way it’s written, or at least it didn’t work for me. Maybe because I’m still using Python 2.7. I had to do a little tweaking, as well as learn a little more about the use of the numerical and graphing modules to get it going.)

Cheers, everyone.

Seattle Weather, revisited

Following up a little on the previous post about Seattle weather conditions and Markov chain modeling, I decided to write a quick Python script that calculates the probability vectors for each day’s weather.

Here it is:


#!/usr/bin/env python

import numpy as np

t = 1

M = np.array([[0.80, 0.65, 0.60],
              [0.10, 0.25, 0.10],
              [0.10, 0.10, 0.30]])

x = np.array([[1],[0],[0]]) #x1

for t in range (1, 15):

     print 't =', t
     print 'x(%d) =' %(t)
     print x[0]
     print x[1]
     print x[2]
     print '\n'

     x = np.dot(M,x)

As you can see, not much to it, really.

Recall that x_t is a vector that contains the current (at time t ) probabilities of the weather either being cloudy (x(1)), rainy (x(2)), or sunny (x(3)). As each day passes, x_{t + 1} = Mx_t where M is the probability transition matrix for the various different states (Cloudy/State 1, Rainy/State 2, Sunny/State 3).

If you iterate this equation multiple times, you get some interesting results:

MarkovPage1

These are the same results that we got by hand before. Now let's do a few more iterations and see what we get:

MarkovPage2

And finally:

MarkovPage3

This is really very exciting; notice how after about 12 iterations, we have a vector that represents stable, long-term probabilities of approximately 76% cloudy days, 12% rainy days, and 12% sunny days. I don't know if that's true or not, but it certainly feels about right! (Of course, with climate change, this just might all be a thing of the past, which would be sad; I like it cloudy.)

Nozarashi o

野ざらしを
心に風の
しむ身かな

Nozarashi o
Kokoro ni kaze no
Shimu mi kana.

– Bashō

My son suggested that I translate this haiku by Bashō. I think he thinks I know more Japanese than I do. But having spent a lot of time with this poem, I’ll give it a try.

It is contained in a book that was published in or around 1685, 野ざらし紀行 (Nozarashi kikō), the title of which is translated in various ways, but my favorite is Journal of Bleached Bones in a Field, a pdf of which can be downloaded here for your reading pleasure.

Basho himself was a very interesting fellow. Born 松尾 金作 (Matsuo Munefusa), he later changed his name to 松尾 芭蕉 (Matsuo Bashō). Apparently he called himself “Bashō,” which means “banana tree” after a tree that grew in the yard of his hut, where he lived more-or-less as a hermit at times. He was a restless person and traveled a lot. At one point his hut burned down; so for a while, at least, he was effectively homeless. He was a practitioner of Zen, and lived a monk-like existence, but as far as I know he was never actually formally a Buddhist monk.

Here’s a picture of Bashō, presumably doing what he did best:

basho_by_hokusai-small.jpg

There are already a number of existing translations of the haiku above, and I am by no means a scholar of Japanese. But I like the way these particular words are arranged, and I find them intriguing.

野ざらしを
Nozarashi o

“Nozarashi” is often translated as “Bleached bones in a field,” because the kanji 野 refers to a “field,” and ざらし or 晒 refers to something “bleached” (presumably y the sun) or exposed. The particle を (pronounced “o”) indicates direction, in a away similar to the preposition “at” or “to.” This is the place where something is happening, the place Basho is seeing or thinking of. So far we have a field and a condition of having been bleached. Where are the bones? As a Zen teacher might say, “they are in your mind.”

心に
Kokoro ni

“Kokoro” is “heart.” に, pronounced “ni,” is another particle indicating direction, in this case it can be thought of as meaning “in” or perhaps also “to” (the way を can). According to one particular resource you can think of を as indicating the direction of action, whereas に is more for the direction of motion. I think を may have more to do with location in this case. Note that a particle in Japanese comes after a word in Japanese where it would typically be used before a word in English.

風の
kaze no

“Kaze” means “spirit” or “wind” (same thing), as in 神風, pronounced “kamikaze,” meaning, “divine wind.” Most people probably associate the kamikaze with suicide pilots during WWII, but this expression was previously used to refer to the typhoons which destroyed Mongol fleets in 1274, and again in 1281, on both occasions saving Japan from invasion. The Japanese were truly under the protection of the gods!

I should mention that I have puzzled over the particle の, pronounced “no,” which usually acts like an apostrophe “s,” indicating possession , but can be very flexible. It can refer to other things, like location, and sometimes it just seems to connect things together. I’m honestly not sure what it means in this case, or if it really means anything. I have suspected that it might be there for rhythm, or just to provide a syllable.

しむ身かな
Shimu mi kana

しむ, “shimu” is a verb that means “pierce.” 身, pronounced “mi” in this instance (Japanese words can often be pronounced a lot of different ways, depending on how they are used) means “body.” The expression かな, “kana,” is something that, as I understand it, is used to represent what we would use an exclamation point for in English. (Kind of like the way よ, “yo,” is used at the end of a Japanese sentence for emphasis.) It also conveniently adds 2 syllables, which helps with the 5-7-5 structure of the poem.

I feel like if I were going to translate this in a way that was closest, perhaps, to the original intent of the author, I might say something like this:

Bleached bones in a field;
The wind pierces me to the heart.

Or, if I were going to expand it a little and try to make it more like a real 5-7-5 haiku in English:

Bleached bones in a field;
The wind pierces my body,
And it chills my heart.

This is a pretty minimalist interpretation, but I think of Haiku as a pretty minimalist form. So there you have it.

A Model of Seattle Weather

TeXmarkov1

My discussion of Markov chains is based largely on what I was able to learn by studying two resources, a paper by Michael Zhang (http://www.eecs70.org/static/resources/markov-chains-michael.pdf) and a book by Steven Boyd and Lieven Vandenberghe, Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares (http://vmls-book.stanford.edu/vmls.pdf), both of which are freely available on the web. What I found most helpful about the Boyd and Vandenberghe book was the way it explained Markov chains as an example of a linear dynamical system, which hadn’t occurred to me before.

Let’s assume a simple (but maybe reasonably accurate) model of Seattle weather. (I’m trying to emphasize how cloudy it is in Seattle because I really like it here, and I don’t want anyone else to come. Please stay away; by the way, it gets cold here, too!) If it’s cloudy (which it is most of the time), then there’s an 80% (0.80) probability that it will be cloudy again tomorrow, a 0.10 probability that it will rain, and a 0.10 probability that it will be sunny. Note that we are considering probabilities for weather events the following day – today is considered a state, we’ll call it x_1, and the new state tomorrow we’ll write as x_2.

Here is a summary of the probabilities of the various possible transitions between states:

TeXMarkovTable1

As you can see, it’s very helpful to have this in the form of a graph, with nodes representing each of the possible states, and directed edges representing the transitions between states. If you go back and take a look at the image above, as well as the list of probabilities, you’ll notice that each state can do one of 3 things; it can remain in the same state the following day, or it can go to one of the other two states. Note that the probabilities of these three transitions for a state sums to 1 – in other words, it has to do something, and, in this model, it can only do one of three things.

We can arrange these probability values more concisely in the form of a matrix, which we will refer to as a transition probability matrix:

\ \\ \begin{array}{lll} P  & = & \left ( \begin{array}{lll} 0.80 & 0.65 & 0.60 \\ 0.10 & 0.25 & 0.10 \\ 0.10 & 0.10 & 0.30 \end{array} \right ) \end{array}

This matrix will be multiplied by the state vector, x_i, where i = t, and t = 1 initially, followed by t = 2, 3, ... on each successive day. The vector x_i contains values for the current probability of the 3 possible states of the system, x(1), x(2), x(3):

\begin{array}{lll} x_i & = & \left ( \begin{array}{c} x(1)\\ x(2)\\ x(3) \end{array} \right ) \end{array}

Notice that each column represents the probabilities of making the transition from a particular state to a new state in the state vector: column 1 represents the probabilities of making the transition from state 1 (the Cloudy state, x(1)), column 2 is state 2 (Rainy, x(2)), and column 3 is state 3 (Sunny, x(3)).

Let’s multiply them together, using x_i = x_1 = {(1, 0, 0)}^T as our initial state probability vector – notice that in the initial state the we know what the conditions are – the weather is cloudy, and so x(1) = 1 and the other states have probability $0&bg=333333&fg=ffffff$. (We are using the transposed row vector in the line above for x_1 for convenience of display, but mathematically we are using the column vector for calculations. It could actually been done another way, but would have required that the matrix be transposed as well, and the transposed matrix would need to be multiplied on the right side of the vector.)

\ \\ \begin{array}{lllll} x_2 & = & Px_1  & = & \left ( \begin{array}{lll} 0.80 & 0.65 & 0.60 \\ 0.10 & 0.25 & 0.10 \\ 0.10 & 0.10 & 0.30 \end{array} \right ) \left ( \begin{array}{c} x(1)\\ x(2)\\ x(3) \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{lll} 0.80 & 0.65 & 0.60 \\ 0.10 & 0.25 & 0.10 \\ 0.10 & 0.10 & 0.30 \end{array} \right ) \left ( \begin{array}{c} 1 \\ 0 \\ 0 \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{c} 0.80 \\ 0.10 \\ 0.10 \end{array} \right ) \end{array}

In this case the result is just the probabilities of column 1. but let’s make it more interesting; let’s multiply the transition matrix by this new state vector which we’ll call x_2 to get x_3, the collection of the probabilities of the various states on the third day.

\ \\ \begin{array}{lllll} x_3 & = & Px_2  & = & \left ( \begin{array}{lll} 0.80 & 0.65 & 0.60 \\ 0.10 & 0.25 & 0.10 \\ 0.10 & 0.10 & 0.30 \end{array} \right ) \left ( \begin{array}{c} 0.80 \\ 0.10 \\ 0.10 \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{c} 0.80\times0.80 + 0.65\times0.10 + 0.60\times0.10\\ 0.10\times0.80 + 0.25\times0.10 + 0.10\times0.10 \\ 0.10\times0.80 + 0.10\times0.10 + 0.30\times0.10 \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{c} 0.765 \\ 0.115\\ 0.120 \end{array} \right ) \end{array}

\begin{array}{lllll} x_4 & = & Px_3  & = & \left ( \begin{array}{lll} 0.80 & 0.65 & 0.60 \\ 0.10 & 0.25 & 0.10 \\ 0.10 & 0.10 & 0.30 \end{array} \right ) \left ( \begin{array}{c} 0.765 \\ 0.115 \\ 0.120 \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{c} 0.800\times0.765 + 0.650\times0.115 + 0.600\times0.120\\ 0.100\times0.765 + 0.250\times0.115 + 0.100\times0.120 \\ 0.100\times0.765 + 0.100\times0.115 + 0.300\times0.120 \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{l} 0.75875\\ 0.11725\\ 0.12400 \end{array} \right ) \end{array}

\ \\ \begin{array}{lllll} x_5 & = & Px_4  & = & \left ( \begin{array}{lll} 0.80 & 0.65 & 0.60 \\ 0.10 & 0.25 & 0.10 \\ 0.10 & 0.10 & 0.30 \end{array} \right ) \left ( \begin{array}{c} 0.75875\\ 0.11725\\ 0.12400 \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{c} 0.800\times0.75875 + 0.650\times0.11725 + 0.600\times0.12400\\ 0.100\times0.75875 + 0.250\times0.11725 + 0.100\times0.12400 \\ 0.100\times0.75875 + 0.100\times0.11725 + 0.300\times0.12400 \end{array} \right ) \\ \\ &&& = & \left ( \begin{array}{l} 0.7576125 \\ 0.1175875 \\ 0.1248000 \end{array} \right ) \end{array}

Notice that even by the second or third day, it’s still looks like it’s going to be cloudy. (Also notice that all the probabilities in the vector x_5 sum to a total of 1, as they should, which is an indicator that we’ve probably done everything right).

There are more interesting things we can do with this (like using R or Python to program a simulation that does multiple iterations), and I may try to do some of that for you in a follow-up post.

Here’s pdf of this post:
TeXmarkov2

 

Markov Chains – Introduction

TeXmarkov1

My daughter recently asked me what Markov Chains are useful for. Whenever someone asks me what a particular piece of mathematics is useful for, I sometimes ask them what music is useful for. There is an answer for that – when I was in the Army, as is well known, we would sing songs while marching and running. The singing has multiple benefits; it increases morale, improves the sense of comradeship among soldiers, and it actually helps you run faster! (At least it helped me.)

However, Markov Chains have all kinds of uses, not the least of which is to model what are called stochastic processes; essentially processes that are distributed according to some probability function. One thing you can do with a model like that is make predictions about the long-term behavior of a system.

In this case the system is Seattle weather; something that people in the Northwest frequently joke about. Contrary to popular opinion, Seattle is not the most rainy city in the world, or even in the country, but it’s definitely one of the cloudiest. What I’m going to try to do here is explain basically what a Markov chain is and how it works, using a model of the weather in my favorite city as an example.

The image above, by the way, was created using \LaTeX and \textrm {Ti}k \textrm {Z} instructions with Tekmaker 5.0.2, which is a really nice \LaTeX editor, except that it has a bad habit of freezing the system whenever I leave out a semicolon. However, you can’t complain too much about free software (my favorite price!).

(To be continued.)