Initially, the integer $80$ is written on a blackboard. At each step, the integer $x$ on the blackboard is replaced with an integer chosen uniformly at random among [0,x−1], unless $x=0$ , in which case it is replaced by an integer chosen uniformly at random among [0,2024]. Let $P(a,b)$ be the probability that after $a$ steps, the integer on the board is $b$. Determine $$\lim_{x\to\infty}\frac{P(a,80)}{P(a,2024)}$$(that is, the value that the function $\frac{P(a,80)}{P(a,2024)}$ approaches as $a$ goes to infinity).
Problem
Source:
Tags: Comc
InftyByond
04.11.2024 19:41
AW HAIL NAAAAA its already on aops
Basically we assume that P(a-1, 80) is similar to P(a,80) and so on, then solving as a system of equations we get 25
Sagnik123Biswas
09.11.2024 23:04
Suppose that the probability distribution stabilizes over time (this is an assumption that is hard to prove and quite frankly not intuitive, but it should be true given that the answer exists). So then $p_{2024} = \frac{p_0}{2025}, p_{2023} = \frac{p_0}{2025} + \frac{p_{2024}}{2024}, p_{2022} = \frac{p_0}{2025} + \frac{p_{2024}}{2024} + \frac{p_{2023}}{2023} \dots$. If you solve the equations, you will notice the pattern $p_{2024-i} = \frac{p_0}{i+1}$. So our answer is $\frac{\frac{1}{81}}{\frac{1}{2025}} = 25$