Problem 45 - A Computational Introduction to Number Theory and Algebra

Question

Let \(S\) be a set of size \(m \geq 1,\) and let \(s_{0}\) be an arbitrary, fixed element of \(S\). Let \(F\) be a random variable that is uniformly distributed over the set of all \(m^{m}\) functions from \(S\) into \(S .\) Let us define random variables \(X_{i},\) for \(i=0,1,2, \ldots,\) as follows: $$ X_{0}:=s_{0}, \quad X_{i+1}:=F\left(X_{i}\right)(i=0,1,2, \ldots) $$ Thus, the value of \(X_{i}\) is obtained by applying the function \(F\) a total of \(i\) times to the starting value \(s_{0}\). Since \(S\) has size \(m,\) the sequence \(\left\\{X_{i}\right\\}_{i=0}^{\infty}\) must repeat at some point; that is, there exists a positive integer \(n\) (with \(n \leq m\) ) such that \(X_{n}=X_{i}\) for some \(i=0, \ldots, n-1 .\) Define the random variable \(Y\) to be the smallest such value \(n .\) (a) Show that for every \(i \geq 0\) and for all \(s_{1}, \ldots, s_{i} \in S\) such that \(s_{0}, s_{1}, \ldots, s_{i}\) are distinct, the conditional distribution of \(X_{i+1}\) given the event \(\left(X_{1}=s_{1}\right) \cap\) \(\cdots \cap\left(X_{i}=s_{i}\right)\) is the uniform distribution on \(S .\) (b) Show that for every integer \(n \geq 1,\) we have \(Y \geq n\) if and only if the random variables \(X_{0}, X_{1}, \ldots, X_{n-1}\) take on distinct values. (c) From parts (a) and (b), show that for each \(n=1, \ldots, m,\) we have $$ \mathrm{P}[Y \geq n \mid Y \geq n-1]=1-(n-1) / m $$ and conclude that $$ \mathrm{P}[Y \geq n]=\prod_{i=1}^{n-1}(1-i / m) \leq e^{-n(n-1) / 2 m} $$ (d) Using part (c), show that $$ \mathrm{E}[Y]=\sum_{n \geq 1} \mathrm{P}[Y \geq n] \leq \sum_{n \geq 1} e^{-n(n-1) / 2 m}=O\left(m^{1 / 2}\right) $$ (e) Modify the above argument to show that \(\mathrm{E}[Y]=\Omega\left(m^{1 / 2}\right)\).

Step-by-Step Solution

Answer

Question: Show that the expected number of distinct numbers generated in this process \(E[Y]\) = \(\Omega(m^{1/2})\). #tag_title# Determine Lower Bound on Probabilities #tag_content# To show \(\mathrm{E}[Y] = \Omega(m^{1/2})\), we need to find a lower bound on the probabilities \(\mathrm{P}[Y \geq n]\). Using \(1 - x \geq e^{-x - x^2/2}\) for \(0 < x < 1\), we obtain: $$ \mathrm{P}[Y \geq n] = \prod_{i=1}^{n-1}\left(1 - \frac{i}{m}\right) \geq \prod_{i=1}^{n-1} e^{-i/m - i^2/(2m^2)} $$ #tag_title# Use the Lower Bound on Probabilities #tag_content# Now, we can compute the expected value of \(Y\) using the lower bound of the probabilities: $$ \mathrm{E}[Y] = \sum_{n \geq 1} \mathrm{P}[Y \geq n] \geq \sum_{n \geq 1} \prod_{i=1}^{n-1} e^{-i/m - i^2/(2m^2)} $$ #tag_title# Sum over the Right Range #tag_content# Observe that we need to sum only up to \(n = m^{1/2}\). So, let's consider this range: $$ \mathrm{E}[Y] \geq \sum_{n \geq 1}^{\lfloor m^{1/2} \rfloor} \mathrm{P}[Y \geq n] \geq \sum_{n \geq 1}^{\lfloor m^{1/2} \rfloor} \prod_{i=1}^{n-1} e^{-i/m - i^2/(2m^2)} $$ #tag_title# Simplify the Lower Bound #tag_content# Most of the terms in each of the products cancel out, leading to a simpler expression: $$ \mathrm{E}[Y] \geq \sum_{n \geq 1}^{\lfloor m^{1/2} \rfloor} e^{-\frac{n(n - 1)}{2m}} $$ Interpreting this expression using the integral test, we can see that the sum is at least a constant times \(m^{1/2}\). #tag_title# Conclude the Result #tag_content# Therefore, we have shown that \(\mathrm{E}[Y] = \Omega(m^{1/2})\). With the earlier result of \(\mathrm{E}[Y] = O(m^{1/2})\), we have characterized the expected value of \(Y\) as \(E[Y]=\Theta(m^{1/2})\).

Step 1: Observe the Conditional Distribution Formula

We must show that the conditional distribution of \(X_{i+1}\) is uniform, given the event \(\left(X_{1}=s_{1}\right) \cap \cdots \cap\left(X_{i}=s_{i}\right)\). The conditional probability of \(X_{i+1}\) given \(X_1, \ldots, X_i\) is: $$ \mathrm{P}[X_{i+1} = s_{i+1} \mid (X_1 = s_1) \cap \cdots \cap (X_i = s_i)] = \frac{\mathrm{P}[(X_1 = s_1) \cap \cdots \cap (X_i = s_i) \cap (X_{i+1} = s_{i+1})]}{\mathrm{P}[(X_1 = s_1) \cap \cdots \cap (X_i = s_i)]} $$

Step 2: Count the Number of Functions

Recall that \(F\) is a random variable representing one of the \(m^m\) functions from \(S\) into \(S\). Since we are looking at the conditional probability of \(X_{i+1}\), we can focus on the first \(i+1\) steps in creating the function. At each of the steps, we can obtain the first \(i+1\) values of the sequence. There are \(m\) choices for \(s_{i+1}\) and \((m-1)^i\) choices for the rest of the function values, since, for each remaining function value, there are \(m-1\) choices excluding the given \(s_1, \ldots, s_i\). Thus, the numerator of our conditional probability is: $$ \frac{(m)(m-1)^i}{m^m} $$ Similarly, the denominator is given by: $$ \frac{(m-1)^i}{m^{i}} $$

Step 3: Compute the Conditional Probability

By dividing the numerator and denominator, we will obtain the conditional probability of \(X_{i+1}\): $$ \frac{(m)(m-1)^i}{m^m} \cdot \frac{m^i}{(m-1)^i} = \frac{1}{m} $$ Therefore, the conditional distribution of \(X_{i+1}\) is indeed uniform on \(S\). (b) \(Y \geq n\) if and only if \(X_{0}, X_{1}, \ldots, X_{n-1}\) are distinct

Step 4: Show the "if" direction

If \(X_0, X_1, \ldots, X_{n-1}\) are distinct, then there can be no repetitions among the first \(n\) values of the sequence. Since \(Y\) represents the smallest integer \(n\) for which \(X_n = X_i\) for some \(i < n\), then, in this case, \(Y \geq n\) must be true.

Step 5: Show the "only if" direction

Conversely, suppose \(Y \geq n\). That means there is no integer \(i

Step 6: Derive Conditional Probability

Using the results of part (a) and part (b), we can compute the conditional probability \(\mathrm{P}[Y \geq n \mid Y \geq n-1]\). From part (b), having \(Y \geq n-1\) means that \(X_0, X_1, \ldots, X_{n-2}\) have distinct values. There are only \(n-1\) possible values that \(X_{n-1}\) can take (except for \(X_n\)). Thus, the conditional probability is: $$ \mathrm{P}[Y \geq n \mid Y \geq n-1] = \frac{m-(n-1)}{m} = 1-\frac{n-1}{m} $$

Step 7: Compute \(\mathrm{P}[Y \geq n]\)

Next, we want to find \(\mathrm{P}[Y \geq n]\). We can use the conditional probabilities found above: $$ \mathrm{P}[Y \geq n] = \mathrm{P}[Y \geq n \mid Y \geq n-1] \cdot \mathrm{P}[Y \geq n-1] $$ By applying this formula repeatedly, we get: $$ \mathrm{P}[Y \geq n] = \prod_{i=1}^{n-1} (1-\frac{i}{m}) $$

Step 8: Apply Inequality

Using the inequality \(1-x \leq e^{-x}\), we will have: $$ \mathrm{P}[Y \geq n] \leq \prod_{i=1}^{n-1} e^{-i/m} = e^{-n(n-1)/(2m)} $$ (d) Compute \(\mathrm{E}[Y]\)

Step 9: Use the Definition of Expectation

The expected value of \(Y\) can be computed by summing up the probabilities: $$ \mathrm{E}[Y] = \sum_{n\geq 1} \mathrm{P}[Y\geq n] $$

Step 10: Apply the Inequality Found in (c)

Using the inequality we found in part (c), we get: $$ \mathrm{E}[Y] \leq \sum_{n \geq 1} e^{-n(n-1)/2m} $$ This sum converges and is in the order of \(m^{1/2}\), so: $$ \mathrm{E}[Y]=O(m^{1/2}) $$ (e) Show \(\mathrm{E}[Y] = \Omega(m^{1/2})\) To modify the argument to show that \(\mathrm{E}[Y] = \Omega(m^{1/2})\), you can proceed with the same steps as in (d), but derive a lower bound on the sum. One way is to find an appropriate lower bound on the probabilities \(\mathrm{P}[Y \geq n]\) and then use that bound in the summation for the expected value. This will require manipulation of inequalities and a careful choice of the lower bounds. Finally, you will arrive at the lower bound that is also in the order of \(m^{1/2}\), showing \(\mathrm{E}[Y] = \Omega(m^{1/2})\).

Key Concepts

Uniform Distribution

Understanding the concept of a uniform distribution is fundamental in the study of probability and statistics. A uniform distribution, often visualized as a flat line, implies that every outcome in a certain range has an equal chance of occurring. There are no biases towards any particular outcome.

When it comes to computational number theory, a uniform distribution dictates that a function will map any input to an output in such a way that all possible outputs are equally likely. This is a crucial concept when studying random variables and functions, as it sets the stage for a fair and predictable model.

In the given exercise, we observe that the random variable representing a function, is uniformly distributed over the functions from set S into S. As the solution clarifies in step 3, regardless of the preceding sequence of outcomes, the next outcome has an equal probability, reinforcing the premise of a uniform distribution. When students struggle to understand this, a helpful visualization might be picturing an equally sided dice, where each roll (outcome) is independent and has the same probability of landing flat.

Conditional Distribution

The conditional distribution offers insight into the behavior of a random variable given a certain precondition or evidence is fulfilled. Rather than looking at the entire sample space, it narrows down the focus.

In our exercise, we consider the probability distribution of a variable, given we know the outcomes of previous variables. This concept is demonstrated clearly in the exercise's solution steps 1-3, when there's need to calculate the conditional probability of the next random variable in the sequence given the previous ones.

It is crucial for students to grasp that conditioning on certain events changes the sample space to only those outcomes that meet the criteria. The example in the exercise demonstrating that the conditional distribution of the next variable is still uniform, even given the previous outcomes, is a testament to the independence of the outcomes of our particular random variable. As an improvement to the exercise, it may benefit students to include various real-world examples that illustrate different conditional probabilities, to solidify the understanding of this concept.

Expected Value

Definition and Significance

The expected value, often denoted as E[X] for a random variable X, is a weighted average of all possible values that X can take on, each value weighted by its respective probability of occurring. Think of it as the long-term average or mean if you repeat an experiment over and over again.

Application in the Exercise

In the discussed exercise, the expected value provides a measure of the average number of steps needed before the sequence repeats. This concept is particularly tricky but pivotal; students are to understand from step 9 that \(\mathrm{E}[Y]\) is a sum of probabilities of \(Y\) being greater or equal to each integer \(n\).

Utility in Computations

The bounds of an expected value, as shown in parts (d) and (e) of the solution, help us understand the efficiency of algorithms in computational number theory. The provided solutions skillfully use inequalities to find a suitable order of magnitude for the expected value, giving a rough idea about how the expected number of steps grows with the size of set S, which is crucial in algorithmic complexity analysis.

To enhance student comprehension, it might be beneficial to compare the concept of the expected value to more familiar terms such as averages from everyday scenarios, such as an average score in a game. Making these parallels can make a seemingly abstract concept of expected value much more tangible.

Previous

Problem 44

Other exercises in this chapter

Problem 43

Let \(\left\\{X_{i}\right\\}_{i=1}^{n}\) be a finite, non-empty, 4 -wise independent family of random variables, each uniformly distributed over a set \(S\). Le

View solution

Problem 44

Let \(k\) be a positive integer, let \(n:=k^{2}-k+1,\) let \(I\) and \(S\) be sets of size \(n,\) and let \(s_{0}\) be a fixed element of \(S .\) Also, let \(I^

View solution

Problem 42

Show that for every prime \(p,\) there exists a pairwise independent family of random variables \(\left\\{X_{i}\right\\}_{i \in \mathbb{Z}_{p}},\) where each \(

View solution

Key Concepts

Uniform Distribution

Understanding the concept of a uniform distribution is fundamental in the study of probability and statistics. A uniform distribution, often visualized as a flat line, implies that every outcome in a certain range has an equal chance of occurring. There are no biases towards any particular outcome.

When it comes to computational number theory, a uniform distribution dictates that a function will map any input to an output in such a way that all possible outputs are equally likely. This is a crucial concept when studying random variables and functions, as it sets the stage for a fair and predictable model.

In the given exercise, we observe that the random variable representing a function, is uniformly distributed over the functions from set S into S. As the solution clarifies in step 3, regardless of the preceding sequence of outcomes, the next outcome has an equal probability, reinforcing the premise of a uniform distribution. When students struggle to understand this, a helpful visualization might be picturing an equally sided dice, where each roll (outcome) is independent and has the same probability of landing flat.

Conditional Distribution

The conditional distribution offers insight into the behavior of a random variable given a certain precondition or evidence is fulfilled. Rather than looking at the entire sample space, it narrows down the focus.

In our exercise, we consider the probability distribution of a variable, given we know the outcomes of previous variables. This concept is demonstrated clearly in the exercise's solution steps 1-3, when there's need to calculate the conditional probability of the next random variable in the sequence given the previous ones.

It is crucial for students to grasp that conditioning on certain events changes the sample space to only those outcomes that meet the criteria. The example in the exercise demonstrating that the conditional distribution of the next variable is still uniform, even given the previous outcomes, is a testament to the independence of the outcomes of our particular random variable. As an improvement to the exercise, it may benefit students to include various real-world examples that illustrate different conditional probabilities, to solidify the understanding of this concept.

Expected Value

Definition and Significance

The expected value, often denoted as E[X] for a random variable X, is a weighted average of all possible values that X can take on, each value weighted by its respective probability of occurring. Think of it as the long-term average or mean if you repeat an experiment over and over again.

Application in the Exercise

In the discussed exercise, the expected value provides a measure of the average number of steps needed before the sequence repeats. This concept is particularly tricky but pivotal; students are to understand from step 9 that \(\mathrm{E}[Y]\) is a sum of probabilities of \(Y\) being greater or equal to each integer \(n\).

Utility in Computations

The bounds of an expected value, as shown in parts (d) and (e) of the solution, help us understand the efficiency of algorithms in computational number theory. The provided solutions skillfully use inequalities to find a suitable order of magnitude for the expected value, giving a rough idea about how the expected number of steps grows with the size of set S, which is crucial in algorithmic complexity analysis.

To enhance student comprehension, it might be beneficial to compare the concept of the expected value to more familiar terms such as averages from everyday scenarios, such as an average score in a game. Making these parallels can make a seemingly abstract concept of expected value much more tangible.