uniform_sample_infinite_sequence.go

uniform_sample_infinite_sequence.go

// 🍍🍌🥝🍍🍌🥝🍍🍌🥝🍍🍌🥝🍍🍌🥝🍍🍌🥝
// time: O(N)
// space: O(1)
// Go Playground: https://go.dev/play/p/ZLq6zcsG6lw
// why: making smoothie! 🍧
package main

import (
	"fmt"
	"math/rand"
)

type Node struct {
	V    string
	Next *Node
}

func sampleUniform(l *Node) *Node {
	if l == nil {
		return nil
	}
	r := l
	count := 1
	for q := l; q != nil; q = q.Next {
		count++
		if rand.Float64() < 1/float64(count) {
			r = q
		}
	}
	return r
}

func main() {
	l := &Node{V: "🥝", Next: &Node{V: "🍍", Next: &Node{V: "🍌"}}}
	N := 100
	for i := 0; i < N; i++ {
		fmt.Printf("%d: %#v\n", i, sampleUniform(l))
	}
}

for truly uniform sampling probability for each is 1/N. but when N -> infinity, then probability of picking any is approaching 0. so algorithms probability has to approach 0 too. meaning it will underfloat float value and will never trigger. so basically you should never select any value and keep iterating.

now, this is different from non-infinite but undetermined N. in which case probability is non zero, but unknown and depends on number of elements. we basically have to go through whole sequence. we have to decrease probability of picking last one as we go.