Stochastic methods and algorithms

Instructor. Motoya Machida, Tennessee Technological University. (E-mail: mmachida@tntech.edu)

Class meeting/zoom session. 10:45–12:25am (Tokyo time), Wednesday from June 11 until July 23, 2025. Lectures will be given in English, broadcasted live, and recorded for participants to watch later at their convenience. Meetings take place at the classroom (M-134), and zoom invitation will be sent to participants. While we encourage you to attend the class in person, you may choose to join the Zoom session remotely and take advantage of maximum flexibility. All other class presentation materials will be made available here.

Description of the course. When a function of interest is intractable, one may view it as a density function proportionally, and seek the characteristics of function by Monte Carlo simulation. Stochastic methods and their algorithms become indispensable in designing iterative/recursive procedures with randomness, and they are often viewed as discrete-time stochastic processes. We begin with an introduction of Monte Carlo methods, explore various ideas of stochastic approach, and relate them to particular algorithms. Lecture presentation is interspersed with demonstrations in R. The tentative coverage of topics is listed as follows.

Date	Lecture contents	lecture pdf	R code	r sources
June 11/June 18	Motivation for stochastic methods/Rejection algorithm	lecture01.pdf	demo01.R	nm.r, search.r
June 25	Markov chain Monte Carlo methods/Metropolis algorithm	lecture02.pdf	demo02a.R, demo02b.R	bwalk.r, metro.r, psrf.r
July 2/July 9	Discrete structure and Gibbs sampler/Gibbs algorithm	lecture03.pdf	demo03.R	potts.r
July 16/July 23	How long should you run it?/Perfect sampling algorithms	lecture04.pdf
(July 23)	Hidden Markov model and dynamic decision making/Viterbi algorithm	lecture05.pdf	demo05.R	dynamic.r, hmm.r, needleman.r, gene57.txt, fli9.txt
(July 23)	Brownian motion and sampling/Langevin algorithms	lecture06.pdf		bm.R
(July 23)	Quantum computation and sampling/Shor's algorithm	lecture07.pdf

R code. R is free software/platform for statistical computing and graphics, and R code is made available for you to run it in your own machine. R can be installed on Windows, Linux, and Mac, and downloaded from CRAN R project. Each “command” is executed in an interactive manner, known as “interpretor,” and is requested in a form of “function.” For example,

> x <- c(3,1,2)

is the instruction to create an array x which contains the values of 3,1,2.

R source files. R functions are prepared as external source files (usually with extension ".r" or ".R"), and must be sourced in R in advance with the command

> source("[script filename]")

Or, call it by

> source(file.choose())

and choose a source file interactively.

Working directory. Your external source files must be found in the working directory and recognized by R. You can always change the working directory from R via [File]->[Change dir...]. Alternatively you can set the working directory by

> setwd("[pathname]")

R Studio. On top of R you may want to use R Studio. It is an integrated development environment (IDE) for R. Follow their instruction to download and install DESKTOP R STUDIO in your PC.