# Expected Number of Dishes in Indian Buffet Process?

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_{

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

• 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? – Rylan Schaeffer Mar 3 at 23:33

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*}