DIMACS
DIMACS REU 2019

General Information

me
Student: Jan Petr
Office: 450
School: Charles University, Prague
E-mail: jp1771 [at] scarletmail [dot] rutgers [dot] edu
Project: Random walks with 'geodesic bias'
Coworkers: Mikhail Beliyaeu, Petr Chmel

Project Description

When considering simple random walks on a graph, it is known that the expected hitting time has the upper bound of approximately O(n^3). However, the random walker may use some heuristics or biases to try to get to the target vertex quicker.
One of such biases is 'geodesic bias' - some vertices in the graph are 'excited' and from them, the random walker takes a step along a fixed shortest path. The question is, do the upper bounds differ?

Note 1: For a nicely written O(n^3), see Petr's webpage.
Note 2: By initial hypothesis I mean the following. For any graph with any number of 'excited' vertices (towards a given 'goal'), the expected hitting time of the 'goal' (from any starting vertex) is O(n^3).


Weekly Log

Week 1:
I have read a short text concerning Markov chains. [1] We (Mikhail, Petr and myself, as well as several other students) met with Dr Narayanan who introduced several problems to us. After deciding on which project we would like to work on, we were given reading recommendations.[2][3] Also, we have prepared our first presentation (see below).
Week 2:
We read relevant chapters of [2] (mainly 1, 2, 10; but each one of us read even more). Together we went through [3], which included proving a lemma which was not proven in the paper. Petr came up with an example of a graph where exciting a vertex greatly changes the expected hitting time. Now we're trying to see if this example could be extended to a counterexample to the initial hypothesis. At the same time we're trying to see if ideas from [3] could be used (in an altered form) to prove the hypothesis. We are also thinking about a statement, possibly simple to prove (possibly false). If it is true, we would have a polynomial (but not cubic) upper bound on the expected hitting time.
Week 3:
We believe we have achieved a result concerning the initial hypothesis. We spent Tuesday writing down our ideas in a formal form and will present them to Dr Narayanan next week. From then on we were considering a problem related to our initial one, differing by a slight change in the statement. So far we've been mostly checking whether techniques from the second week could be used in this case.
Week 4:
We met with Dr Narayanan; he confirmed our belief from the last week and shared with us several ideas to consider further. During the next days, we were dealing with the problem mentioned in the last entry. Although we haven't managed to solve it fully yet, Mikhail proposed what seems to be a relevant partial result. While likely of a little importance to our problem, it might be worth mentioning that in this week's calculations, Fibonacci's sequence showed up at an unexpected place and we discovered and proved a property of the golden ratio which was new to us.
Week 5:
We had another meeting with Dr Narayanan which yielded a few new ideas. We then spent the whole week considering different variations of a specific graph, trying to compute (or at least estimate) its behaviour, using various techniques. So far the only results we have managed to obtain were of a rather trivial character.
Week 6:
Our Monday's meeting with Dr Narayanan gave us inspiration that we transformed into a hypothesis on Tuesday. Its validity would mean finally solving the problem from Week 3. On Thursday we presented our new ideas to Dr Narayanan and were suggested a possible proving strategy. We hope we managed to implement it, yet a thorough check is still in order.
Week 7:
This week was mostly about summarizing our results. We wrote down the first version of the proof mentioned in the last entry (so far it seems to work) as well as few paragraphs of a paper-like text. We prepared and presented our final presentation.
Week 8:
During our last week in the United States we attended a workshop, a tutorial and a conference organized by DIMACS. Apart from that we continued writing down our results.

Presentations

References


Additional Information