import random


def geometric_sample(pool, max_num_items,
                     sample_prob):
  """Samples k items using geometric sampling without replacement.

  At each step, item #i will be sampled with probability sample_prob^i (except
  the last item which gets the remaining probability mass). Item #i will then
  be removed from the pool.

  Args:
    pool: An ordered list of items to sample.
    max_num_items: Maximum number of items to sample.
    sample_prob: Probability for the geometric sampling.

  Returns:
    A list of sampled items.
  """
  pool = list(pool)
  sampled = []
  for _ in range(max_num_items):
    if not pool:
      break
    i = 0
    while random.random() > sample_prob and i < len(pool) - 1:
      i += 1
    sampled.append(pool.pop(i))
  return sampled