Let \(X_0=n\). If the current state is \(k\), we perform \(k\) independent uniform draws from \(n\) labels, and the next state \(X_{r+1}\) is the number of distinct labels that appear in those \(k\) draws. Because every round satisfies \(1 \le X_{r+1} \le k\), the process eventually reaches the absorbing state \(1\). The task is to compute the expected number of rounds needed to go from \(n\) to \(1\), for the case \(n=1000\), and report the result to six decimal places.
The key observation is that the process is a finite Markov chain whose transition law depends only on an occupancy count: from state \(k\), the next state is the number of occupied labels after \(k\) draws into \(n\) equally likely labels.
Let \(t_k\) denote the expected number of additional rounds needed to reach state \(1\) when the current state is \(k\). Then
$$t_1=0.$$
To determine \(t_k\), we need the transition probabilities
$$q_k(j)=\Pr(X_{r+1}=j\mid X_r=k),\qquad 1\le j\le k.$$
So the combinatorial core of the problem is: after \(k\) independent draws from \(n\) equally likely labels, what is the probability that exactly \(j\) distinct labels appear?
Start with zero draws. Then only zero labels can be occupied:
$$q_0(0)=1.$$
Now append one more draw. To end with exactly \(j\) distinct labels after \(k+1\) draws, there are two mutually exclusive possibilities:
the first \(k\) draws already used exactly \(j\) labels and the new draw hits one of those \(j\) labels, or the first \(k\) draws used exactly \(j-1\) labels and the new draw hits a brand-new label.
This gives the recurrence
$$q_{k+1}(j)=q_k(j)\frac{j}{n}+q_k(j-1)\frac{n-j+1}{n}.$$
This is exactly the triangular probability table computed by the implementations. An equivalent closed form is
$$q_k(j)=\frac{n(n-1)\cdots(n-j+1)}{n^k}\,S(k,j),$$
where \(S(k,j)\) is a Stirling number of the second kind, but the recurrence is the most direct way to evaluate all needed probabilities numerically.
From state \(k\), one round is spent immediately, and then the chain moves to state \(j\) with probability \(q_k(j)\). Therefore
$$t_k=1+\sum_{j=1}^{k} q_k(j)\,t_j.$$
At first glance this looks circular, because \(t_k\) appears on both sides. That is not a problem: the only unknown on the right that is not already a smaller-state value is the self-loop term corresponding to \(j=k\).
Move the \(j=k\) term to the left:
$$\left(1-q_k(k)\right)t_k=1+\sum_{j=1}^{k-1} q_k(j)\,t_j.$$
Hence
$$t_k=\frac{1+\sum_{j=1}^{k-1} q_k(j)\,t_j}{1-q_k(k)}.$$
The denominator is positive for every \(k\ge 2\), because \(q_k(k)\) is only the probability that all \(k\) draws are distinct:
$$q_k(k)=\frac{n(n-1)\cdots(n-k+1)}{n^k}\lt 1.$$
So once the probabilities are known, the expectations can be computed in increasing order \(t_2,t_3,\dots,t_n\). That is why the system is triangular rather than requiring a full linear solver.
For state \(2\), two draws from three labels produce either one distinct label or two distinct labels:
$$q_2(1)=\frac{1}{3},\qquad q_2(2)=\frac{2}{3}.$$
Therefore
$$t_2=1+\frac{1}{3}t_1+\frac{2}{3}t_2=1+\frac{2}{3}t_2,$$
so
$$t_2=3.$$
For state \(3\), three draws from three labels give
$$q_3(1)=\frac{1}{9},\qquad q_3(2)=\frac{2}{3},\qquad q_3(3)=\frac{2}{9}.$$
Then
$$t_3=1+\frac{1}{9}t_1+\frac{2}{3}t_2+\frac{2}{9}t_3.$$
Substituting \(t_1=0\) and \(t_2=3\) gives
$$t_3=1+0+2+\frac{2}{9}t_3,$$
hence
$$\frac{7}{9}t_3=3,\qquad t_3=\frac{27}{7}.$$
This is the small exact checkpoint used to verify the recurrence.
The required answer is \(t_n\) with \(n=1000\). No random simulation is needed. Once the occupancy table \(q_k(j)\) has been filled, the expected number of rounds follows deterministically from the formula above.
The C++, Python, and Java implementations follow the same two-stage plan. First, they build a \((n+1)\times(n+1)\) probability table row by row. Each row corresponds to a draw count \(k\), and each entry stores the probability of seeing a specific number of distinct labels. Only the triangular region \(0\le j\le k\le n\) is relevant, so each new row is formed from the previous one using the occupancy recurrence.
After the transition table is ready, the implementation stores the expected remaining rounds for each state. It sets the absorbing value \(t_1=0\), then computes \(t_2,t_3,\dots,t_n\) in increasing order by applying the self-loop formula. Because every new state depends only on smaller states and on the already known diagonal probability \(q_k(k)\), no iterative approximation is required. The final printed value is the expectation for \(n=1000\), formatted to six digits after the decimal point.
Building the occupancy table requires
$$\sum_{k=0}^{n-1}(k+1)=O(n^2)$$
updates. Solving the expectation equations requires
$$\sum_{k=2}^{n}(k-1)=O(n^2)$$
more arithmetic operations. Therefore the overall running time is \(O(n^2)\). The implementations keep the full triangular probability table in memory, so the space usage is \(O(n^2)\), while the expectation array itself contributes only \(O(n)\).
Setze \(X_0=n\). Befindet sich der Prozess im Zustand \(k\), dann werden \(k\) unabhängige gleichverteilte Ziehungen aus \(n\) Marken ausgeführt, und der nächste Zustand \(X_{r+1}\) ist die Anzahl verschiedener Marken, die in diesen \(k\) Ziehungen erscheinen. Da in jeder Runde \(1 \le X_{r+1} \le k\) gilt, endet der Prozess schließlich im absorbierenden Zustand \(1\). Gesucht ist der Erwartungswert der benötigten Rundenzahl, um von \(n\) nach \(1\) zu gelangen, im eigentlichen Problem für \(n=1000\), ausgegeben mit sechs Nachkommastellen.
Der Kern der Aufgabe ist eine endliche Markov-Kette: Aus Zustand \(k\) springt man in die Anzahl besetzter Marken, die nach \(k\) Ziehungen in \(n\) gleichwahrscheinliche Klassen fallen.
Sei \(t_k\) die erwartete Anzahl zusätzlicher Runden bis zum Erreichen von Zustand \(1\), wenn der aktuelle Zustand \(k\) ist. Dann gilt
$$t_1=0.$$
Außerdem benötigen wir die Übergangswahrscheinlichkeiten
$$q_k(j)=\Pr(X_{r+1}=j\mid X_r=k),\qquad 1\le j\le k.$$
Damit reduziert sich die kombinatorische Frage auf folgendes Belegungsproblem: Nach \(k\) unabhängigen Ziehungen aus \(n\) gleichwahrscheinlichen Marken, mit welcher Wahrscheinlichkeit sieht man genau \(j\) verschiedene Marken?
Bei null Ziehungen ist nur null besetzt:
$$q_0(0)=1.$$
Füge nun eine weitere Ziehung hinzu. Um nach \(k+1\) Ziehungen genau \(j\) verschiedene Marken zu haben, gibt es zwei disjunkte Fälle:
Entweder hatten die ersten \(k\) Ziehungen bereits genau \(j\) verschiedene Marken und die neue Ziehung trifft eine davon, oder die ersten \(k\) Ziehungen hatten genau \(j-1\) verschiedene Marken und die neue Ziehung trifft eine neue Marke.
Daraus folgt die Rekurrenz
$$q_{k+1}(j)=q_k(j)\frac{j}{n}+q_k(j-1)\frac{n-j+1}{n}.$$
Genau so entsteht die dreieckige Wahrscheinlichkeitstabelle in den Implementierungen. Eine äquivalente geschlossene Formel lautet
$$q_k(j)=\frac{n(n-1)\cdots(n-j+1)}{n^k}\,S(k,j),$$
wobei \(S(k,j)\) eine Stirling-Zahl zweiter Art ist. Für die direkte Berechnung aller benötigten Werte ist die Rekurrenz jedoch der praktischste Weg.
Aus Zustand \(k\) wird sofort eine Runde verbraucht, danach geht die Kette mit Wahrscheinlichkeit \(q_k(j)\) in Zustand \(j\) über. Also gilt
$$t_k=1+\sum_{j=1}^{k} q_k(j)\,t_j.$$
Das sieht zunächst zirkulär aus, weil \(t_k\) auf beiden Seiten vorkommt. Tatsächlich ist nur der Selbstschleifen-Term mit \(j=k\) problematisch; alle anderen Beiträge betreffen bereits kleinere Zustände.
Bringt man den Term \(j=k\) auf die linke Seite, erhält man
$$\left(1-q_k(k)\right)t_k=1+\sum_{j=1}^{k-1} q_k(j)\,t_j.$$
also
$$t_k=\frac{1+\sum_{j=1}^{k-1} q_k(j)\,t_j}{1-q_k(k)}.$$
Der Nenner ist für jedes \(k\ge 2\) positiv, denn \(q_k(k)\) ist nur die Wahrscheinlichkeit, dass alle \(k\) Ziehungen verschieden sind:
$$q_k(k)=\frac{n(n-1)\cdots(n-k+1)}{n^k}\lt 1.$$
Deshalb kann man die Werte der Reihe nach als \(t_2,t_3,\dots,t_n\) berechnen. Man braucht also keinen allgemeinen linearen Gleichungslöser, sondern nur diese dreieckige Auswertung.
Im Zustand \(2\) liefern zwei Ziehungen aus drei Marken entweder eine einzige verschiedene Marke oder zwei verschiedene Marken:
$$q_2(1)=\frac{1}{3},\qquad q_2(2)=\frac{2}{3}.$$
Daher
$$t_2=1+\frac{1}{3}t_1+\frac{2}{3}t_2=1+\frac{2}{3}t_2,$$
und damit
$$t_2=3.$$
Im Zustand \(3\) gilt
$$q_3(1)=\frac{1}{9},\qquad q_3(2)=\frac{2}{3},\qquad q_3(3)=\frac{2}{9}.$$
Also
$$t_3=1+\frac{1}{9}t_1+\frac{2}{3}t_2+\frac{2}{9}t_3.$$
Mit \(t_1=0\) und \(t_2=3\) folgt
$$t_3=1+0+2+\frac{2}{9}t_3,$$
somit
$$\frac{7}{9}t_3=3,\qquad t_3=\frac{27}{7}.$$
Genau dieser kleine exakte Wert dient als Plausibilitätskontrolle der Rekurrenz.
Gesucht ist \(t_n\) für \(n=1000\). Es wird nichts simuliert. Sobald die Belegungstabelle \(q_k(j)\) feststeht, ergibt sich der Erwartungswert deterministisch aus der obigen Formel.
Die C++-, Python- und Java-Implementierungen verwenden denselben zweistufigen Plan. Zuerst wird eine \((n+1)\times(n+1)\)-Tabelle von Übergangswahrscheinlichkeiten zeilenweise aufgebaut. Jede Zeile gehört zu einer Ziehungszahl \(k\), und jeder Eintrag speichert die Wahrscheinlichkeit für eine bestimmte Zahl verschiedener Marken. Relevant ist nur der dreieckige Bereich \(0\le j\le k\le n\), daher entsteht jede neue Zeile direkt aus der vorherigen über die Belegungsrekurrenz.
Danach speichert die Implementierung die erwarteten Rest-Runden für jeden Zustand. Mit dem absorbierenden Startwert \(t_1=0\) werden dann \(t_2,t_3,\dots,t_n\) aufsteigend berechnet. Jeder neue Wert verwendet nur bereits bekannte kleinere Zustände und die Diagonalwahrscheinlichkeit \(q_k(k)\), sodass keine iterative Näherung nötig ist. Am Ende wird der Wert für \(n=1000\) mit sechs Nachkommastellen ausgegeben.
Der Aufbau der Belegungstabelle benötigt
$$\sum_{k=0}^{n-1}(k+1)=O(n^2)$$
Aktualisierungen. Die Auswertung der Erwartungsgleichungen benötigt
$$\sum_{k=2}^{n}(k-1)=O(n^2)$$
weitere Rechenoperationen. Insgesamt beträgt die Laufzeit also \(O(n^2)\). Die Implementierungen halten die vollständige dreieckige Wahrscheinlichkeitstabelle im Speicher; daher ist der Speicherbedarf \(O(n^2)\), während das Feld der Erwartungswerte nur \(O(n)\) zusätzlich benötigt.
\(X_0=n\) ile başlayalım. Süreç \(k\) durumundayken, \(n\) etiket arasından bağımsız ve eş olasılıklı olarak \(k\) çekiliş yapılır; sonraki durum \(X_{r+1}\), bu \(k\) çekilişte görülen farklı etiket sayısıdır. Her turda \(1 \le X_{r+1} \le k\) olduğu için süreç sonunda soğurucu durum olan \(1\)'e ulaşır. Amaç, \(n\)'den başlayıp \(1\)'e inmek için gereken beklenen tur sayısını hesaplamaktır; problemde istenen büyük örnek \(n=1000\)'dir ve sonuç altı ondalık basamakla yazdırılır.
Asıl fikir, süreci sonlu bir Markov zinciri olarak görmek ve geçiş olasılıklarını bir doluluk sayımı problemiyle ifade etmektir: durum \(k\) iken bir sonraki durum, \(n\) eş olasılıklı etiket içine yapılan \(k\) çekilişten sonra kaç etiketin dolu kaldığıdır.
Mevcut durum \(k\) iken durum \(1\)'e ulaşmak için gereken ek tur sayısının beklentisine \(t_k\) diyelim. O halde
$$t_1=0.$$
Ayrıca şu geçiş olasılıklarına ihtiyacımız vardır:
$$q_k(j)=\Pr(X_{r+1}=j\mid X_r=k),\qquad 1\le j\le k.$$
Dolayısıyla kombinatorik çekirdek şu sorudur: \(n\) eş olasılıklı etiketten yapılan \(k\) bağımsız çekiliş sonunda tam olarak \(j\) farklı etiket görülme olasılığı nedir?
Sıfır çekilişte yalnızca sıfır etiket doludur:
$$q_0(0)=1.$$
Şimdi bir çekiliş daha ekleyelim. \(k+1\) çekiliş sonunda tam olarak \(j\) farklı etiket görülmesi için iki ayrık olasılık vardır:
İlk \(k\) çekilişte zaten \(j\) farklı etiket görülmüştür ve yeni çekiliş bunlardan birine gelmiştir; ya da ilk \(k\) çekilişte \(j-1\) farklı etiket görülmüştür ve yeni çekiliş daha önce gelmeyen yeni bir etikete düşmüştür.
Böylece
$$q_{k+1}(j)=q_k(j)\frac{j}{n}+q_k(j-1)\frac{n-j+1}{n}.$$
Uygulamaların satır satır oluşturduğu üçgensel olasılık tablosu tam olarak budur. Eşdeğer kapalı biçim
$$q_k(j)=\frac{n(n-1)\cdots(n-j+1)}{n^k}\,S(k,j)$$
şeklindedir; burada \(S(k,j)\) ikinci tür Stirling sayısıdır. Ancak gerekli tüm değerleri doğrudan hesaplamak için en pratik yol bu yinelemedir.
Durum \(k\)'dan başlarken bir tur hemen harcanır, sonra zincir \(q_k(j)\) olasılığıyla durum \(j\)'ye gider. Bu yüzden
$$t_k=1+\sum_{j=1}^{k} q_k(j)\,t_j.$$
İlk bakışta bu denklem döngüsel görünür, çünkü \(t_k\) iki tarafta da vardır. Fakat sağ taraftaki tek gerçek sorun, \(j=k\) olan öz-döngü terimidir; diğer bütün terimler daha küçük durumlara aittir.
\(j=k\) terimini sola taşıyalım:
$$\left(1-q_k(k)\right)t_k=1+\sum_{j=1}^{k-1} q_k(j)\,t_j.$$
Buradan
$$t_k=\frac{1+\sum_{j=1}^{k-1} q_k(j)\,t_j}{1-q_k(k)}$$
elde edilir. Her \(k\ge 2\) için payda pozitiftir; çünkü \(q_k(k)\) yalnızca tüm \(k\) çekilişin birbirinden farklı gelme olasılığıdır:
$$q_k(k)=\frac{n(n-1)\cdots(n-k+1)}{n^k}\lt 1.$$
Böylece olasılık tablosu bilindiğinde \(t_2,t_3,\dots,t_n\) sırasıyla hesaplanabilir. Genel amaçlı bir lineer denklem çözücüsüne ihtiyaç yoktur.
Durum \(2\) için, üç etiketten yapılan iki çekiliş ya tek bir farklı etiket ya da iki farklı etiket üretir:
$$q_2(1)=\frac{1}{3},\qquad q_2(2)=\frac{2}{3}.$$
Dolayısıyla
$$t_2=1+\frac{1}{3}t_1+\frac{2}{3}t_2=1+\frac{2}{3}t_2,$$
ve buradan
$$t_2=3$$
çıkar. Durum \(3\) için ise
$$q_3(1)=\frac{1}{9},\qquad q_3(2)=\frac{2}{3},\qquad q_3(3)=\frac{2}{9}.$$
Bu kez
$$t_3=1+\frac{1}{9}t_1+\frac{2}{3}t_2+\frac{2}{9}t_3.$$
\(t_1=0\) ve \(t_2=3\) yazarsak
$$t_3=1+0+2+\frac{2}{9}t_3,$$
dolayısıyla
$$\frac{7}{9}t_3=3,\qquad t_3=\frac{27}{7}.$$
Bu küçük tam değer, yinelemenin doğru kurulduğunu kontrol etmek için kullanılır.
Aranan cevap, \(n=1000\) için \(t_n\)'dir. Hiçbir Monte Carlo simülasyonu yapılmaz. Doluluk olasılıkları tablosu kurulduktan sonra beklenen tur sayısı yukarıdaki formülle tamamen deterministik olarak bulunur.
C++, Python ve Java uygulamaları aynı iki aşamalı planı izler. Önce \((n+1)\times(n+1)\) boyutlu bir geçiş olasılık tablosu satır satır doldurulur. Her satır belirli bir çekiliş sayısını temsil eder ve her hücre tam olarak belli sayıda farklı etiket görülme olasılığını saklar. Yalnızca \(0\le j\le k\le n\) üçgensel bölgesi anlamlı olduğu için her yeni satır, bir önceki satırdan doluluk yinelemesiyle üretilir.
Daha sonra uygulama, her durum için kalan beklenen tur sayısını tutar. Soğurucu değer \(t_1=0\) atanır ve ardından \(t_2,t_3,\dots,t_n\) artan sırayla hesaplanır. Her yeni değer yalnızca daha küçük ve önceden çözülmüş durumları ve aynı satırdaki köşegen olasılığı kullanır; bu yüzden yakınsak bir sayısal yöntem gerekmez. Son aşamada \(n=1000\) için bulunan beklenti altı ondalık basamakla yazdırılır.
Doluluk tablosunun kurulması
$$\sum_{k=0}^{n-1}(k+1)=O(n^2)$$
adet güncelleme gerektirir. Beklenti denklemlerinin çözümü de
$$\sum_{k=2}^{n}(k-1)=O(n^2)$$
adet ek aritmetik işlem yapar. Bu nedenle toplam zaman karmaşıklığı \(O(n^2)\)'dir. Uygulamalar tam üçgensel olasılık tablosunu bellekte tuttuğu için alan karmaşıklığı \(O(n^2)\), beklenti dizisinin ek maliyeti ise yalnızca \(O(n)\)'dir.
Sea \(X_0=n\). Si el estado actual es \(k\), se realizan \(k\) extracciones independientes y uniformes entre \(n\) etiquetas, y el siguiente estado \(X_{r+1}\) es el número de etiquetas distintas que aparecen en esas \(k\) extracciones. Como en cada ronda se cumple \(1 \le X_{r+1} \le k\), el proceso termina finalmente en el estado absorbente \(1\). La meta es calcular el número esperado de rondas necesarias para pasar de \(n\) a \(1\); en el problema real se toma \(n=1000\) y la salida se da con seis decimales.
La idea central es ver el proceso como una cadena de Markov finita. Desde el estado \(k\), la ley de transición es exactamente la distribución de ocupación obtenida al lanzar \(k\) bolas en \(n\) cajas equiprobables y contar cuántas cajas quedan ocupadas.
Sea \(t_k\) el número esperado de rondas adicionales para llegar al estado \(1\) cuando el estado actual es \(k\). Entonces
$$t_1=0.$$
También necesitamos las probabilidades de transición
$$q_k(j)=\Pr(X_{r+1}=j\mid X_r=k),\qquad 1\le j\le k.$$
Así, el núcleo combinatorio queda reducido a una pregunta clásica: después de \(k\) extracciones independientes entre \(n\) etiquetas equiprobables, ¿cuál es la probabilidad de observar exactamente \(j\) etiquetas distintas?
Con cero extracciones solo hay cero etiquetas ocupadas:
$$q_0(0)=1.$$
Ahora añadimos una extracción más. Para terminar con exactamente \(j\) etiquetas distintas después de \(k+1\) extracciones, hay dos posibilidades disjuntas:
las primeras \(k\) extracciones ya usaban exactamente \(j\) etiquetas y la nueva cae en una de esas \(j\), o las primeras \(k\) extracciones usaban exactamente \(j-1\) etiquetas y la nueva cae en una etiqueta nueva.
Por tanto,
$$q_{k+1}(j)=q_k(j)\frac{j}{n}+q_k(j-1)\frac{n-j+1}{n}.$$
Esa es exactamente la tabla triangular de probabilidades calculada por las implementaciones. Una forma cerrada equivalente es
$$q_k(j)=\frac{n(n-1)\cdots(n-j+1)}{n^k}\,S(k,j),$$
donde \(S(k,j)\) es un número de Stirling de segunda especie. Sin embargo, la recurrencia es la forma más directa de obtener todos los valores necesarios.
Desde el estado \(k\), se consume una ronda inmediatamente y luego la cadena pasa al estado \(j\) con probabilidad \(q_k(j)\). Por análisis del primer paso,
$$t_k=1+\sum_{j=1}^{k} q_k(j)\,t_j.$$
A primera vista parece una ecuación circular, porque \(t_k\) aparece en ambos lados. En realidad, el único término problemático es el bucle propio con \(j=k\); los demás ya dependen de estados más pequeños.
Llevando el término \(j=k\) al lado izquierdo se obtiene
$$\left(1-q_k(k)\right)t_k=1+\sum_{j=1}^{k-1} q_k(j)\,t_j,$$
y por tanto
$$t_k=\frac{1+\sum_{j=1}^{k-1} q_k(j)\,t_j}{1-q_k(k)}.$$
El denominador es positivo para todo \(k\ge 2\), porque \(q_k(k)\) no es más que la probabilidad de que las \(k\) extracciones sean todas distintas:
$$q_k(k)=\frac{n(n-1)\cdots(n-k+1)}{n^k}\lt 1.$$
Eso permite calcular \(t_2,t_3,\dots,t_n\) en orden creciente. No hace falta resolver un sistema lineal completo; basta con esta evaluación triangular.
En el estado \(2\), dos extracciones entre tres etiquetas producen una sola etiqueta distinta o dos etiquetas distintas:
$$q_2(1)=\frac{1}{3},\qquad q_2(2)=\frac{2}{3}.$$
Luego
$$t_2=1+\frac{1}{3}t_1+\frac{2}{3}t_2=1+\frac{2}{3}t_2,$$
de donde
$$t_2=3.$$
En el estado \(3\) se tiene
$$q_3(1)=\frac{1}{9},\qquad q_3(2)=\frac{2}{3},\qquad q_3(3)=\frac{2}{9}.$$
Así,
$$t_3=1+\frac{1}{9}t_1+\frac{2}{3}t_2+\frac{2}{9}t_3.$$
Sustituyendo \(t_1=0\) y \(t_2=3\), resulta
$$t_3=1+0+2+\frac{2}{9}t_3,$$
por lo tanto
$$\frac{7}{9}t_3=3,\qquad t_3=\frac{27}{7}.$$
Este valor exacto pequeño sirve como comprobación de que la recurrencia está bien planteada.
La respuesta pedida es \(t_n\) con \(n=1000\). No se recurre a simulación. Una vez completada la tabla de ocupación \(q_k(j)\), el número esperado de rondas se obtiene de forma completamente determinista.
Las implementaciones en C++, Python y Java siguen el mismo esquema de dos etapas. Primero construyen una tabla de probabilidades de tamaño \((n+1)\times(n+1)\) fila por fila. Cada fila corresponde a una cantidad de extracciones \(k\), y cada entrada almacena la probabilidad de observar un número concreto de etiquetas distintas. Solo importa la región triangular \(0\le j\le k\le n\), así que cada fila nueva se obtiene directamente de la anterior mediante la recurrencia de ocupación.
Después, la implementación almacena la esperanza de rondas restantes para cada estado. Fija el valor absorbente \(t_1=0\) y calcula \(t_2,t_3,\dots,t_n\) en orden creciente. Cada nuevo valor usa únicamente estados menores ya resueltos y la probabilidad diagonal \(q_k(k)\), de modo que no se necesita ningún método iterativo de aproximación. Al final se imprime la esperanza correspondiente a \(n=1000\) con seis cifras decimales.
La construcción de la tabla de ocupación requiere
$$\sum_{k=0}^{n-1}(k+1)=O(n^2)$$
actualizaciones. La resolución de las ecuaciones de esperanza requiere
$$\sum_{k=2}^{n}(k-1)=O(n^2)$$
operaciones adicionales. En consecuencia, el tiempo total es \(O(n^2)\). Las implementaciones conservan la tabla triangular completa de probabilidades, por lo que el uso de memoria es \(O(n^2)\); el arreglo de esperanzas agrega solo \(O(n)\).
设 \(X_0=n\)。如果当前状态是 \(k\)，就从 \(n\) 个标签中独立且等概率地抽取 \(k\) 次，并把这 \(k\) 次抽样中出现的不同标签个数定义为下一状态 \(X_{r+1}\)。由于每一轮都满足 \(1 \le X_{r+1} \le k\)，这个过程最终一定会到达吸收状态 \(1\)。题目要求计算从初始状态 \(n\) 出发、直到降到 \(1\) 所需轮数的期望值；在实际求解中取 \(n=1000\)，并把结果保留六位小数输出。
这道题的本质是一个有限状态 Markov 链。处在状态 \(k\) 时，下一步转移分布就是“向 \(n\) 个等概率盒子里投 \(k\) 个球后，恰好有多少个盒子非空”的占位分布。
记 \(t_k\) 为“当前状态为 \(k\) 时，到达状态 \(1\) 还需要多少轮”的期望值。那么
$$t_1=0.$$
我们还需要如下转移概率：
$$q_k(j)=\Pr(X_{r+1}=j\mid X_r=k),\qquad 1\le j\le k.$$
因此组合部分可以表述为：从 \(n\) 个等概率标签中独立抽取 \(k\) 次，恰好看到 \(j\) 个不同标签的概率是多少？
当抽样次数为零时，只可能看到零个标签：
$$q_0(0)=1.$$
现在在已有的 \(k\) 次抽样后再增加一次抽样。要在 \(k+1\) 次抽样后恰好看到 \(j\) 个不同标签，有两种互斥情况：
前 \(k\) 次已经恰好看到 \(j\) 个不同标签，而新的一次抽样落在这 \(j\) 个标签之一上；或者前 \(k\) 次恰好看到 \(j-1\) 个不同标签，而新的一次抽样第一次命中一个新标签。
于是得到递推式
$$q_{k+1}(j)=q_k(j)\frac{j}{n}+q_k(j-1)\frac{n-j+1}{n}.$$
这正是实现中逐行填充的三角概率表。它也有一个等价的闭式表达：
$$q_k(j)=\frac{n(n-1)\cdots(n-j+1)}{n^k}\,S(k,j),$$
其中 \(S(k,j)\) 是第二类 Stirling 数。不过在需要把所有相关概率都算出来时，直接使用上面的递推最自然也最稳定。
从状态 \(k\) 出发时，当前这一轮一定先消耗掉，然后链以概率 \(q_k(j)\) 转移到状态 \(j\)。因此有
$$t_k=1+\sum_{j=1}^{k} q_k(j)\,t_j.$$
表面上看这像一个循环定义，因为 \(t_k\) 同时出现在等式两边。实际上问题只来自 \(j=k\) 这一项，也就是“下一轮之后仍然停留在同一状态”的自环项；其余项都只依赖更小的状态。
把 \(j=k\) 对应的项移到左边：
$$\left(1-q_k(k)\right)t_k=1+\sum_{j=1}^{k-1} q_k(j)\,t_j.$$
于是
$$t_k=\frac{1+\sum_{j=1}^{k-1} q_k(j)\,t_j}{1-q_k(k)}.$$
对所有 \(k\ge 2\)，分母都是正数，因为 \(q_k(k)\) 只是“这 \(k\) 次抽样全部互不相同”的概率：
$$q_k(k)=\frac{n(n-1)\cdots(n-k+1)}{n^k}\lt 1.$$
这意味着一旦概率表已知，就可以按顺序计算 \(t_2,t_3,\dots,t_n\)。不需要求解一个完整的线性方程组，整个问题天然就是一个三角形递推。
先看状态 \(2\)。从三个标签中抽两次，要么两次都落在同一标签上，要么落在两个不同标签上，因此
$$q_2(1)=\frac{1}{3},\qquad q_2(2)=\frac{2}{3}.$$
代入期望方程可得
$$t_2=1+\frac{1}{3}t_1+\frac{2}{3}t_2=1+\frac{2}{3}t_2,$$
所以
$$t_2=3.$$
再看状态 \(3\)。从三个标签中抽三次，出现 1 个、2 个、3 个不同标签的概率分别为
$$q_3(1)=\frac{1}{9},\qquad q_3(2)=\frac{2}{3},\qquad q_3(3)=\frac{2}{9}.$$
于是
$$t_3=1+\frac{1}{9}t_1+\frac{2}{3}t_2+\frac{2}{9}t_3.$$
代入 \(t_1=0\) 与 \(t_2=3\) 后得到
$$t_3=1+0+2+\frac{2}{9}t_3,$$
从而
$$\frac{7}{9}t_3=3,\qquad t_3=\frac{27}{7}.$$
这个小规模的精确值正好可以用来检验转移递推和期望递推是否一致。
最终答案就是 \(n=1000\) 时的 \(t_n\)。整个计算完全不依赖随机模拟；只要占位概率表 \(q_k(j)\) 已经填好，期望轮数就能由上面的公式确定下来。
C++、Python 和 Java 实现都采用同样的两阶段方案。第一阶段建立一个 \((n+1)\times(n+1)\) 的概率表，并按行推进。第 \(k\) 行对应“抽样次数为 \(k\)”时的分布，每个表项存储“恰好看到若干个不同标签”的概率。由于只有 \(0\le j\le k\le n\) 的三角区域有意义，所以每一新行都可以直接由前一行按照占位递推更新出来。
第二阶段保存每个状态的剩余期望轮数。实现先设定吸收状态的值 \(t_1=0\)，再按照 \(t_2,t_3,\dots,t_n\) 的顺序依次计算。每一个新值都只依赖更小状态的已知结果以及当前行的对角概率 \(q_k(k)\)，因此不需要数值迭代或矩阵求逆。最后输出 \(n=1000\) 时的期望值，并格式化为六位小数。
构造占位概率表需要
$$\sum_{k=0}^{n-1}(k+1)=O(n^2)$$
次更新。求解期望方程还需要
$$\sum_{k=2}^{n}(k-1)=O(n^2)$$
次额外运算。因此总时间复杂度为 \(O(n^2)\)。实现保留了完整的三角概率表，所以空间复杂度为 \(O(n^2)\)；存放期望值的一维数组只额外占用 \(O(n)\) 空间。
Положим \(X_0=n\). Если текущим состоянием является \(k\), то выполняются \(k\) независимых равновероятных выборок из \(n\) меток, а следующее состояние \(X_{r+1}\) равно числу различных меток, появившихся в этих \(k\) выборках. Поскольку на каждом шаге выполняется \(1 \le X_{r+1} \le k\), процесс неизбежно попадает в поглощающее состояние \(1\). Требуется найти математическое ожидание числа раундов, необходимых для перехода из \(n\) в \(1\); в самой задаче берется \(n=1000\), а результат выводится с шестью знаками после запятой.
По сути это конечная цепь Маркова. Из состояния \(k\) мы переходим к количеству занятых меток после \(k\) выборок в \(n\) равновероятных ячеек, то есть к стандартному распределению занятости.
Обозначим через \(t_k\) ожидаемое число дополнительных раундов до достижения состояния \(1\), если текущим является состояние \(k\). Тогда
$$t_1=0.$$
Нам также нужны вероятности перехода
$$q_k(j)=\Pr(X_{r+1}=j\mid X_r=k),\qquad 1\le j\le k.$$
Значит, комбинаторное ядро задачи таково: после \(k\) независимых выборок из \(n\) равновероятных меток какова вероятность увидеть ровно \(j\) различных меток?
При нуле выборок занято ровно ноль меток:
$$q_0(0)=1.$$
Добавим еще одну выборку. Чтобы после \(k+1\) выборок оказалось ровно \(j\) различных меток, возможны два взаимоисключающих случая:
либо после первых \(k\) выборок уже было ровно \(j\) различных меток и новая выборка попала в одну из них, либо после первых \(k\) выборок было ровно \(j-1\) различных меток и новая выборка впервые попала в новую метку.
Отсюда следует рекуррентная формула
$$q_{k+1}(j)=q_k(j)\frac{j}{n}+q_k(j-1)\frac{n-j+1}{n}.$$
Именно эту треугольную таблицу вероятностей вычисляют реализации. Эквивалентная замкнутая формула имеет вид
$$q_k(j)=\frac{n(n-1)\cdots(n-j+1)}{n^k}\,S(k,j),$$
где \(S(k,j)\) обозначает число Стирлинга второго рода. Но для прямого вычисления всех нужных значений рекуррентная схема удобнее.
Из состояния \(k\) один раунд тратится сразу, после чего цепь переходит в состояние \(j\) с вероятностью \(q_k(j)\). Поэтому
$$t_k=1+\sum_{j=1}^{k} q_k(j)\,t_j.$$
На первый взгляд это выглядит как замкнутое определение, потому что \(t_k\) стоит по обе стороны равенства. Но на правой стороне только одно действительно новое неизвестное: член с \(j=k\), соответствующий самопереходу.
Перенесем слагаемое при \(j=k\) влево:
$$\left(1-q_k(k)\right)t_k=1+\sum_{j=1}^{k-1} q_k(j)\,t_j.$$
Тогда
$$t_k=\frac{1+\sum_{j=1}^{k-1} q_k(j)\,t_j}{1-q_k(k)}.$$
Знаменатель положителен для любого \(k\ge 2\), поскольку \(q_k(k)\) есть всего лишь вероятность того, что все \(k\) выборок окажутся попарно различными:
$$q_k(k)=\frac{n(n-1)\cdots(n-k+1)}{n^k}\lt 1.$$
Следовательно, после построения таблицы вероятностей значения \(t_2,t_3,\dots,t_n\) можно вычислять последовательно. Полный линейный решатель не нужен.
Для состояния \(2\) две выборки из трех меток дают либо одну различную метку, либо две различные метки:
$$q_2(1)=\frac{1}{3},\qquad q_2(2)=\frac{2}{3}.$$
Поэтому
$$t_2=1+\frac{1}{3}t_1+\frac{2}{3}t_2=1+\frac{2}{3}t_2,$$
откуда
$$t_2=3.$$
Для состояния \(3\) имеем
$$q_3(1)=\frac{1}{9},\qquad q_3(2)=\frac{2}{3},\qquad q_3(3)=\frac{2}{9}.$$
Тогда
$$t_3=1+\frac{1}{9}t_1+\frac{2}{3}t_2+\frac{2}{9}t_3.$$
Подставляя \(t_1=0\) и \(t_2=3\), получаем
$$t_3=1+0+2+\frac{2}{9}t_3,$$
а значит
$$\frac{7}{9}t_3=3,\qquad t_3=\frac{27}{7}.$$
Это небольшое точное значение удобно использовать как проверку корректности всей схемы.
Нужный ответ равен \(t_n\) при \(n=1000\). Никакое моделирование не используется. Как только таблица занятости \(q_k(j)\) построена, математическое ожидание числа раундов определяется полностью и однозначно.
Реализации на C++, Python и Java придерживаются одного и того же двухэтапного плана. Сначала построчно строится таблица вероятностей размера \((n+1)\times(n+1)\). Каждая строка отвечает числу выборок \(k\), а каждая ячейка хранит вероятность увидеть конкретное число различных меток. Существенна только треугольная область \(0\le j\le k\le n\), поэтому каждая новая строка получается из предыдущей по рекуррентной формуле занятости.
Затем реализация хранит ожидаемое число оставшихся раундов для каждого состояния. Задается поглощающее значение \(t_1=0\), после чего последовательно вычисляются \(t_2,t_3,\dots,t_n\). Каждый новый элемент зависит только от уже известных меньших состояний и от диагональной вероятности \(q_k(k)\), так что никакой итерационной подгонки не требуется. В конце выводится значение для \(n=1000\) с шестью знаками после запятой.
Построение таблицы занятости требует
$$\sum_{k=0}^{n-1}(k+1)=O(n^2)$$
обновлений. Решение уравнений ожидания требует еще
$$\sum_{k=2}^{n}(k-1)=O(n^2)$$
арифметических операций. Следовательно, общее время работы равно \(O(n^2)\). Реализации хранят полную треугольную таблицу вероятностей, поэтому потребление памяти равно \(O(n^2)\), а массив ожиданий добавляет только \(O(n)\).
لنعرّف \(X_0=n\). إذا كانت الحالة الحالية هي \(k\)، فإننا نجري \(k\) سحوبات مستقلة ومتساوية الاحتمال من بين \(n\) وسمًا، ثم تكون الحالة التالية \(X_{r+1}\) هي عدد الأوسمة المختلفة التي ظهرت في هذه السحوبات \(k\). وبما أن كل جولة تحقق دائمًا \(1 \le X_{r+1} \le k\)، فإن العملية تصل في النهاية إلى الحالة الماصّة \(1\). المطلوب هو حساب عدد الجولات المتوقع للانتقال من \(n\) إلى \(1\)، وفي المسألة الأساسية نأخذ \(n=1000\) ونطبع النتيجة بدقة ست منازل عشرية.
الفكرة الأساسية هي النظر إلى العملية على أنها سلسلة ماركوف منتهية. فعندما نكون في الحالة \(k\)، فإن توزيع الانتقال إلى الجولة التالية يساوي تمامًا توزيع عدد الخانات المشغولة بعد رمي \(k\) كرات في \(n\) خانات متساوية الاحتمال.
لنرمز بـ \(t_k\) إلى العدد المتوقع من الجولات الإضافية اللازمة للوصول إلى الحالة \(1\) عندما تكون الحالة الحالية هي \(k\). عندئذ
$$t_1=0.$$
ونحتاج أيضًا إلى احتمالات الانتقال
$$q_k(j)=\Pr(X_{r+1}=j\mid X_r=k),\qquad 1\le j\le k.$$
وهكذا يصبح لبّ المسألة التركيبي هو السؤال التالي: بعد \(k\) سحوبات مستقلة من \(n\) أوسمة متساوية الاحتمال، ما احتمال أن نرى بالضبط \(j\) أوسمة مختلفة؟
عند عدم إجراء أي سحب، لا يظهر أي وسم:
$$q_0(0)=1.$$
الآن نضيف سحبًا جديدًا. لكي نحصل بعد \(k+1\) سحوبات على \(j\) أوسمة مختلفة بالضبط، فهناك حالتان متنافيتان:
إما أن أول \(k\) سحوبات كانت قد أنتجت بالفعل \(j\) أوسمة مختلفة ثم جاء السحب الجديد على أحد هذه الأوسمة، أو أن أول \(k\) سحوبات أنتجت \(j-1\) أوسمة مختلفة ثم وقع السحب الجديد على وسم جديد لم يظهر من قبل.
لذلك نحصل على العلاقة
$$q_{k+1}(j)=q_k(j)\frac{j}{n}+q_k(j-1)\frac{n-j+1}{n}.$$
وهذا بالضبط هو الجدول المثلثي للاحتمالات الذي تبنيه التطبيقات. وهناك صيغة مغلقة مكافئة هي
$$q_k(j)=\frac{n(n-1)\cdots(n-j+1)}{n^k}\,S(k,j),$$
حيث \(S(k,j)\) هو عدد ستيرلينغ من النوع الثاني. لكن من أجل حساب جميع القيم المطلوبة مباشرة، تكون العلاقة التراجعية هي الأسهل في التطبيق.
إذا بدأنا من الحالة \(k\)، فإننا نستهلك جولة واحدة فورًا، ثم تنتقل السلسلة إلى الحالة \(j\) باحتمال \(q_k(j)\). ومن ثم
$$t_k=1+\sum_{j=1}^{k} q_k(j)\,t_j.$$
قد تبدو هذه معادلة دائرية لأن \(t_k\) يظهر في الطرفين. لكن هذا ليس عائقًا حقيقيًا؛ فالحد الوحيد الذي يعيد استخدام \(t_k\) نفسه هو حد الحلقة الذاتية عند \(j=k\)، أما بقية الحدود فتعتمد فقط على حالات أصغر.
بنقل حد \(j=k\) إلى الطرف الأيسر نحصل على
$$\left(1-q_k(k)\right)t_k=1+\sum_{j=1}^{k-1} q_k(j)\,t_j,$$
ومنها
$$t_k=\frac{1+\sum_{j=1}^{k-1} q_k(j)\,t_j}{1-q_k(k)}.$$
والمقام موجب لكل \(k\ge 2\)، لأن \(q_k(k)\) ليس إلا احتمال أن تكون جميع السحوبات \(k\) مختلفة فيما بينها:
$$q_k(k)=\frac{n(n-1)\cdots(n-k+1)}{n^k}\lt 1.$$
وبالتالي يمكن حساب \(t_2,t_3,\dots,t_n\) بالترتيب التصاعدي بمجرد معرفة جدول الاحتمالات. لسنا بحاجة إلى حل نظام خطي عام.
في الحالة \(2\)، تؤدي سحبتان من بين ثلاثة أوسمة إلى ظهور وسم واحد مختلف أو وسمين مختلفين:
$$q_2(1)=\frac{1}{3},\qquad q_2(2)=\frac{2}{3}.$$
إذًا
$$t_2=1+\frac{1}{3}t_1+\frac{2}{3}t_2=1+\frac{2}{3}t_2,$$
ومن ثم
$$t_2=3.$$
أما في الحالة \(3\) فنحصل على
$$q_3(1)=\frac{1}{9},\qquad q_3(2)=\frac{2}{3},\qquad q_3(3)=\frac{2}{9}.$$
وعليه
$$t_3=1+\frac{1}{9}t_1+\frac{2}{3}t_2+\frac{2}{9}t_3.$$
وبالتعويض عن \(t_1=0\) و\(t_2=3\) نحصل على
$$t_3=1+0+2+\frac{2}{9}t_3,$$
ومنها
$$\frac{7}{9}t_3=3,\qquad t_3=\frac{27}{7}.$$
هذه القيمة الدقيقة الصغيرة تُستخدم كفحص جيد لصحة العلاقة الاحتمالية ومعادلة التوقع.
الإجابة النهائية هي \(t_n\) عند \(n=1000\). لا نحتاج إلى أي محاكاة عشوائية. فبمجرد اكتمال جدول الإشغال \(q_k(j)\)، يصبح عدد الجولات المتوقع محددًا مباشرة بهذه الصيغة.
تتبع تطبيقات C++ وPython وJava الخطة نفسها على مرحلتين. في المرحلة الأولى تُبنى مصفوفة احتمالات بحجم \((n+1)\times(n+1)\) صفًا بعد صف. كل صف يمثّل عدد سحوبات معينًا \(k\)، وكل خانة تخزن احتمال رؤية عدد محدد من الأوسمة المختلفة. ولا تكون ذات معنى إلا المنطقة المثلثية \(0\le j\le k\le n\)، لذلك يُشتق كل صف جديد مباشرة من الصف السابق باستخدام علاقة الإشغال.
وفي المرحلة الثانية تحتفظ الشيفرة بقيم التوقع للحالات المختلفة. تبدأ من القيمة الماصّة \(t_1=0\)، ثم تحسب \(t_2,t_3,\dots,t_n\) بالترتيب التصاعدي. كل قيمة جديدة تعتمد فقط على حالات أصغر محسوبة مسبقًا وعلى الاحتمال القطري \(q_k(k)\)، لذلك لا توجد حاجة إلى طريقة تقريبية تكرارية. وفي النهاية تُطبع قيمة التوقع عند \(n=1000\) مع ست منازل بعد الفاصلة.
بناء جدول الإشغال يحتاج إلى
$$\sum_{k=0}^{n-1}(k+1)=O(n^2)$$
تحديثات. كما أن حل معادلات التوقع يحتاج إلى
$$\sum_{k=2}^{n}(k-1)=O(n^2)$$
عملية حسابية إضافية. لذلك يكون الزمن الكلي \(O(n^2)\). وتحفظ التطبيقات الجدول المثلثي الكامل للاحتمالات في الذاكرة، لذا يكون استهلاك الذاكرة \(O(n^2)\)، بينما تضيف مصفوفة التوقعات \(O(n)\) فقط.