expected length of linked list

Question

Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $[1, \dots, T]$

Q) Derive the expected length for the linked list just before the k'th operation is performed

---

so we need the weighted average of all possible values of some random variable. for each $X_i$ let it be the number of steps for given events. If theres a prepend we add a node whereas if theres an access we do nothing to the length. How do we come up with an equation for expectd length?

$E(X) = something \cdot (k-1)$ since just before $k$ but not sure how to derive the probability yet

Any help appreciated

Answer 1

$E(X) = something \cdot (k-1)$

That $something$ is $p$. The full formula should be $E(Y)=1+p(k-1)$, where $Y$ is the random variable that is the length for the linked list just before the $k$-th operation is performed.

To convince yourself that $p$ is the right answer, try a few cases. When $p=1$, every operation adds one element to $T$. When $p=0$, no prepend operation will happen. When $p=1/2$, an element is added about half of the times. Make sense?

Here is the simple reason why. Let $Y_i$ be the increase of length in step $i$. Then

• $Y_1, Y_2, \cdots, Y_n$ are independent random variables,
• $E(Y_i)=p$ for all $i$ since the probability of prepending is $p$ for each operation.

Since the expectation of the sum is the sum of the expectations for independent variables, we have $$\begin{align} E(Y) &=E(1+ Y_1+ Y_2+ \cdots+ Y_{k-1})\\ &=1+ E(Y_1)+E(Y_2)+\cdots+E(Y_{k-1})\\ &=1+ p(k-1) \end{align}$$ where 1 comes from the initial one element in $T$.

Answer 2

You can break this down into basics. Recall that the expected value of the length will be the sum of all possible lengths multiplied by their probability: $$\mathbb{E}[L] = \sum_{i = 0}^{k-1} i \cdot P(L = i)$$

The probability $P(L = i)$ is the probability of length being equal to $i$ after $k-1$ operations. This means exactly $i$ of the $k-1$ operations would've been prepend and $k - 1 - i$ operations would've been search. The probability of this will be:

$$P(L = i) = p^{i} \cdot (1 - p)^{k - 1 - i} \cdot N(i, k - 1)$$

Where $N(i, k - 1)$ is the number of ways we can do $i$ prepends out of the k-1 total operations. Consider that there are multiple orders to those operations (e.g. {prepend, prepend, search} and {prepend, search, prepend} both reach length 2). We can "choose" $i$ of the $k - 1$ operations to be prepend then the rest will be search, thus we have:

$$N(i, k - 1) = \binom{k - 1}{i}$$

Now we can plug this back in:

$$\begin{align*} \mathbb{E}[L] & = \sum_{i = 0}^{k-1} i \cdot p^{i} \cdot (1 - p)^{k - 1 - i} \cdot \binom{k - 1}{i} \end{align*}$$

You can see this is clearly the expected value of a binomial distribution and we get:

$$\mathbb{E}[L] = p \cdot (k-1)$$

(See here if you want to work through these last two steps precisely).