Random Walks and Electric Networks

Peter Doyle

Math 17: Beyond Calculus
Dartmouth College
Winter 2011
(11) MWF 11:15 - 12:20

Contents

• Introduction
• Mon 3 Jan 2011: Getting started
• Wed 5 January 2011
• Portfolio
• For Friday 14 January 2011
• Course organization
• Saturday 8 January 2011
• Office hours
• Monday 10 January 2011
• Creating a zip archive of your portfolio
• For Friday 28 January 2011
• Comments on portfolios
• Wednesday 19 January 2011
• Monday 24 January 2011
• The Cantor-Schroeder-Bernstein theorem in action
• How to learn German and French
• Friday 28 January 2011
• Monday 7 February 2010
• For Thursday 11 February 2010
• Also for Thursday 11 February 2010: Conway's Game of Life
• Wednesday 9 February
• For Wednesday 23 February 2011
• For Thursday 24 February 2011
• For Friday 25 February 2011

Introduction

This course is intended as an introduction to math beyond calculus. It is primarily meant to appeal to first-year students who have completed Math 8, 11, 12, or 13. The idea is to introduce math that is fun, challenging, and important, and prepare and inspire you to major in math.

This is a topics course, with no set material that we have to go through. This year, the focus will be on Polya's theorem that a random walker on an infinite street network in d-dimensional space is bound to return to the starting point when d = 2, but has a positive probability of escaping to infinity without returning to the starting point when d $\geq$ 3. Our goal will be to interpret this theorem as a statement about electric networks, and then to prove the theorem using techniques from classical electrical theory.

We'll be discussing a lot of other topics as well: Polya's theorem is a point of departure, not a fixed destination. Some topics will be more accessible than others, and I don't expect all students to follow everything. There won't be any formal exams, though there will be quizzes on things that I think every student should master. A big emphasis will be on computer explorations, and major independent projects, which will demand a lot of work. A motivated student coming from Math 8 should be able to do fine in the course. At the same time, I hope that a lot of what we do will be challenging to students coming out of Math 12. (There will also be some upperclass students in the class, and I hope they will enjoy it, but the class is primarily aimed at first-years.)

An important component of the course will be learning basic Matlab programming, and the mathematical typesetting language Latex. A good reference for Matlab is Toby Driscoll's `Learning Matlab', which I've ordered as a text for the course:
http://tinyurl.com/driscollmatlab
It's available at Wheelock Books.

The main course text is available free online:
http://www.math.dartmouth.edu/~doyle/docs/walkspdf/walks.pdf
The Latex source is here:
http://www.math.dartmouth.edu/~doyle/docs/walkspdf/walks.zip

Mon 3 Jan 2011: Getting started

Our first class will be Wednesday 5 January. Before then, please email me, telling a little about your math background. Specifically, have you studied probability? Linear algebra? Differential equations? Also, what physics have you studied? Have you done any computer programming? If so, have you used Matlab? And by any chance have you used Latex?

It would be great if you could try installing Matlab on your laptop as soon as possible. Look here:
http://caligari.dartmouth.edu/downloads/matlab/
Note that the installation instructions will be in the README_Install file in the download folder. If you succeed getting this installed, try evaluating these two commands:

x=2*3.^-[1:10]*(rand(10,10^4)<1/2); % Pick points from the Cantor set
stairs([min(x) sort(x)],0:1/length(x):1) % Plot the c.d.f.

You could also try installing Tex. For Mac, go here:
http://www.tug.org/mactex
For Windows, go here:
http://www.tug.org/texlive/windows.html
Use the Texworks front end, which works on both Mac and Windows. Try typesetting the course text:
http://www.math.dartmouth.edu/~doyle/docs/walkspdf/walks.zip
(Be sure to select format pdflatex, which is not the default format, from the drop-down menu next to the green arrow, and hit typeset a couple of times to get the table of contents.)

Let me know how this all goes! If nothing works, don't despair. I just want you to try this now so we can see what problems arise.

Wed 5 January 2011

Matlab

Remember that for Friday, I am asking you to bring your laptops to class, with Matlab up and running. Susan Schwarz, the campus Matlab administrator, has offered her help. You can contact her if you run into questions or problems when installing Matlab. Her email is Susan.A.Schwarz@dartmouth.edu
The key thing is to try this right away, so there is time to get any problems straightened out by Friday. If you can get Tex installed, as well, so much the better.

Remember that, as I mentioned in class today, the Matlab license manager needs an authorized connection to the Dartmouth network while you are using Matlab. Ethernet and Dartmouth Secure work for this; Dartmouth Public does not. Well actually, you can use Dartmouth Public if you fire up VPN:
https://gateway.dartmouth.edu/
Using VPN, you can use Matlab from off-campus.

Taylor series

Please review Taylor series!

Complex numbers

What is a good place to learn about complex numbers? This brief description from MIT has a useful applet:
http://www-math.mit.edu/~djk/calculus_beginners/chapter02/complement01.html
The most exciting things I've found are the games `Complex shoot'
http://wims.unice.fr/wims/en_H6~algebra~compshoot.en.html
and `SQRT shoot' (follow the link from the `Complex shoot' page). The Wikipedia article seems OK, though the diagram illustrating the geometry of multiplication completely misses the boat:
http://en.wikipedia.org/wiki/Complex_number
I'm not thrilled with this Wikibooks offering:
http://en.wikibooks.org/wiki/Algebra/Complex_Numbers
Let me know if you find other useful resources. (For example, you could check your old calculus text.)

The Cantor set

For the Cantor set, one place to look is here:
http://www.cut-the-knot.org/do_you_know/Cantor2.shtml

The Pirates of Penzance

About binomial theorem I am teeming with a lot o' news:
http://en.wikipedia.org/wiki/Major-General's_Song

http://www.youtube.com/watch?v=zSGWoXDFM64

Portfolio

You should begin work on your course `portfolio'. Your portfolio will consist of a single folder with title yourname, which you will bundle into a file yourname.zip and email to me every Wednesday before class. The key ingredient will be a file journal.pdf (with accompanying Latex source journal.tex) which will keep a record of your progress in the course. I will be asking for you to complete specific assignments, e.g. writing programs or answering questions, and among the things your journal should include are your work (or links to your work) on these assignments. This is just a start. Your journal should also describe your independent work associated with the course, and in particular, the progress you make picking and completing major course `projects'.

For Friday 14 January 2011

Here are some samples of how to do probability simulations and computations using Matlab:
http://www.math.dartmouth.edu/~doyle/docs/17/matlab/matlabdemo.m

• Edit the Latex document pretest.tex so that it includes the answers. Include the Latex source and pdf output in your portfolio. The source is here:
  http://www.math.dartmouth.edu/~doyle/docs/17/pretest.tex
  
• Explain the Taylor series for e^z, e^-z, cos z, sin x, cosh z, and sinh z. Explain how to remember them.
• Complete the exercises for Chapter 1 of `Learning Matlab'.
• Using Matlab, find by simulation the probability of reaching 10 before 0 for a random walk on the integers between 0 and 10, as a function of where you start the walk. Find also the expected time to reach 0 or 10.
• Write a Matlab function markov(P, i, n) to simulate n steps of a Markov chain with transition matrix P and starting state i.
• Using Matlab and complex numbers, draw a picture of the Koch snowflake curve.

Course organization

Portfolios and quizzes

I've written above about the portfolio you will be creating, and mentioned that there will be occasional quizzes.

Projects

You will be completing two major course projects, on any mathematical topic of your choice. The two projects will give you a chance to do an investigation on your own. Projects need not involve a Matlab component, though I expect most projects will have one. The first project will be due at the end of the sixth week of the term, or thereabouts. The second project will be due on the last day of classes, when students will present their projects in a poster session. The second project may be either an extension of the first project, or an entirely new project. You may work together in pairs on these projects if you choose.

You will be recording progress on your projects in your portfolios. This is important, because it is the most effective way for me to give you timely feedback. As you can guess, the key to doing a good project is to get going on it early, and get plenty of feedback on how it is going.

Grading

Grades will be subjective, based on my assessment of what students have put into and gotten out of the course. I will take into account your portfolios, projects, quiz scores, and class participation.

Honor Code

Students are encouraged to work together on homework assignments. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

On projects, no copying of text, computer code, or graphics will be permitted without prior written permission from me.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

Sources

The preceeding sections on Honor Code and Disabilities were cribbed from Pete Winkler's Math 100 webpage.

Saturday 8 January 2011

I've had some questions about the first assignment, in light of which I am realizing that it had better be due next Friday.

Some comments.

• The purpose of having you edit in the answers to the pretest is to make sure you understand what the correct answers are, and to give you a little practice with Latex. On Monday we can work on Latex. Also, we can discuss the answers that we didn't go over.
• The main purpose of having you write about the Taylor series for e^z and its relatives is that you come to understand and remember these series, The best way to understand something is to try to explain it. Imagine that someone has asked you to explain what the deal is with all these series, and how you can remember them. What would you say, or rather, write? In Latex, of course. Because another goal here is to practice writing in Latex.
• As for Markov chains and the Koch snowflake, on Monday we will discuss these, and how to deal with them in Matlab. Of course you can look them up before that!
• Regarding how to present the results of Matlab investigations, one very good way is by using a Matlab notebook, like the matlabdemo.m notebook linked to above. From this you can publish to html, and from there print to pdf:
  http://www.math.dartmouth.edu/~doyle/docs/17/matlab/matlabdemo.pdf
  Another option is to export your notebook to Latex. We will discuss this on Monday!

Office hours

My proposal is to hold office hours 12-2 Tuesday, overlapping the x-hour, plus by appointment. That way I know people are guaranteed to be free for at least part of the time. I'm always free right after class, but that doesn't work for people who have a class at 12. I might also arrange other set times if we can find times that work for everyone, or almost everyone.

Monday 10 January 2011

RWEN, section 1.1

For tomorrow (Tuesday), please read section 1.1 (`Random walks in one dimension') of RWEN (`Random walks and electric networks'):
http://www.math.dartmouth.edu/~doyle/docs/walkspdf/walks.pdf
This will get you started with random walks and Markov chains.

Learning Matlab, chapters 2 and 3

Realistically, you are going to want to read most of Chapters 2 and 3 of `Learning Matlab' in order to simulate Markov chains, and draw the Koch curve.

Matlab programs for Markov chains

Sample Matlab programs to simulate Markov chains can be found here:
http://www-math.bgsu.edu/z/ap/
You can refer to these to learn how to do such simulations, but you should write your own for the homework assignment.

The Koch curve

I would like you to use complex numbers to plot the Koch curve. A quick search turns up a Matlab program that plots the Koch curve, without using complex numbers, and maybe a more diligent search would turn up something closer to what I am looking for. But...

Creating a zip archive of your portfolio

On the Mac, in the Finder, click to highlight the folder entitled yourname, and then select Compress "yourname" from the File menu. This will create a file yourname.zip, suitable for attaching to an email message.

(If some Windows user wants to send me instructions for Windows, I'll post them here.)

For Friday 28 January 2011

• Do the exercises from chapters 2 of Learning Matlab. Read chapter 3, and practice the programming techniques introduced there.
• Read sections 1.2.1-1.2.5 or RWEN and do exercises 1.2.1-1.2.8.

Comments on portfolios

I realize that this first assignment was over the top. In particular, most people did not get to the simulation problems. Don't worry, we keep after this.

Please make sure that the zip file you submit is called yourname.zip, and contains a file journal.pdf, with accompanying tex source journal.tex. This file should link to all other elements of your portfolio, for example, other tex documents, and Matlab programs and output.

For Matlab, it looks like the easiest way to present it is via Matlab notebooks, which can be published to html, whence to pdf, or directly to pdf.

I'm impressed at how well Latex is working out for most of you, given that we haven't discussed it at all in class. Among issues we'll want to discuss are:

• ``foo'' versus "foo".
• x versus x.
• cos versus cos.
• (${\frac{{1}}{{2}}}$)⁵ versus $\left(\vphantom{ \frac{1}{2} }\right.$${\frac{{1}}{{2}}}$$\left.\vphantom{ \frac{1}{2} }\right)^{5}_{}$.
• ^. versus *.
• Displayed equations.
• The verbatim environment for code, etc.
• Links to other files, e.g. Matlab notebooks.

Here is a useful link one student discovered, from the Harvard math department:
http://www.math.harvard.edu/texman/

Wednesday 19 January 2011

The slide rule:
http://en.wikipedia.org/wiki/Slide_rule

Benford's law:
http://en.wikipedia.org/wiki/Benford's_law

Fractal dimension:
http://en.wikipedia.org/wiki/Fractal_dimension

http://en.wikipedia.org/wiki/List_of_fractals_by_Hausdorff_dimension

Countable sets:
http://en.wikipedia.org/wiki/Countable_set

The real numbers are uncountable:
http://en.wikipedia.org/wiki/Cantor's_diagonal_argument

Monday 24 January 2011

I've modified the current assignment, now due the coming Friday (see above). Instead of having you do the exercises from Chapter 3, I'm just asking you to read it, and practice the programming techniques introduced there. Perhaps I haven't emphasized that the way to learn a programming language is to play around with it. You shouldn't expect to be able to do the Chapter 3 exercises right off the bat, unless you already know basic tricks of programming from having programmed before in some other computer language. The programming problems from RWEN are simpler and more directly relevant to us, so let's concentrate on these. Of course, if you have already done some or all of the Chapter 3 exercises, that's great: Be sure to include this in your journal!

| A| $\leq$ | B| $\wedge$ | B| $\leq$ | A| $\Rightarrow$ | A| = | B|:
http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theorem

The World's Largest Matrix Computation:
http://www.mathworks.com/company/newsletters/news_notes/clevescorner/oct02_cleve.html

The Cantor-Schroeder-Bernstein theorem in action

Let A and B be the open and closed intervals with endpoints -1, 1:

A = {x $$\in$$ R : - 1 < x < 1};

B = {x $$\in$$ R : - 1 $$\leq$$ x $$\leq$$ 1}.

Define injections f : A$\to$B, f (x) = x and g : B $\mapsto$ A, g(x) = x/2. Find the bijection h : A$\to$B produced by the proof of the Cantor-Schroeder-Bernstein theorem.

How to learn German and French

A mathematician needs to be able to read, or at least decipher, texts written in German and French, as these were the standard languages of mathematical discourse from the early 19th century through the beginning of the 20th century. Before that, Latin prevailed, so it would be good to be able to read Latin as well. And Russian!!

One way to learn to read German or French is to learn to speak them. For French, check out the free online video course `French in Action':
http://www.learner.org/resources/series83.html
This course proceeds slowly enough that you can likely learn French just by watching the videos, which are free online. Another good resource is the French Basic course developed by the United States Foreign Service Institute, which is available free online:
http://fsi-language-courses.org/Content.php
This course has no video component, and it seems to blast right off, so it would be best to watch `Franch in Action' first.

For German, I am sorry to see that the the video course `Fokus Deutsch' is no longer freely available as it was previously, though it's probably still out there somewhere. I cannot personally vouch for the FSI German Basic Course, but I think it would be a good bet.

Spanish is not so necessary for mathematics, but the online resources for learning it are superb. Foremost is the free video series `Destinos':
http://www.learner.org/resources/series75.html
And the FSI Spanish Basic course is great. (Some people complain that it is boring, but they are wrong.) Another fantastic resource is the ability to watch telenovelas online, e.g. `Betty la Fea':
http://www.youtube.com/view_play_list?p=6EF0917BD301C519
After that you'll be ready for `Don Quijote', which is a lot better than you probably think if you've tried to read it in English translation:
http://www.amazon.com/Quijote-Mancha-Tomo-Quixote-Part/dp/B000UB3HBS

http://www.amazon.com/Quijote-Mancha-Tomo-Quixote-Part/dp/B000UB3HC2

Friday 28 January 2011

James Fenimore Cooper, The Prairie:
http://www.gutenberg.org/ebooks/6450
Mark Twain, Fenimore Cooper's Literary Offenses:
http://www.pbs.org/marktwain/learnmore/writings_fenimore.html

Ordered pairs:
http://en.wikipedia.org/wiki/Ordered_pair

Dedekind cuts:
http://en.wikipedia.org/wiki/Dedekind_cut

You might want to read and try to decipher the formal axioms of Zermelo-Fraenkel set theory:
http://en.wikipedia.org/wiki/Zermelo-Fraenkel_set_theory

Monday 7 February 2010

Here are links for topics we've raised over the past week. (Some are more technical than I would like.)

Osculating circle:
http://mathworld.wolfram.com/OsculatingCircle.html
(I don't like the fact that you can't see that generically the curve crosses its osculating circle.)
http://www.ies.co.jp/math/java/calc/curve/curve.html
(Applet 1 shows the curve crossing the osculating circle; Applet 2 doesn't work for me.)

Principal curvatures and Gaussian curvature:
http://en.wikipedia.org/wiki/Principal_curvature

http://en.wikipedia.org/wiki/Gaussian_curvature
(Both are technical, but have some good pictures.)

Theorema Egregium:
http://en.wikipedia.org/wiki/Theorema_Egregium
(Look for the animation showing the deformation of a helicoid into a catenoid.)

Trefoil knot:
http://en.wikipedia.org/wiki/Trefoil_knot
Note the parametric formula.

Also try typing knot in Matlab.

Figure-8 knot:
http://en.wikipedia.org/wiki/Figure_eight_knot_(mathematics)
Again, note the parametrization.

The Borromean rings:
http://en.wikipedia.org/wiki/Borromean_rings

Euler characteristic:
http://en.wikipedia.org/wiki/Euler_characteristic

Angle defect and Decartes' theorem
http://en.wikipedia.org/wiki/Defect_(geometry)

The real projective plane:
http://en.wikipedia.org/wiki/Real_projective_plane

The Euclidean algorithm:
http://en.wikipedia.org/wiki/Euclidean_algorithm

The Gaussian integers:
http://en.wikipedia.org/wiki/Gaussian_integer
Note the picture of the Gaussian primes.

For Thursday 11 February 2010

1. Finish up previous assignments. Don't worry about RWEN problem 1.2.5; if you do it, bear in mind that by `monotonically increasing' we mean `weakly monotonically increasing', i.e. non-decreasing.
2. Write from scratch Matlab code to compute the g.c.d. of integers a and b using the Euclidean algorithm. Make sure your code covers all cases (a and b positive, negative, or zero).
3. Use your g.c.d. code to color the squares of an (n + 1)-by-(n + 1) grid so that square a, b is red if gcd(a - 1, b - 1) = 1 and blue otherwise.
4. Write from scratch Matlab code to determine if a + bi is a Gaussian prime.
5. Color in the Gaussian primes as in 3 above.

Also for Thursday 11 February 2010: Conway's Game of Life

Implement Conway's Game of Life. Try it out for some of the patterns given in these links:
http://en.wikipedia.org/wiki/Conway's_Game_of_Life

http://www.math.com/students/wonders/life/life.html
When you're sure your program is working, try it for Gosper's glider gun:

m=zeros(9,36);
m(5:6,1:2)=ones(2);
m(3:9,11:18)=[...
    0 0 1 1 0 0 0 0;...
    0 1 0 0 0 1 0 0;...
    1 0 0 0 0 0 1 0;...
    1 0 0 0 1 0 1 1;...
    1 0 0 0 0 0 1 0;...
    0 1 0 0 0 1 0 0;...
    0 0 1 1 0 0 0 0];
m(1:7,21:25)=[...
    0 0 0 0 1;...
    0 0 1 0 1;...
    1 1 0 0 0;...
    1 1 0 0 0;...
    1 1 0 0 0;...
    0 0 1 0 1;...
    0 0 0 0 1];
m(3:4,35:36)=ones(2);

Hints: The key step is to determine, for given state matrix m and row and column indices a, b, what the state should be at a, b next time. It will help to assume that (for an n₁-by-n₂ matrix) 1 < a < n₁ and 1 < b < n₂. Then you just need some nested loops to fill in the new matrix M. Set m = M and you're done. Well, almost: There will be problems at the border unless, before you do anything else, you make sure that the first and last two rows and columns are all 0. if not, replace m with an (n₁ + 4)-by-(n₂ + 4) matrix, with the old m in the middle. Now put everything inside a loop where you display the grid (use image) and pause briefly (use pause) after every step.

Wednesday 9 February

Turing machine:
http://en.wikipedia.org/wiki/Turing_machine
Turing machine applet (it so cool!):
http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html
An `real' Turing machine:
http://www.snotr.com/video/4545
A toy Turing machine built with Lego:
http://legoofdoom.blogspot.com/

Turing's thesis:
http://en.wikipedia.org/wiki/Church–Turing_thesis

The halting problem:
http://en.wikipedia.org/wiki/Halting_problem

The four color theorem:
http://en.wikipedia.org/wiki/Four_color_theorem
The dual graph:
http://en.wikipedia.org/wiki/Dual_graph
Planar graphs and Kuratowski's theorem:
http://en.wikipedia.org/wiki/Planar_graph

Fermat's last theorem:
http://en.wikipedia.org/wiki/Fermat's_Last_Theorem

The 3x + 1 problem:
http://en.wikipedia.org/wiki/Collatz_conjecture

For Wednesday 23 February 2011

• Fix your Matlab code to check for Gaussian primes by trying out the obvious possibilities.
• Write a program (any program!) for the Turing machine applet:
  http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html
  

For Thursday 24 February 2011

Prepare for a 20 minute meeting with me to discuss progress on your project.

For Friday 25 February 2011

Prepare to give a 5 minute class presentation describing what your project is, and what progress you have made on it. WARNING: 5 minutes is a very short time!