Home‎ > ‎

Week 7

I did a number of things this week.

On Monday, Lenore and I brainstormed a few more questions that I could look into. For instance, we wanted to know: If you bound the diameter of the graph, does DSD get bounded as well? My goal was to come up with a few conjectures about DSD and random walks. Later that day, her husband came and gave a mini lecture on operating systems. He spoke about the history of operating systems (briefly covering UNIX and MS-DOS), early programming languages and how they  were associated with assemblers and compilers, as well as other computer architecture concepts. It was a very informative session.

The highlight for Tuesday was me presenting my mathematical findings to the other students and brainstorming ways to prove the intermediate step I was stuck on. I worked through an example of computing the DSD value for a complete graph of five nodes with varying random walks. After explaining my work, we went through the computation of DSD by hand once again to try to prove my claim. For a five-noded network, we listed the weight  corresponding to the start node and other nodes in a table with varying length of random walks (given that initially one node had weight 1 and at each step, the weight at each node was equally distributed to the other nodes):
 m  0  1  2  3
 s  1  0  1/4  3/16
 a  0  1/4  3/16  13/64

Here, m corresponds to the length of the random walk, s corresponds to the weight at the initial node, and a corresponds to the weight at the other nodes. It can be seen that the weight of the start node at step j is equal to the weight of the other nodes at one step prior. After looking at this, we tried to come up with a generalized formula to compute DSD at the "all" nodes for a random walk of length m on a graph with five nodes: 2 - 2((4m - (-1)m) / (4m * 5)) . I then looked at a graph with four nodes and generalized this formula to a graph with n+1 nodes: 2 - 2((nm - (-1)m) / (nm * (n+1))).

I spent the following days looking at minimum and maximum DSD values on various trees, paths, and other graphs on 3,4, and 5 nodes. While observing these, I noticed that many graphs with the same number of nodes had the same minimum DSD value regardless of their shape. I found that these minimum values also followed the sum of the reciprocals of  triangular numbers pattern that the complete graphs did previously. With that, I came to another conjecture: The minimum non-zero DSD value for a path with n nodes is the DSD value corresponding  to the complete graph of 2n - 2 nodes. Here, path refers to a straight line such as
o-o-o.

This weekend, I went to Boston Public Market. There was a farmers market going on when I went, which was a highlight because the produce there was not that pricey (as opposed to grocery stores and other farmers markets I went to). I didn't bring a bag, so I'm thinking of going there again to buy my groceries. The following day, I went on a boat ride tour that showed me lighthouses near and around Gloucester. It was nice seeing them; although, I have to admit, it was equally as nice seeing the expensive summer homes that were next to them.

Comments