1（a）现在，让我们删除每个元素都是唯一的假设。尤其是，yi≤yi + 1≤···≤yj−1≤yj是我们所知道的。为什么上面的推理不再起作用？ （提示：提供一个示例，在这种宽松的假设下，我们得出的概率不再正确）

1（b）表明我们陈述随机快速排序算法的方式略有变化，或者分析中的略有变化，因此我们仍然可以得出结论，Pr（yi和yj进行了比较）仍精确地为2。

03/101/103 /5Q =1/ 10 1/10 7/10 1 /10，

1/ 10 7/10 1/10 1 /109/ 10 1/10 0 0

3（b）如果链从状态1开始，则求出经过32步后处于状态3的概率。

3（c）如果链开始于从四个状态中随机随机选择的状态，则求出128步后处于状态3的概率。

3（d）计算马尔可夫链的平稳分布π。

3（e）令π为平稳分布。假设过程在状态1开始。t的最小值是什么| maxi | Qt1，i-πi| ≤0.01？最小的是什么，t的最小值是最大| Qt1，i-πi| ≤0.001？

5（a）假设猫从顶点u开始，鼠标从顶点v开始。显示（证明）从u到v的长度最大为2n。

5（b）在鼠标停留之前的预期时间内显示O（m2n）的上限。仔细调整答案。

6（a）编写一个函数random_walk_trials（n，t），该函数模拟您的室友在n分钟后行走的路径，并进行t次模拟试验，并报告室友在最后一分钟返回家园的次数。注意：n和t均为正数。该功能应报告在t试验结束后模拟步行返回家园的次数。还要注意，“返回家园”仅在他们在时间n返回家园时报告，而忽略他们是否早点返回并再次离开，直到在其他地方结束。

There are 6 problems worth 80 points total. This assignment covers a few of the aspects of the random- ized algorithms and probabilistic method before diving into Markov chains, with a particular focus on the probability distribution as well as sampling. For your submission, please attach all of your files to a single submission on UB Learns. If you require a zip file, please submit your PDF, your main code file, and then your zip file as separate attachments (double-check your submission on UB Learns after you submit).

Randomized Algorithms

Problem 1. (4 points each) In the runtime analysis of the Random Quicksort algorithm in lecture (textbook section 2.5, p 37), we assumed, for simplicity, that each of the elements in the input were unique. That is, yi < yi+1 < ··· < yj1 < yj. From that, we concluded that yi is chosen as a pivot before any other in the setYij ={yi,yi+1,…,yj1,yj}withprobability1/|Yij|=1/(ji+1).Similarly,theprobabilitythat yj is chosen as a pivot before any other element in Y ij is also 1/(j i + 1).

1(a) Now, let’s remove the assumption that every element is unique. In particular, yi yi+1 ≤ · · · ≤ yj1 yj is all we know. Why does the reasoning above not work anymore? (Hint: provide an example where the probability we derived is no longer correct with this relaxed assumption)

1(b) Indicate a slight change in the way we stated the Random Quicksort algorithm, or a slight change in the analysis, so that we can still conclude that Pr(yi and yj were compared) is still exactly 2 .

Probabilistic Method

Problem 2. (6 points) A hypergraph H is a pair of sets (V, E), where V is the set of vertices and E is the set of hyperedges. Every hyperedge in E is a subset of V . An r-uniform hypergraph is one where the size of each edge is r vertices. For example, a 2-uniform hypergraph is just a standard graph.

Suppose n 2 and let H = (V, E) be an n-uniform hypergraph. Show that if |E| < 4n1, then there exists a coloring of vertices in V with 4 colors such that no edge e E is monochromatic. (Note that each “edge” e E is a subset of size n of V, so an edge is monochromatic if all vertices are colored the same color.)

Markov Chains
Problem 3. (4 points each) [modified from p198 ex 7.1] Consider a Markov chain with state space {1, 2, 3, 4}

and the transition matrix

0 3/101/103/5Q = 1/10 1/10 7/10 1/10,

1/10 7/10 1/10 1/109/10 1/10 0 0

so Q1,4 = 3/5 is the probability if moving from state 1 to state 4. 3(a) Draw the Markov chain for this process.

3(b) Find the probability of being in state 3 after 32 steps if the chain begins at state 1.

3(c) Find the probability of being in state 3 after 128 steps if the chain begins at a state chosen uniformly at random from the four states.

1. 3(d)  Compute the stationary distribution π of the Markov chain.
2. 3(e)  Let π be the stationary distribution. Suppose that the process begins in state 1. What is the smallest value of t for which maxi |Qt1,i πi| ≤ 0.01? What is the smallest What is the smallest value of t for which maxi |Qt1,i πi| ≤ 0.001?

Problem 4. (6 points) [p200 ex 7.14] Prove that the Markov chain corresponding to a random walk on an undirected, non-bipartite, connected graph is time reversible.

Problem 5. (8 points each) A cat and mouse each independently take a random walk on an undirected, connected, non-bipartite graph G = (V, E) with n vertices and m edges. They start at the same time on different nodes, and each makes one transition per time step. The cat eats the mouse if they are every at the same node at some time step.

1. 5(a)  Suppose that the cat starts at vertex u and the mouse starts at vertex v. Show (prove) that there is an even-length walk from u to v of length at most 2n.

Problem 6. (6 points each) Your housemate has just consumed the food you meal preped for the entire week. To avoid a food coma, they decide to go for a walk as follows:

• they walk 1 block per minute,
• they cannot think straight so they walk in an arbitrary direction north, south, east, or west, with equal probability, and
• they never stay stationary.
Given this scenario, complete the following:

6(a) Write a function random_walk_trials(n,t) that simulates the path your housemate walks after n minutes and performs t trials of the simulation and reports how many times your housemate returns home in the last minute. Note: n and t are both positive numbers. The function should report the number of times the simulated walk returns home at the end out of the t trials. Also note that returning home only reports if they return home at time n and ignores if they returned sooner and left again, ending elsewhere. EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue

EasyDue™是一个服务全球中国留学生的专业代写公司