Computing expectation exercises; using linearity of expectation and iterator random variables

Question

Disclaimer: This is homework that is overdue by, but I do want to understand it and get through it, so any hints or guidance is appreciated

This is for an algorithms class currently dealing with random algorithms; my class does have an online discussion with a lot of hints, but I still can't really get it going.

I hear that I have to use indicator random variables for most of these, and apply linearity of expectation to get the desired expectation.

Indicator random variables, from reading up online, is defined as the variable that only takes values 0 and 1 and has a probability associated with it.

So far, for 1 and 2, I've tried to examine the problem from a smaller standpoint.

Before jumping into any of them, I had to identify relevant equations:

In my class notes, I have Linearity of expectation as

$ E[X + Y] = E[X] + E[Y] $

 For 1)

I deduced that a complete binary tree of depth n has total number of vertices $|V| = 2^n - 1$. Since we aren't really interested in the root node, we can actually generalize it to $|E| = |V| = 2^n - 2$, where $|V|$ does not include the root node, and a binary tree that consists of only the root node has depth = 1

I started out trying to deduce and compute the expectation for a simple binary tree, where the tree is of depth 2 and consists of only three nodes.

If I let $p = 1/2$

For tree of depth 2 $ E[X] = 0 * (p*p) + 1 * (p * (1-p)) + 1 * (p * (1-p)) + 2 * (1-p)^2 = 1 $

For a tree of depth 1, obviously $ E[X] = 0 $ all of the time

For a tree of depth 3, I would have three 'cases'

 1) the right subtree's edge is deleted. There are three cases in here: one of the child edges of this subtree is deleted, the other child is this is deleted, or none of the children are deleted
 2) the left subtree's edge is deleted. There are three cases in here, identical to the one where the right subtree is deleted
 3) a combination of three leaves are deleted

Obviously, this got a lot more complex after the tree has depth greater than 2 and it wasn't worth going further into since I was only laying out the cases to get a better understanding of the pattern. I'm not confident at all at my method of attacking this problem, and this is where I am now

 For 2)

I followed the advice of the hint, and calculated the probability a sequence of length $k$ is monotone. I tackled this the same way as 1), brute forcing each combination up til I got

$ p = \frac{k + 1}{2^{k}} $

Since at each length $k$, there are $k + 1$ possible monotone strings and for each $k$, the are $2^k$ possible strings.

In essence, I'm stuck at this part too.

I cant really say much either for 3, as I had no idea how to start that as opposed to the rest of them

My professor says to

Write the random variable whose expectation you are trying to compute as a sum of indicator random variables and then use linearity of expectation.

That last statement is pretty much my main question in this whole topic, as it seems to be the key to figuring all of them out. I tried looking up examples for the latter, but it seems pretty scarce and it's not in my textbook.

Thanks for reading, hope you can help!

Answer 1

On 2)

The probability that a sequence of length $k$ is monotone is $\left(k+1\right)2^{-k}$.

This because there are exactly $k+1$ distinct patterns that will be labeled as monotone, and each pattern has a probability of $2^{-k}$ to occur.

A sequence of length $n$ has $\binom{n}{k}$ subsequences of length $k$. Give each a number $r\in\left\{ 1,\dots,\binom{n}{k}\right\} $ and let $X_{r}$ take value $1$ if the referred subsequence is monotone and let $X_{r}$ take value $0$ if it is not monotone. Define: $$X:=X_{1}+\cdots+X_{\binom{n}{k}}$$ Then $X$ equals the number of monotone subsequences of a sequence of length $n$ that have length $k$.

The $X_{i}$ are equally distributed and this with: $$\mathbb{E}X_{i}=1.\mathbb{P}\left(X_{i}=1\right)+0.\mathbb{P}\left(X_{i}=0\right)=\mathbb{P}\left(X_{i}=1\right)=\left(k+1\right)2^{-k}$$ This leads to: $$\mathbb{E}X=\mathbb{E}X_{1}+\cdots+\mathbb{E}X_{\binom{n}{k}}=\binom{n}{k}\left(k+1\right)2^{-k}$$

On 3)

Let $\mathcal{A}_{5}\subseteq\wp\left(V\right)$ denotes the collection of subsets of $V$ that have cardinality $5$ and for every $A\in\mathcal{A}_{5}$ define rv $X_{A}$ by stating that it takes value $1$ if set $A$ is independent and takes value $0$ otherwise.

Then $X:=\sum_{A\in\mathcal{A}_{5}}X_{A}$ is the number of independent subset and: $$\mathbb{E}X=\mathbb{E}\sum_{A\in\mathcal{A}_{5}}X_{A}=\sum_{A\in\mathcal{A}_{5}}\mathbb{E}X_{A}$$

If $p$ denotes the probability that set $\left\{ 1,2,3,4,5\right\} $ is independent then $\mathbb{E}X_{A}=p$ for each $A\in\mathcal{A}_{5}$ and the cardinality of $\mathcal{A}_{5}$ is $\binom{n}{5}$.

So: $$\mathbb{E}X=\binom{n}{5}p$$ What remains is computing $p$.

Can you do that?

Answer 2

On 1: Suppose a node is on depth $i$ from the root (the root is on depth $0$, its direct children is of depth $1$, etc). What is the probability of this node to still be connected to the root? It is equal to the probability that none of the $i$ edges between it and the root is removed, i.e.

$$2^{-i}$$

For a node of depth $i$ from the root, define $X_i$ to be the indicator random variable that takes the value of $1$ if it's still connected to the root by the end of the edge removals. We have

$$E[X_i] = \Pr(X_i = 1) = 2^{-i}$$

Let $X$ be the sum of all $X_i$ for all nodes. We want to compute $E[X]$.

For a complete binary tree of depth $k$, how many nodes are there of depth $i \le k$? There are $2^i$ such nodes. So,

\begin{eqnarray*} E[X] &=& E[\sum_{0 \le i \le k} 2^i E[X_i] \\ &=& \sum_{0 \le i \le k} 2^i E[X_i] \\ &=& k+1 \end{eqnarray*}

Where the second line is due to the linearity of expectation.