Question

Generalized Pólya Urn Scheme. In an urn containing \(a\) white and \(b\) black balls we select a ball at random. If a white ball is selected we return it and add \(\alpha\) white and \(\beta\) black to the urn and if a black ball is selected we return it and add \(\gamma\) white and \(\delta\) black, where \(\alpha+\beta=\gamma+\delta\). The process is repeated. Let \(X_{n}\) be the number of selections that are white among the first \(n\) repetitions. (i) If \(P_{n, k}=\operatorname{Pr}\left\\{X_{n}=k\right\\}\) and \(\varphi_{n}(x)=\sum_{k=0}^{n} P_{n, k} x^{k}\) establish the identity $$ \begin{array}{r} \varphi_{n}(x)=\frac{(\alpha-\gamma)\left(x^{2}-x\right)}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}^{\prime}(x) \\ +\frac{\\{x[(n-1) \gamma+a]+b+(n-1) \delta\\}}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}(x) \end{array} $$ (ii) Prove the limit relation \(E\left(X_{n} / n\right) \rightarrow \gamma /(\beta+\gamma)\) as \(n \rightarrow \infty\).

Short answer

(i) We establish the identity for the probability generating function (pgf) as follows: \[\varphi_{n}(x) = \frac{(\alpha-\gamma)\left(x^{2}-x\right)}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}^{\prime}(x) + \frac{\\{x[(n-1) \gamma+a]+b+(n-1) \delta\\}}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}(x) .\] (ii) We prove the limit relation for the expected value: \[E\left(\frac{X_{n}}{n}\right) \rightarrow \frac{\gamma}{\beta+\gamma} \quad\text{as }\ n \rightarrow \infty.\]

Step-by-step solution

(i) Recurrence relation for the pgf

Based on the rules of the urn scheme, we can describe the pgf as follows. At the \(n^{th}\) step, with probability \(\frac{(a+b+(n-1)(\alpha+\beta))(a+(n-1)\gamma)}{(n-1)(\alpha+\beta)+a+b}\) a white ball is drawn, and with probability \(\frac{(a+b+(n-1)(\alpha+\beta))b}{(n-1)(\alpha+\beta)+a+b}\) a black ball is drawn. This allows us to compute \(\varphi_n(x)\) using the urn's condition at the \((n-1)^{th}\) step. Now, let's compute the pgf of \(X_{n}\) using the conditional probability and the pgf \(\varphi_{n-1}(x)\):\\ \[\varphi_{n}(x) = E\left[x^{X_n}\right]= \frac{(a+(n-1)\gamma)}{(n-1)(\alpha+\beta)+a+b}x \varphi_{n-1}(x) +\frac{b}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}(x) .\] Differentiate this equation with respect to \(x\):\\ \[\varphi_{n}'(x) = \frac{(a+(n-1)\gamma)}{(n-1)(\alpha+\beta)+a+b}\varphi_{n-1}(x) +\frac{(a+(n-1)\gamma)}{(n-1)(\alpha+\beta)+a+b}x \varphi_{n-1}'(x) +\frac{b}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}'(x) .\] Then, we can rearrange this expression and obtain the desired identity:\\ \[\varphi_{n}(x) = \frac{(\alpha-\gamma)\left(x^{2}-x\right)}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}^{\prime}(x) + \frac{\\{x[(n-1) \gamma+a]+b+(n-1) \delta\\}}{(n-1)(\alpha+\beta)+a+b} \varphi_{n-1}(x) .\]

(ii) Limit relation for the expected value

Now let's compute the expected value of the ratio \(X_n/n\):\\ \[E\left(\frac{X_n}{n}\right) = \frac{1}{n} E(X_n) = \frac{1}{n} \sum_{k=0}^{n} k P_{n, k}.\] Additionaly, we know that \(E(X_n) = n\frac{a \gamma + b \alpha}{a (\alpha + \beta) + b (\alpha + \beta)}\), provided that \(\alpha+\beta=\gamma+\delta\). Therefore, we have:\\ \[E\left(\frac{X_n}{n}\right) = \frac{n\frac{a \gamma + b \alpha}{a (\alpha + \beta) + b (\alpha + \beta)}}{n}=\frac{a \gamma + b \alpha}{a (\alpha+\beta)+b (\alpha+\beta)}=\frac{a \gamma +b \alpha}{a \gamma + a \beta+b \alpha+b \beta}.\] Now, taking the limit as \(n \rightarrow \infty\) we obtain:\\ \[\lim_{n\rightarrow\infty} E\left(\frac{X_n}{n}\right) =\lim_{n\rightarrow\infty}\frac{a \gamma + b \alpha}{a \gamma + a \beta+b \alpha+b \beta}=\frac{\gamma}{\beta+\gamma}.\] And we have obtained the desired limit relation: \[E\left(\frac{X_{n}}{n}\right) \rightarrow \frac{\gamma}{\beta+\gamma} \quad\text{as }\ n \rightarrow \infty .\]

Key concepts

Stochastic Processes

A stochastic process is a collection of random variables, typically indexed by time, that describes a system evolving over time in a probabilistic manner. In our context, the Generalized Pólya Urn Scheme is a classic example of a stochastic process.

The number of white balls selected, denoted as random variables \(X_n\) for \( n = 1, 2, 3, ...\), captures the essence of this randomness. The value of \(X_n\) depends on the outcome of the previous selections, which aligns well with the stochastic nature of the problem. Each selection alters the composition of the urn, demonstrating the dependence of future results on past actions - a property common in many stochastic processes.

Understanding this concept is crucial for students as it lays the groundwork for more complex probabilistic models. These processes form a vast area of study applicable in fields ranging from finance to physics, making it an indispensable tool for analyzing systems influenced by randomness.

Probability Generating Function

The Probability Generating Function (PGF), denoted as \(\varphi_{n}(x)\), is a powerful tool in the analysis of discrete random variables, particularly when dealing with sums or sequences of random variables.

In the urn model, the PGF is a concise way to encode all the probabilities \(P_{n, k}\) associated with the random variable \(X_n\) into a single function. This function simplifies computations, such as finding expected values and determining probabilities of different outcomes. The PGF is particularly useful for recursive processes, like the urn scheme, as it allows the student to express the PGF of \(X_n\) in terms of the PGF of \(X_{n-1}\), making process analysis more manageable.

The given exercise shows a complex relation for \(\varphi_n(x)\), which represents the progression of the urn's content as the process evolves. The recurrence relation helps to understand the long-term behaviour of the stochastic process within the Urn scheme framework, and it is a fundamental concept for students studying probability theory.

Expected Value

The Expected Value of a random variable provides a measure of the central tendency or average outcome one might anticipate. In the urn problem, the expected value helps in understanding the average number of times a white ball is chosen in a large number of selections.

To convey this to students clearly, it's important to highlight that the expected value is essentially a long-term average. It's not about predicting a single outcome but about providing insight into what can be expected over many trials, given the odds defined by \(\alpha, \beta, \gamma, \delta\) for drawing and adding balls in each trial. This concept is critical, as it guides decision making and predictions for processes that involve random variation.

Moreover, the expected value plays a crucial role in determining whether a stochastic process is fair or biased towards a certain outcome. This is exemplified in the proof of how the ratio \(\frac{X_n}{n}\) evolves, showcasing the underlying probability structure of the urn scheme.

Limit Theorems

In probability theory, Limit Theorems are pivotal as they describe the behavior of a stochastic process as the number of trials or time progresses to infinity. The most renowned among these is the Central Limit Theorem. However, in our urn model exercise, we are more focused on the concept of convergence in probability or in expectation.

The problem demonstrates a limit theorem by showing that the expected ratio of white ball selections to the total number of trials \(\frac{X_n}{n}\) converges to a constant as the number of trials \(n\) goes to infinity. This behavior is critical for students to understand as it indicates stability in the long-term proportions of the urn content, despite the randomness in each trial.

Intuitively, the limit theorems reassure us that regardless of the initial conditions (\(a\) and \(b\)), as the number of trials grows, the influence of the starting conditions becomes negligible, and the system's behaviour becomes predictable to some extent. This is an important insight for students as it helps them to appreciate the power of long-term averages in the presence of random fluctuations.