本次美国统计代写主要是关于随机过程里面的markov算法
有6个问题，总分80分。该作业涵盖了进入马尔可夫链之前的随机算法和概率方法的一些方面，尤其侧重于概率分布和采样。对于您的提交，请将所有文件附加到UB Learns的单个提交中。如果需要zip文件，请先提交PDF，主代码文件，然后再将zip文件作为单独的附件提交（提交后在UB Learns上仔细检查提交）。
随机算法
问题1.（每个点4分）在讲座（教科书第2.5节，第37页）中对Random Quicksort算法的运行时分析中，为简单起见，我们假定输入中的每个元素都是唯一的。即，yi <yi + 1 <···<yj-1 <yj。据此，我们得出结论，在集合中的ij = {yi，yi + 1，…，yj-1，yj}且概率为1 || Yij | = 1 /（（j−i + 1）类似地，在y ij中的任何其他元素之前选择yj作为枢轴的概率也是1 /（j − i + 1）。
1（a）现在，让我们删除每个元素都是唯一的假设。尤其是，yi≤yi + 1≤···≤yj−1≤yj是我们所知道的。为什么上面的推理不再起作用？ （提示：提供一个示例，在这种宽松的假设下，我们得出的概率不再正确）
1（b）表明我们陈述随机快速排序算法的方式略有变化，或者分析中的略有变化，因此我们仍然可以得出结论，Pr（yi和yj进行了比较）仍精确地为2。
概率法
问题2（6分）超图H是一对集合（V，E），其中V是顶点集合，E是超边集合。 E中的每个超边都是V的子集。 r统一超图是每个边的大小为r个顶点的超图。例如，2均匀超图只是一个标准图。
假设n≥2，并且令H =（V，E）为n一致超图。显示| E | <4n-1，则V中存在4种颜色的顶点着色，使得没有边e∈E是单色的。 （请注意，每个“边” e∈E是V的大小n的子集，因此，如果所有顶点的颜色相同，则边是单色的。）
马尔可夫链
问题3（各4点）[从p198 ex 7.1修改]考虑状态空间为{1、2、3、4}的马尔可夫链
和过渡矩阵
03/101/103 /5Q =1/ 10 1/10 7/10 1 /10，
1/ 10 7/10 1/10 1 /109/ 10 1/10 0 0
因此Q1,4 = 3/5是从状态1转移到状态4的概率。3（a）为此过程画出马尔可夫链。
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？
问题4（6分）[p200 ex 7.14]证明了与无向，无二分连通图上的随机游走相对应的马尔可夫链是时间可逆的。
问题5（每点8点）猫和老鼠分别在具有n个顶点和m个边的无向，连通，非二等图G =（V，E）上分别随机行走。它们在不同的节点上同时开始，每个节点每个时间步进行一次转换。如果它们在某个时间点处在同一节点上，则猫会吞食鼠标。
5（a）假设猫从顶点u开始，鼠标从顶点v开始。显示（证明）从u到v的长度最大为2n。
5（b）在鼠标停留之前的预期时间内显示O（m2n）的上限。仔细调整答案。
问题6（每人6分）您的室友刚吃完您整周准备的饭菜。为了避免食物昏迷，他们决定按照以下步骤散步：
他们每分钟走一格，
他们无法直视，所以他们以相同的概率朝北，南，东或西的任意方向行走，并且
他们永远不会静止不动。
在这种情况下，请完成以下操作：
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 < ··· < yj−1 < yj. From that, we concluded that yi is chosen as a pivot before any other in the setYij ={yi,yi+1,…,yj−1,yj}withprobability1/|Yij|=1/(j−i+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 ≤ · · · ≤ yj−1 ≤ 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| < 4n−1, 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/5 Q = 1/10 1/10 7/10 1/10 ,
1/10 7/10 1/10 1/10 9/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.
- 3(d) Compute the stationary distribution π of the Markov chain.
- 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.
- 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.
- 5(b) ShowanupperboundofO(m2n)ontheexpectedtimebeforethecateatsthemouse.Carefullyjustify your answer.
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.