Question 1 · Fig. 1
What does the next point cost?
0 / 24 insertions
- Arrival
- Charge
- Update
Tree totals, replay and display
Costly visits are drawn more slowly: the charge takes seconds, since . Play explains three arrivals at this pace, then surveys faster. This is a display choice, not a result of the paper.
One path, one cost history
Same arrivals; central star is fixed at the origin.
Expectation & bounds
Question 2 · Fig. 3 · Section 5.2
Does memory reduce the mean cost?
One path is noisy. Averaging many independent random sequences estimates the expected cost per insertion. The paper compares the exponential memory with the input-order path, the star at the initial point, the center star and the prefix centroid; for the expectation is exact.
The paper's six panels, as examples:
Mean cost per insertion
Fig. 3Read the numerical results
Values appear after a run.
Question 3 · Fig. 2 · Section 3.3
Where do random arrivals land?
The center star pays per point because a uniform point of the ball has radius with . In high dimension almost all the volume sits near the boundary; the rescaled distance has an exponential limit. Memory and power do not change this input law.
Input radius
Fig. 2(a)Rescaled distance to the boundary
Fig. 2(b)Question 4 · Fig. 4 · Section 5.3
Where does the memory settle in the long run?
For a fixed the state has a unique stationary law. Its root mean square radius is (Eq. 45): memory moves the band toward the center, dimension sharpens it. The cost power does not enter.
Panels of the paper:
State radius, d = 1…50
Fig. 4 · your γOne row as a probability density
Fig. 4 rowThe nine panels of Fig. 4, as in the paper
Question 5 · Fig. 6 · Appendix C
How long is the next connection in the long run?
Move between its endpoints. The rescaled state coordinate goes from the coordinate law of a uniform point to a Gaussian; the insertion length goes from the distance between two uniform points to the radius law, and decreases in stochastic order (Theorem 3.15).
N counts retained states in one correlated chain, after a separate automatic burn-in. Choose 100–10,000,000; runs exceeding 250 million point-coordinate steps are rejected, never shortened. The eight-memory comparison below has its own N.
Memories of the paper:
Rescaled state coordinate
Fig. 6(a)Insertion length
Fig. 6(b)The eight memories of Fig. 6, as in the paper
This N applies to each of the eight memories, independently of the individual plot above. Automatic burn-in is additional for each correlated chain. Choose 100–10,000,000; the combined run must fit 250 million point-coordinate steps.
Question 6 · Theorem 4.8 · Fig. 5 · Appendix D
Can chosen arrivals make memory costly?
An adversary chooses the points. Alternating the two ends of a diameter forces the asymptotic mean cost , and for , nothing does worse (Theorem 4.8). For some above , blocks of repeated endpoints can cost more (Proposition D.1).
One period, insertion by insertion
Prop. D.1Every block length at your and
exact familyThe whole parameter plane · Fig. 5
(a) Best periodic block
Fig. 5(a)(b) Selected memories
Fig. 5(b)What is being measured?
For insertions we generate points, starting at . Each arrival connects to the previous memory . Its contribution is the -power of the full insertion length.
L = Σ ‖pᵢ − xᵢ₋₁‖ᵅ
The dashed connection is charged before memory moves. The green movement subdivides that connection. At the movement and the remaining branch together have the insertion length. At other powers the edge-power sum (Eq. 3) is a different quantity.
The center-star benchmark uses an externally supplied origin. It counts connections from to that origin; joining to the origin would be an additional cost.
Expectation, observation and limit
Exact expectation averages over all possible random inputs. Monte Carlo estimates it from independent complete trials. A shaded 95% interval uses 1.96 standard errors, is approximate, pointwise, and omitted below 30 complete trials.
Theoretical bounds enclose the finite expectation. A stationary law describes the long run at a fixed ; its samples come from one correlated chain and receive no independent-sample interval. At , memory stays at the first random point, even though the stationary limit concentrates at the center.
Every numerical cost uses all coordinates. Spatial views show the ball in 3D, or an orthographic projection of the first three coordinates. A projection can hide a long connection; the full length remains in the readout.