Markov Inequality for lower bounds

Question

In a paper I found a strange application of Markovs inequality which I couldn't follow maybe you can help. $X_k$ is the set of $k$-element Subsets of $\mathbb{Z}_d^n$ we fix a $C^{-1} \in X_{k-1}$ and given a $j \in [n]\setminus C^{-1}$ we let $C_j = (C^{-1},j) \in X_k$. We have an event called $\textbf{Good}(C^{-1},i)$:

$\underset{j \sim [n]\setminus C^{-1}}{\mathbb{P}}\left[ l_{C_j}=f(\sigma(C_j)) \right] \geq \frac{1}{d} + \frac{\epsilon}{2}$

where $l_C \in \mathbb{Z}_d$ are guesses for the value of $f:\mathbb{Z}_d^k \rightarrow \mathbb{Z}_d$

Now the Author follows that we can use Markovs inequality and get this lower bound:

$ \underset{C^{-1} \sim X_{k-1}}{\mathbb{P}}\left[ \textbf{Good}(C^{-1},i) \right] \geq \frac{\epsilon}{2 \cdot d^2} $

I have no clue how he got there i've never seen Markov being used for lower bounds and also dont know how to deal with the propability of a propability being larger than some value. For a more detailed posing of the question or where I got it from https://arxiv.org/abs/1404.0024 on Page 39 "Proof of Theoreme 6"

Answer 1

The notation is a touch painful and I don't understand any of the context, but the following is likely to do the trick.

There are three random variables: $C, j, \sigma$. Now, fix $C$ and $\sigma$. Then the first probability you state (that is, $\underset{j \sim [n]\setminus C^{-1}}{\mathbb{P}}\left[ l_{C_j}=f(\sigma(C_j)) \right]$) is just a number. But take $C$ fixed and $\sigma$ a random variable, then that first probability is a function of $\sigma$, and thus a random variable---and so you can ask whether this random variable exceeds, say, $1/d + \epsilon/2$, nothing weird in that.

For the lower bound, most likely write the probability $P(\textrm{GOOD}(C^{-1}, i)) = E1\{\textrm{GOOD}(C^{-1}, i)\}$, and now apply Markov's the usual way (the expectation is now on the upper-bound-side of things, as per usual!)

In your comment, you specify that you do not understand how we can rewrite this probability as an expectation. If you are asking how one does this in general, then note that on a probability space $(\Omega, \Sigma, P)$, we define the Lebesgue integral, denoted $E$, by first defining the indicator function of a set $A \in \Sigma$ to be given by $1[A](\omega) = 1$ if $\omega \in A$ and $0$ otherwise, and we define $E1[A] = P(A)$. If your comment is asking how this specific probability can be rewritten as an expectation, then I might need you to specify what is different here from the general case!