  The Ku\v{c}era-G\'acs theorem is a landmark result in algorithmic randomness
asserting that every real is computable from a Martin-L\"of random real. If the
computation of the first $n$ bits of a sequence requires $n+h(n)$ bits of the
random oracle, then $h$ is the redundancy of the computation. Ku\v{c}era
implicitly achieved redundancy $n\log n$ while G\'acs used a more elaborate
coding procedure which achieves redundancy $\sqrt{n}\log n$. A similar upper
bound is implicit in the later proof by Merkle and Mihailovi\'c. In this paper
we obtain strict optimal lower bounds on the redundancy in computations from
Martin-L\"of random oracles. We show that any nondecreasing computable function
$g$ such that $\sum_n 2^{-g(n)}=\infty$ is not a general upper bound on the
redundancy in computations from Martin-L\"of random oracles. In fact, there
exists a real $X$ such that the redundancy $g$ of any computation of $X$ from a
Martin-L\"of random oracle satisfies $\sum_n 2^{-g(n)}<\infty$. Moreover, the
class of such reals is comeager and includes a $\Delta^0_2$ real as well as all
weakly 2-generic reals. This excludes many slow growing functions such as $\log
n$ from bounding the redundancy in computations from random oracles for a large
class of reals. On the other hand it was recently shown that if $\sum_n
2^{-g(n)}<\infty$ then $g$ is a general upper bound for the redundancy in
computations of any real from some Martin-L\"of random oracle. Our results are
obtained as an application of a theory of effective betting strategies with
restricted wagers which we develop.
