Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Maths 162: Computational Mathematics

Assignment 3

        Note that the questions are ordered by topics and NOT by difficulty. If question 1 seems hard, don’t assume that the other questions will be harder, they will just be different.

        For each question, work through as far as you can - even if you cannot get a complete/perfect answer, write what you can. As the main idea is to demonstrate your understanding of the ideas, methods and programming, do include all your working and your MATLAB code along with the answers that you get from your MATLAB code.

        Full marks: 20 marks.

Getting help:

● No cheating. You are allowed to discuss with others how to go about a question, but you must produce your own computations and write your answers by yourself.

● Course material: the course book, your notes from lectures, and the tutorials all provide helpful information for answering the assignment questions. There is also the Coder’s guide to programming and the Spider’s guide to Cobwebs.

● Help files in MATLAB: One way to find information about a particular MATLAB function is to type help in the MATLAB Command Window followed by the name of the function. For example, to get help with using sqrt , the square root function, type help sqrt . This gives basic information. For more information, you can click on the link to the Help browser (i.e., the question mark at the top of the MATLAB window.)

● Office Hours: Priya will be holding office hours in Gather, upstairs in the tutorial room, 2:30-3:30pm on Monday, and 3:30-4:30pm on Tuesday.

● How to submit: This assignment is to be submitted online through Canvas as a single ZIP or PDF file, containing answers for all questions, your workings, any figures, and code in a sensible order. This is practise for how you will be submitting your answer script for the final exam. Make sure you name your programs and figures appropriately including the question number in its title. It will be very helpful to start new questions in a new page, similar to how the questions each start on a new page!

1   Probability paradox (5 marks)

What this question is checking? This question is checking how comfortable you are with reading a given Matlab function and understanding what it does. The first part involves writing comments in a given function to explain what is being done in each line. The second part then checks if you can use the given function to obtain a figure for different input values NP. This involves writing a loop and storing the output in each case for availability later.

The birthday paradox or the birthday problem is the result that in a group of NP randomly chosen people, some pair of them will share their birthday. Given that there are a possible 366 days in a year (with February 29 included), and any day being equally probable as a birthday, we expect that the probability for a pair to share their birthday to be greater than 50% when NP > 188 (i.e., 366/2). But we will see that when we compute the probability of sharing a birthday, we need a group of only NP = 23 random people to have a probability of a pair sharing their birthday more than 50% of the time!

Up on the canvas page, attached to this assignment is a MATLAB file called ‘birthday.m’. It contains a function which takes in as input the number N of random people in a group and outputs the probability that at least one pair of the individuals share a birthday.

(a) Read the birthday.m file and comment it to explain what each line does. Rename the commented file as ‘birthday commented.m’ and add it to your response.    [3 marks]

(b) Now write a program called birthdayparadox.m where you vary the number of NP individuals from NP = 1 till NP = 100 and plot a figure with NP on the x−axis and the probability that you get for at least a pair share their birthday for that given number of NP people, along the y−axis. Include both your file ‘birthdayparadox.m’ and saved figure (call it ‘fig1b_birthday.pdf’).    [2 marks]

        This picture should look like the figure that you see on the Wikipedia page explaining the birthday paradox.

2   Networks (5 marks)

What this question is checking? This question revises the concept of important vertices in a graph and compares the definition of ‘closeness’ as an alternative to the degree of a vertex. It checks if you are able to think of a network to show the difference between degree and closeness of a vertex. Finally, this question checks if you are able to interpret this concept in the context of actors in cinema.

        In class, when we were studying social networks we said that one way to identify important vertices in a graph was to look at their degrees: i.e. if a vertex has high degree, it’s likely important in the network we’re studying, as it’s connected to many other things! However, there are other notions out there for centrality. Consider the following concept of closeness:

        ——————

        DEFINITION: Given a simple graph G and vertices x, y ∈ G, recall that we defined the distance from x to y, denoted d(x, y), as the smallest number of edges needed in a path from x to y.

For any vertex y, we define its farness f(y) as the sum  d(x, y); i.e. take y, find the distance to every other vertex x in our graph, and add them up; this gives you a measure of how “far” y is from all other vertices. We then define the closeness of y as 1/f(y); this measures how “close” y is to all other vertices.

        ——————

        Closeness can be a better measure of centrality than degree in many situations. An example: make Auckland into a graph, where vertices are locations and edges are roads. Suppose that you wanted to open a COVID-19 testing centre. If you did this at a vertex with high degree, it would have lots of roads leaving it, but might be far away from many people. However, if you picked a vertex with high closeness, you’d minimize the overall travel time for people coming from any location to be tested (better!)

(a) Measure the closeness of all the vertices in the graph shown at right.    [2 marks]

(b) In the graph at right, the vertex with the largest closeness value was also the vertex with the largest degree. This is not always true! Create a graph where none of the vertices with largest degree are vertices with largest closeness value. Make sure to show your working.    [2 marks]

(c) Six Degrees of Kevin Bacon is a game people play on the the costar graph on all actors, where we connect two actors by an edge when they’re costars. To play, someone names an actor. Other people then try to find the shortest chain of actors in the costar graph that links them to Kevin Bacon. (See this website for many examples!)

The name of the game comes from the belief that all actors can be linked to Kevin Bacon in 6 or less steps, as he’s done a ton of work across many different film genres. What does this mean about Kevin Bacon’s closeness in the costar graph?    [1 marks]

3   Random Walk (5 marks)

What this question is checking? This question is checking your ability to extract information about probabilities from the given graph. Using that information, you can either calculate the probability of the corgi ending up at home using pen and paper or via writing a Matlab program.

        We’re trying to model a corgi randomly walking through a neighbourhood. Consider the following graph with loops, which we’re using as a simplified model of our neighbourhood:

There are in this world four possible locations: H, the corgi’s home, B, an all-devouring black hole that absorbs everything that accidentally wanders into it, and two intermediate locations x and y.

        We assume that our corgi, left to its own devices, will randomly wander between these locations. Specifically: if it is at some vertex that is neither H nor B at time t, at time t + 1 it will choose a neighbouring vertex uniformly at random and wander there.

        If the corgi ever makes it home (i.e. wanders to H,) it is safe and goes merrily to sleep. If it wanders to B, however, it is sucked into the black hole and never will be seen again.

        Suppose the corgi starts at x. What are the corgi’s chances of making it home? Prove your claim.

        Hint: Start by thinking about the corgi’s chances of making it home starting from any vertex v, not just x and denote this probability as p(v). Determine this probability for different places in the neighbourhood.

4   Markov chains (5 marks)

What this question is checking? This question is checking your ability to compare different transition probabilities (given in a transition matrix) and to write a program to return the best probable time estimate for a random walk starting at a location i reaches the location j in k steps.

        Write a function ‘bestMarkov.m’ with comments explaining the steps. It should take in as input a n × n matrix A that is the transition matrix for a Markov chain, as well as integers i, j, m. For each value of k from 1 to m, it should calculate the probability of going from state i to state j in k steps in our Markov process. With this done, it should return the value of k for which this probability is the largest.

        (In this sense, ‘bestMarkov.m’ tells you the time by which a random walk starting at i is most likely to have arrived at j!)