Question

In the list example of Section \(3.6 .1\) suppose that the initial ordering at time \(t=0\) is determined completely at random; that is, initially all \(n !\) permutations are equally likely. Following the front-of-the-line rule, compute the expected position of the element requested at time \(t\). Hint: To compute \(P\left\\{e_{j}\right.\) precedes \(e_{i}\) at time \(\left.t\right\\}\) condition on whether or not either \(e_{i}\) or \(e_{j}\) has ever been requested prior to \(t\).

Short answer

The short answer for the expected position of the element requested at time \(t\), denoted as \(E(t)\), can be found by using the formula: \(E(t) = \sum_{i=1}^n\sum_{k=1}^{i-1} k \cdot P_{ij}(t)\) where \(n\) is the total number of elements and \(P_{ij}(t)\) is the probability that element \(e_j\) precedes element \(e_i\) at time \(t\). The base case is \(P_{ij}(0) = \frac{1}{2}\), and the recursive formula is: \(P_{ij}(t) = \left(1-\frac{2}{n}\right) P_{ij}(t-1) + \frac{1}{n} P_{ji}(t-1)\)

Step-by-step solution

Consider the hint given

We need to compute the probability \(P\left\\{e_{j}\right.\) precedes \(e_{i}\) at time \(t\left. \right\\}\). To do this, we need to condition on whether or not either \(e_{i}\) or \(e_{j}\) has ever been requested prior to \(t\). Let's denote this probability as \(P_{ij}(t)\) and we have: \(P_{ij}(t) = P\left\\{e_{j}\right. \text{ precedes } e_{i} \text{ at time } t \left| \right. \text{ neither } e_{i} \text{ nor } e_{j} \text{ has been requested prior to time } t\right. \}\) At time \(t=0\), we know that the probability of any pair \((i, j)\) being in any specific order is \(\frac{1}{2}\). So, \(P_{ij}(0) = \frac{1}{2}\)

Compute probability of specific arrangement at time \(t>0\)

Now let's compute \(P_{ij}(t)\) for \(t > 0\). There are two cases to consider: 1. Neither \(e_i\) nor \(e_j\) is requested at time \(t\): In this case, their relative order doesn't change, and so the probability is the same as \(P_{ij}(t-1)\). This happens with probability \(1-\frac{2}{n}\), because there are \(n\) elements in total and \(n-2\) elements are not \(e_i\) and \(e_j\). 2. One of the elements \(e_i\) or \(e_j\) is requested: In this case, their relative order is reversed, which means we need to consider the probability \(P_{ji}(t-1)\). Each element has a \(\frac{1}{n}\) probability of being requested at time \(t\). Considering both cases, we have: \(P_{ij}(t) = \left(1-\frac{2}{n}\right) P_{ij}(t-1) + \frac{1}{n} P_{ji}(t-1)\)

Compute expected position

To compute the expected position of the element requested at time \(t\), we should find the probability that any \(e_i\) is in the \(k\)-th position in the list. We can do this by iterating over the possible elements preceding \(e_i\) and their probabilities of being just before \(e_i\). Then we sum this probability over all possible values of \(i\) and \(k\). The expected position of the element requested at time \(t\) is given by: \(E(t) = \sum_{i=1}^n\sum_{k=1}^{i-1} k \cdot P_{ij}(t)\) With the base case \(P_{ij}(0) = \frac{1}{2}\) and the recursive formula from step 2, we can compute the expected position for any given time \(t\).

Key concepts

Understanding Permutations in Probability

Permutations are fundamental to understanding complex probability problems. In essence, a permutation is an arrangement of items in a specific order. For example, think of a list of elements \(e_1, e_2, \text{...}, e_n\). The number of ways you can arrange these elements is represented by \(n!\), which is the product of all positive integers up to \(n\). In probability models, each of these arrangements, or permutations, is considered to have an equal chance of occurring unless stated otherwise.

When we consider a situation where the initial order of elements is chosen randomly, it means any permutation is as likely as any other. This is critical in our scenario because it lays the groundwork for calculating probabilities related to the positions of elements over time under the given rules of changing order, such as the 'front-of-the-line' rule mentioned in the exercise. Grasping the concept of permutations prepares you to understand various outcomes in a probability model and analyze random processes systematically.

Calculating Expected Position

The concept of 'expected position' is quite intriguing. It refers to the average or mean position of an element over all possible permutations. As the name suggests, it's what you 'expect' on average. We calculate it as a sum of all potential positions multiplied by their corresponding probabilities.

Consider an element \(e_i\) in a list. The 'expected position' of \(e_i\) is not just where it starts but where it tends to be after certain events, like requests in our example. The expected position takes into account the likelihood of each outcome and sums up all the probabilities across different positions. In a random process, this helps us foresee the average behavior of each element under the defined conditions, which is crucial in many applications, such as queuing theory, search algorithms, and predictive models.

Applying Conditional Probability

Conditional probability is a measure of the probability of an event occurring given that another event has already occurred. This is represented symbolically as \(P(A|B)\), which reads as 'the probability of A given B.' Understandably, it's a way to account for additional information that might affect the likelihood of events.

The use of conditional probability is highlighted in our exercise when we calculate the chances of one element preceding another at a given time \(t\) with the knowledge of prior requests. By considering whether \(e_i\) or \(e_j\) has been requested before time \(t\), we're essentially tweaking the probabilities dynamically. Conditional probability allows us to update our calculations based on new data, which is especially useful in dynamic systems that evolve over time, such as predicting customer behavior, market trends, or in our case, the ordering of elements in a list.