It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.2K
- Applied Category Theory Course 352
- Applied Category Theory Seminar 4
- Exercises 149
- Discussion Groups 49
- How to Use MathJax 15
- Chat 479
- Azimuth Code Project 108
- News and Information 145
- Azimuth Blog 149
- Azimuth Forum 29
- Azimuth Project 189
- - Strategy 108
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 711
- - Latest Changes 701
- - - Action 14
- - - Biodiversity 8
- - - Books 2
- - - Carbon 9
- - - Computational methods 38
- - - Climate 53
- - - Earth science 23
- - - Ecology 43
- - - Energy 29
- - - Experiments 30
- - - Geoengineering 0
- - - Mathematical methods 69
- - - Meta 9
- - - Methodology 16
- - - Natural resources 7
- - - Oceans 4
- - - Organizations 34
- - - People 6
- - - Publishing 4
- - - Reports 3
- - - Software 21
- - - Statistical methods 2
- - - Sustainability 4
- - - Things to do 2
- - - Visualisation 1
- General 39

Options

From course taught by Glen Takahara at Queens University at Kingston:

Good exposition of concepts, combining informal language with mathematical precision. Calculations get laborious at times.

## Comments

Notes from Introduction.

Examples of stochastic systems: CPU with jobs arriving in random fashion; network multiplexor with packets arriving randomly; a store with random demands on its inventory.

Prob. A monkey hits keys on a typewriter randomly and forever. Show that he eventually types the complete works of Shakespeare with probability 1.

Ans. Show that the probability that he never types the complete works is zero. Let \(S\) be the string, of length \(n\), that is the complete works of Shakespeare. Let \(A\) be the set of infinite strings that do not contain \(S\) anywhere as a substring, and let \(B\) be the set of infinite strings that do not contain \(S\) as a substring starting at an index which is a multiple of \(n\). Then \(A \subseteq B\), so \(Prob(A) <= Prob(B)\). Now, \(Prob(B) = (1 - x) ^ \infty = 0\), for small positive value \(x\). So \(Prob(A) = 0\).

Prob. Suppose that in 1 week a chicken will lay N eggs, where N is a random variable with Poisson(\(\lambda\)) distribution. Also each egg has probability \(p\) of hatching a chick. Let \(X\) be the number of of chicks hatched in a week. What is \(E[X]\)?

Ans. Simple and clear: \(E[X] = \lambda * p\).

The proof involves conditioning on the event \(N = k\).

`Notes from Introduction. Examples of stochastic systems: CPU with jobs arriving in random fashion; network multiplexor with packets arriving randomly; a store with random demands on its inventory. Prob. A monkey hits keys on a typewriter randomly and forever. Show that he eventually types the complete works of Shakespeare with probability 1. Ans. Show that the probability that he never types the complete works is zero. Let \\(S\\) be the string, of length \\(n\\), that is the complete works of Shakespeare. Let \\(A\\) be the set of infinite strings that do not contain \\(S\\) anywhere as a substring, and let \\(B\\) be the set of infinite strings that do not contain \\(S\\) as a substring starting at an index which is a multiple of \\(n\\). Then \\(A \subseteq B\\), so \\(Prob(A) <= Prob(B)\\). Now, \\(Prob(B) = (1 - x) ^ \infty = 0\\), for small positive value \\(x\\). So \\(Prob(A) = 0\\). Prob. Suppose that in 1 week a chicken will lay N eggs, where N is a random variable with Poisson(\\(\lambda\\)) distribution. Also each egg has probability \\(p\\) of hatching a chick. Let \\(X\\) be the number of of chicks hatched in a week. What is \\(E[X]\\)? Ans. Simple and clear: \\(E[X] = \lambda * p\\). The proof involves conditioning on the event \\(N = k\\).`

From Introduction, cont'd.

Analysis of QUICKSORT.

QUICKSORT(\(x_1, ..., x_n\)):

If \(n = 0\) or \(n = 1\), no sorting needing, so return.

Randomly choose \(x_i\).

Divide up the remaining values into two sets \(L\) and \(H\), where \(L\) is the set of values less than or equal to \(x_i\), and \(H\) is the set of values greater than \(x_i\).

return QUICKSORT(\(L\)), \(x_i\), QUICKSORT(\(H\))

`From Introduction, cont'd. Analysis of QUICKSORT. QUICKSORT(\\(x_1, ..., x_n\\)): If \\(n = 0\\) or \\(n = 1\\), no sorting needing, so return. Randomly choose \\(x_i\\). Divide up the remaining values into two sets \\(L\\) and \\(H\\), where \\(L\\) is the set of values less than or equal to \\(x_i\\), and \\(H\\) is the set of values greater than \\(x_i\\). return QUICKSORT(\\(L\\)), \\(x_i\\), QUICKSORT(\\(H\\))`

The number of comparisons QUICKSORT makes to sort a list of \(n\) values is a random variable.

Let \(X_n\) be the number of comparisons QUICKSORT makes to sort a list of \(n\) values, and let \(M_n = E[X_n]\).

Let \(Y\) be rank of the number \(x_i\) that is chosen. I.e., \(Y = i\).

Condition on \(Y\) and use the Law of Total Expectation to get:

$$ M_n = E[X_n] = E[E[X_n|Y]] = \sum_{j=1}^{n} E[X_n|Y=j] * 1/n $$ Next,

$$ E[X_n | Y = j] = n - 1 + E[X_{j-1}] + E[X_{n-j}] $$ because \(n = 1\) comparisons are required to partition the values into \(L\) and \(H\), and the other two terms stem from the recursive structure of the algorithm.

...

After grinding through the calculation, the final result is:

$$ M_{n+1} = (n + 2) \sum_{i=1}^{n} \frac{2i}{(i+1)(i+2)} $$ which has complexity \(n\) log \(n\).

`The number of comparisons QUICKSORT makes to sort a list of \\(n\\) values is a random variable. Let \\(X_n\\) be the number of comparisons QUICKSORT makes to sort a list of \\(n\\) values, and let \\(M_n = E[X_n]\\). Let \\(Y\\) be rank of the number \\(x_i\\) that is chosen. I.e., \\(Y = i\\). Condition on \\(Y\\) and use the Law of Total Expectation to get: \[ M_n = E[X_n] = E[E[X_n|Y]] = \sum_{j=1}^{n} E[X_n|Y=j] * 1/n \] Next, \[ E[X_n | Y = j] = n - 1 + E[X_{j-1}] + E[X_{n-j}] \] because \\(n = 1\\) comparisons are required to partition the values into \\(L\\) and \\(H\\), and the other two terms stem from the recursive structure of the algorithm. ... After grinding through the calculation, the final result is: \[ M_{n+1} = (n + 2) \sum_{i=1}^{n} \frac{2i}{(i+1)(i+2)} \] which has complexity \\(n\\) log \\(n\\).`