2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It's fine I understood it after your response $\endgroup$ – mammy wood Apr 4 at 6:41
  • $\begingroup$ Thanks! I believe I have shown the formula clearly and rigorously in my answer now. $\endgroup$ – Apass.Jack Apr 4 at 6:46
1
$\begingroup$

$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$.

$\endgroup$
  • 1
    $\begingroup$ The list starts with one element. $\endgroup$ – Yuval Filmus Apr 4 at 6:46
  • $\begingroup$ @YuvalFilmus you beat OP and me. Updating ... $\endgroup$ – Apass.Jack Apr 4 at 6:48
  • $\begingroup$ should it be $E(X) = 1 + p(k-1)$ since it starts with 1 element? $\endgroup$ – mammy wood Apr 4 at 6:58
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I am afraid that you have been trying to make something very simple more difficult. $\endgroup$ – Apass.Jack Apr 4 at 6:34
  • $\begingroup$ I'm not sure what you mean. I was going back to the basics of expected value over a binomial distribution and showing how you get there. $\endgroup$ – ryan Apr 4 at 6:49
  • $\begingroup$ I agree that you are going to the basics. It might be enlightening as well to show that complicated meticulous formula will lead to the same formula. On the other hand, your computation also uses the fact P(AB)=P(A)P(B) if A and B are independent. From that fact/definition, it is immediate that sum of the expectation is the expectation of the sum. $\endgroup$ – Apass.Jack Apr 4 at 7:13
  • $\begingroup$ Fair enough, this is just how I initially broke it down. Sums of expectations did not initially come to me. $\endgroup$ – ryan Apr 4 at 15:57
  • 1
    $\begingroup$ Upvoted, partly to emphasize the determination. Often, one can get an answer by going back to the very basics and taking pains to advance a lot of reasoning. $\endgroup$ – Apass.Jack Apr 4 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.