expected length of linked list 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
$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)
&amp;=E(1+ Y_1+ Y_2+ \cdots+ Y_{k-1})\\
&amp;=1+ E(Y_1)+E(Y_2)+\cdots+E(Y_{k-1})\\
&amp;=1+ p(k-1)
\end{align}$$
where 1 comes from the initial one element in $T$.