## Description

1. Prove that for all n ≥ 1 and 1 ≤ k < n:

n

k

+

n

k + 1

=

n + 1

k + 1

.

2. (a) How many well-formed formulas can be constructed from one ∨; one

∧; two parenthesis pairs (,); and the three literals p, ¬p, and q?

(b) Under the equivalence relation defined by logical equivalence, how

many equivalence classes do the formulas in part (a) form?

3. Suppose you are trying to negotiate a maze and you are stuck with a

number of choices:

• Option A takes you to the exit in 5 minutes,

• Option B returns you to your current position after 3 minutes,

• Option C takes you to the exit in 8 minutes, and

• Option D returns you to your current position after 2 minutes.

(a) Suppose you make your choice uniformly at random, and if you return

to your current position you are unable to recall any of your previous

choices, so you always choose from all four options. What is your

expected time for exiting the maze?

(b) Suppose now you can remember any choice which returned you to

your current position, and you choose uniformly at random from

your unexplored options. What is your expected time for exiting the

maze?

4. Consider the following graph:

v1 v2 v3 v4

Consider the following process:

• Initially, start at v1.

• At each time step, choose one of the vertices adjacent to your current

location uniformly at random, and move there.

Let p1(n), p2(n), p3(n), p4(n) be the probability your location after n time

steps is v1, v2, v3, or v4 respectively. So p1(0) = 1 and p2(0) = p3(0) =

p4(0) = 0.

1

(a) Express p1(n + 1), p2(n + 1), p3(n + 1), and p4(n + 1) in terms of

p1(n), p2(n), p3(n), and p4(n).

(b) As n gets larger, each pi(n) converges to a single value (called the

steady state) which can be determined by setting pi(n + 1) = pi(n)

in the above equations. Determine the steady state probabilities for

all vertices.

(c) What is your expected distance from v1 in the steady state?

Comment: This is an example of a Markov chain – a very useful model for stochastic processes. This particular Markov chain

is modelling a (bounded) 1-dimensional random walk, also a very

common model with applications in many scientific fields.

5. Consider the following graph:

(a) Suppose you colour each vertex one of three colours chosen uniformly

at random. What is the probability you get a valid 3-colouring of the

graph?

(b) Suppose you orient each edge (e.g. top to bottom, left to right)

and choose, for each oriented edge, one of six “colour pairs” (i.e.

(red, blue), (red, green), (green, blue), (blue,red), (green,red), or (blue, green))

uniformly at random.

Each colour pair indicates how you colour the

two vertices of the oriented edge – e.g. if (u, v) is given (green, blue)

then u is coloured green and v is coloured blue. Note that a vertex

may be given more than one colour, in which case the colouring is

not valid. What is the probability you get a valid 3-colouring using

this process?

2

## Advice on how to do the assignment

All submitted work must be done individually without consulting someone else’s

solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.

• Assignments are to be submitted via WebCMS (or give) as a pdf

• Be careful with giving multiple or alternative answers. If you give multiple

answers, then we will give you marks only for ”your worst answer”, as this

indicates how well you understood the question.

• Some of the questions are very easy (with the help of the lecture notes or

book). You can use the material presented in the lecture or book (without

proving it). You do not need to write more than necessary (see comment

above).

• When giving answers to questions, we always would like you to prove/explain/motivate your answers.

• If you use further resources (books, scientific papers, the internet,…) to

formulate your answers, then add references to your sources.

3