Randomized Algorithms and Probabilistic Analysis of Algorithms - Exercise Sheet 4/5 - Winter 2022/23

Sep 14, 2026

Randomized Algorithms and Probabilistic Analysis of Algorithms, Exercise Sheet 4/5 for Winter 2022/23, provides problems on randomized approximation, gambling-style random walks, and Markov chain theory. It covers randomized geometric sampling for approximation guarantees, hitting/ruin probabilities in a fair ±1 euro game, and stationary distributions via detailed balance and time reversal. Additional tasks apply reverse-sequence Markov reasoning and develop probabilistic method techniques, including coloring arguments and intermediate “sample and modify” constructions.

LanguageEnglish

CategoryExam

FormatPDF

Pages3

Reading Time8 min

AccessFree to download

Randomized Algorithms and Probabilistic Analysis of Algorithms

Exercise Sheet 4/5

Approximation by random sampling

Gambling and ruin probabilities

Cover time of the complete graph

Stationary distributions and time reversibility

Time-reversal of Markov chains

Probabilistic method techniques

Philip Wellnitz, Barış Can Esmer Winter 2022/23 Randomized Algorithms and Probabilistic Analysis of Algorithms, Exercise Sheet 4/5 [https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/winter22/random](https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/winter22/random) Total Points: 100 + 100 Due: Wednesday, January 11, 2023 You are allowed to collaborate on the exercise sheets. Justify your answers . Cite all external sources that you use (books, websites, research papers, etc.) . You need to collect at least 50% of all points on exercise sheets to be admitted to the exam. Please hand in your solutions before the lecture on the day of the deadline. | .1 points For 0 < "; 􀀎 < 1, demonstrate a randomized algorithm that gives an ("; 􀀎)-approximation of 􀀙 .
(Hint: Sample a random point from the square (􀀀1; 􀀀1)(1 ; 􀀀1)(1 ; 1)(􀀀1; 1) and consider the event that said sample lies inside of the unit circle.)
Exercise 4 2 10 + 20 | | | | --- | --- | --- | | . points
Your favorite game center offers a new game where in each round, you can equally likely win 1€ or loose 1€ . You start with an initial budget of 200€ and you may play as long as your balance is positive (that is, you can play as long as you are not bankrupt) .
a) What is the probability that you win 200€ before going bankrupt?
b) For positive ` 1 ; `2 , what is the probability that you own 200€ + `1 € before you own 200€ 􀀀 `2 €?
Exercise 4 3 10 | | | | Show that the
Exercise | .
cover time of the complete graph on n vertices is 􀀂(n lnn) .
4 4 | points
10 | | . points
Consider a finite, irreducible, and aperiodic Markov chain with transition matrix P. Show that if there are nonnegative numbers = (􀀙1 ; : : : ; 􀀙n) that sum to 1 and satisfy for any i; j
􀀙iPi;j = 􀀙jPj;i ; (1)
then is the stationary distribution corresponding to P.
Note: A Markov chain that satisfies (1) is also called time-reversible.
Exercise 4 5 10 + 15 + 5 | | | Exercise 4 20 . points Consider a finite Markov chain with n states, transition matrix P, and stationary distribution . Imagine running the chain for r steps, yielding the sequence X0 ; X1 ; : : : ; Xr and consider the reverse sequence Xr ; : : : ; X0 . a) Argue that the reverse sequence is Markovian. b) Argue that for the reverse sequence, the transition probabilities Qi;j are given by 􀀙jPj;i Qi;j = : 􀀙i c) Argue that for a time-reversible Markov chain, we have Pi;j = Qi;j for all states i; j. In this exercise sheet, we develop several techniques to prove the existence of objects. Collectively, these methods are also called the probabilistic method. ~~ ~~Exercise~~ ~~5.1~~ ~~5~~ ~~+~~ ~~5~~ ~~+~~ ~~5~~ ~~+~~ ~~5~~ ~~points~~ ~~ In this exercise, we show that for integers n and k that satisfy 􀀀 nk􀀁2􀀀􀀀k2􀀁+1 < 1, we can color the edges of the complete graph Kn with two colors such that no complete subgraph Kk is monochromatic. a) Define a sample space 􀀊 of all valid colorings of Kn with two colors. What is the size of said sample space? b) Compute the probability that in a coloring sampled uniformly from 􀀊, a specific k-clique Kk is monochromatic. (Hint: Think of uniformly sampling a coloring from 􀀊 as assigning each edge one of the two colors uniformly at random.) c) Assuming 􀀀 nk􀀁2􀀀􀀀k2􀀁+1 < 1, conclude that the probability that all k-cliques in Kn are monochromatic is less than 1 . Further conclude that hence, there is a coloring of Kn that ensures that no k-clique subgraph is monochromatic. d) Discuss how to (efficiently) construct such a coloring of Kn. ~~ ~~Exercise~~ ~~5.2~~ ~~10~~ ~~+~~ ~~10~~ ~~points~~ ~~In this exercise, we see an averaging argument that is sometimes easier to apply. a) Prove that for a probability space S and a random variable X defined on S with E [ X ] = 􀀖, we have Pr [ X 􀀕 􀀖 ] > 0 and Pr [ X 􀀔 􀀖 ] > 0. b) Prove that in any undirected graph G = (V; E) with m edge

FAQs

What topics are covered in Exercise Sheet 4/5?

The sheet covers randomized approximation via sampling, gambling/ruin probabilities, cover time bounds for complete graphs, and Markov chain results including stationary distributions and time reversal. It also introduces probabilistic method techniques such as averaging and sample-and-modify.

How does the sheet approach randomized approximation in the first exercise?

It samples a random point from a specified square region and uses the probability that the sample lies inside the unit circle to derive the required approximation guarantee.

What does the sheet require to use probabilistic method arguments?

It asks to justify answers and to apply probabilistic reasoning such as bounding event probabilities (e.g., clique colorings), using averaging/expectations, and sometimes constructing an intermediate random structure before modifying it to achieve the desired properties.

Sep 14, 2026

Upload by Evangeline