I'm sure this question has an answer somewhere online, but I can't find it. Suppose I have an Indian Buffet Process with $T$ customers and concentration parameter $\alpha$. For those unfamiliar with the IBP, the IBP is a Bayesian nonparametric model defining a distribution over binary matrices $Z$ with $T$ rows (customers) and an infinite number of columns (dishes). Let $z_{t, k}$ denote the $t$th row and $k$th column of $Z$, and let $\Lambda_t$ denote the number of non-empty columns of $Z$ after the $t$th customer has sampled their dishes.

The IBP gives the following sequential sampling process:

The first customer samples $\lambda_1 \sim Poisson(\alpha/1)$ new "dishes". We set the first $\lambda_1$ entries in the first row of $Z$ to 1 i.e. $z_{1, k} = 1$ for $k \in [1, \lambda_t]$

Each subsequent customer does three things:

  1. Samples dishes proportional to the number of previous customers who sampled that dish:

$$\forall k \leq \Lambda_t, \quad p(z_{t, k} \lvert z_{<t}, \alpha) = \frac{1}{t} \sum_{t' = 1}^T \delta (z_{t', k} = 1)$$

  1. Samples $\lambda_t \sim Poisson(\alpha/t)$ new dishes. We set $z_{t, k} = 1$ for $k \in [\Lambda_{t-1}+1, \Lambda_{t-1} + \lambda_t]$

  2. Add the number of new dishes to the previous number of total dishes i.e. $\Lambda_t \leftarrow \Lambda_{t-1} + \lambda_t$

My question: what is the expected number of non-empty columns (or equivalently, the expected number of sampled dishes) $\Lambda_t$?

  • 1
    $\begingroup$ Almost immediately after I posted this, I found a CMU reference (cs.cmu.edu/~epxing/Class/10708-14/scribe_notes/…) which says the number of non-empty columns is distributed $Poisson(\alpha H_T)$, where $H_T := \sum_{t=1}^T \frac{1}{t}$. Can someone provide a derivation? $\endgroup$ – Rylan Schaeffer Mar 3 at 23:33

I realized this problem has a straightforward answer almost immediately after posting :facepalm:

The easy answer is that each customer adds $\lambda_t$ new dishes and $\lambda_t \sim Poisson(\alpha / t)$. Consequently, by linearity of expectation, we have:

$$ \begin{align*} \Lambda_t &= \sum_{t=1}^T \lambda_t\\ \mathbb{E}[\Lambda_t] &= \mathbb{E}[\sum_{t=1}^T \lambda_t]\\ &=\sum_{t=1}^T \mathbb{E}[\lambda_t]\\ &=\sum_{t=1}^T \frac{\alpha}{t}\\ &= \alpha \sum_{t=1}^T \frac{1}{t} \end{align*} $$


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.