Engineering / Mathematics — Probabilistic Algorithms
Generating a Random Non-Increasing Sequence
Sampling a random non-increasing sequence in a bounded range, and its role as a subroutine in generating factored numbers.
Executive summary
A random non-increasing sequence is generated by repeatedly drawing uniformly from the range below the current value, terminating when the value reaches one.
The construction is short, its expected length is logarithmic, and it is the engine of a surprising algorithm for producing random numbers together with their factorisations.
Learning objectives
- State the generation procedure.
- Bound the expected length of the sequence.
- Explain its role in the factored-number algorithm.
01The procedure
Random non-increasing sequence
bound na non-increasing sequence from at most n down to 1- Set s₁ by drawing uniformly from {1, ..., n}.
- For i = 2, 3, ...: draw sᵢ uniformly from {1, ..., sᵢ₋₁}.
- Stop when sᵢ = 1.
- Return the sequence s₁ ≥ s₂ ≥ ... ≥ 1.
expected O(ln n) termsEach term is drawn from the range determined by its predecessor, so the sequence is non-increasing by construction and terminates because the value strictly decreases in expectation.
02Expected length
From a current value s, the next value is uniform on {1, ..., s}, so its expectation is about s/2. The value therefore halves in expectation each step, giving a logarithmic expected length.
E[length] ≈ ln n for the sequence starting from nA more careful analysis using the harmonic sum confirms the expected number of terms is asymptotically ln n, matching the intuition from the halving argument up to constants.
03Role in generating factored numbers
The connection is not obvious. Taking the prime terms of such a sequence and multiplying them produces an integer with a known factorisation, and with the right acceptance rule the result is uniform over a range.
Generate the sequence
Draw a random non-increasing sequence bounded by n.
Keep the primes
Discard composite terms; the surviving primes are the candidate factors.
Form the product
Multiply the retained primes to obtain a candidate integer with known factorisation.
Accept or reject
Accept with a probability chosen so that the output is uniform on the target range.
04Frequently asked questions
Why does the sequence terminate?
Because the value is non-increasing and strictly decreases with probability at least 1 − 1/s at each step from value s. It cannot remain above 1 indefinitely with positive probability.
Is the sequence uniform over non-increasing sequences?
No, and it is not intended to be. The distribution is precisely the one that makes the downstream acceptance rule produce a uniform factored integer, which is a different and more useful requirement.
Could the sequence be generated more directly?
The recursive draw is already optimal in expected cost at O(ln n) terms. The interest lies in the distribution it induces, not in the efficiency of the generation itself.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 167-170.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.