191014K02 | Day 5 Tutorial

191014K02: Day 5 Tutorial

Start the local search algorithm discussed in class and suppose that initially \(d(\gamma, \beta) \leqslant d\). Consider a random walk from \(d\) with down-probability \(1/k\). Show that \(\forall s \geqslant 0\) and \(j \geqslant 0\): \[ \operatorname{Pr}[{\color{indianred}d(\gamma, \beta) \leqslant j \text { in step } s}] \geqslant \operatorname{Pr}\left[P_s \leqslant j\right]. \]
We saw in class that the probability that the walk eventually visits \(0\) is \(q_d=\left(\frac{1}{k-1}\right)^d\). We want to now show that the probability that this happens in “not too many” i.e, \((O(d))\) steps, is \(\geqslant q_d/2\). To this end:
1. Show that starting at position \(d+3\) the probability of reaching \(0\) is \(\leqslant q_d/8\).
2. Show that \(\forall k\), \(\exists c\) such that \(\forall d\)¹, after \(cd\) steps, the probability of being at position \(\leqslant d+3\) is \(\leqslant q_d/8\).
3. Show that the probability of reaching \(0\) from \(d\) after at least \(cd\) steps is at most \(q_d/2\).
4. Show that the probability of reaching \(0\) from \(d\) after at most \(cd\) steps is at least \(q_d/2\).
Show that a tournament has a directed cycle if and only if it has a directed triangle.
Demonstrate a \(3\)-approximation algorithm for the Tournament Feedback Vertex Set problem.