2
$\begingroup$

I can't figure out what the notation $[x \neq k ]$ means. Here's a bit of context:

The formula is: $Pr[A_i^k = 1] = \frac{[i\neq k]}{|k-i| + 1} = \begin{cases} \frac{1}{k-i+1} \text{ if } i \lt k \\ 0 \text { if } i = k \\ \frac{1}{i-k+1} \text{ if } i \gt k \end{cases}$

and is part of a chapter where the average expected time of operations of a randomised treap are proved.

$A_i^k$ is an indicator variable defined as $[ x_i \text{ is a proper ancestor of }x_k ]$ where $x_n$ is the node with the $n$-th smallest search key. That probability comes up because $\text{depth}(x_k) = \sum_{i=1}^{n} A_i^k$ and $\mathbf{E}[\text{depth}(x_k)] = \sum_{i=1}^nPr[A_i^k = 1]$.

I have no access to the pages that explain the notation since I'm studying from a pdf of a few pages taken from a book.

$\endgroup$
2
  • 1
    $\begingroup$ I can't suggest one character edit, but I think in the denominator on the left hand side of the equation you meant to use $|k - i|$ instead of $|k - 1|$. Like: $\frac{[ i \neq k]}{|k - i| + 1}$. $\endgroup$ Jun 30 '20 at 17:50
  • $\begingroup$ @MarceloFornet yes. I'll fix it. $\endgroup$ Jun 30 '20 at 17:51
6
$\begingroup$

It is used like a boolean where $[i \neq k] = 1$ if $i \neq k$ and $0$ otherwise. Notice that $[i \neq k]$ is equivalent to $i < k$ or $i > k$ for numbers, which is the right part of the equation you wrote.

It is called Iverson bracket and in general $[statement] = 1$ if $statement$ is true and $0$ otherwise.

$\endgroup$
3
  • $\begingroup$ Thanks. Never encountered that before. $\endgroup$ Jun 30 '20 at 17:50
  • 1
    $\begingroup$ It's called the Iverson bracket. Might want to add that to your answer. $\endgroup$ Jun 30 '20 at 18:05
  • $\begingroup$ @AaronRotenberg thanks for pointing out, haven't heard about that name before. Added to the answer. $\endgroup$ Jul 1 '20 at 21:36

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.