Universal prediction  and compression of \emph{i.i.d.} distributions
has been studied extensively. It is well known that the optimal
\emph{log-loss} or \emph{redundancy} for predicting length$-n$
sequences over $k$ symbols is $\Theta( k\log n)$. 
For large-alphabet applications, it is natural to
consider a variant where at each step, given
the past observations, we must provide a distribution
over the observed symbols, and one \emph{new} symbol.
 
Improving on  the previous results, we show that the 
redundancy at least  $n^{1/3}$ and at most  $n^{1/3} \log^{4/3} n$, thus achieving tight bounds up to logarithmic factors. 
The result holds uniformly for all distributions over all alphabet sizes.