1
$\begingroup$

I'm trying to generate a random sequence of integers whereby no two consecutive values are equal to each other. This sequence is meant to simulate changes in state only. Is there some term or concept which captures this idea that's already been formalized in probability?

My current approach is to generate an excess of random ints from the count I desire followed by a reduction that eliminates all the entries whose diff in the sequence is zero and further reducing to just the quantity desired should I have succeeded in yielding the necessary amount.

This related stack overflow post asks some implementation details for such on operation but I wonder if there's anything formal out there that conceptualizes this operation like a constrained random walk or something along those lines.

https://stackoverflow.com/questions/20284347/sequence-of-random-selection-with-no-two-consecutive-objects-same

$\endgroup$
  • 1
    $\begingroup$ Your question needs to specify much more. What probability distribution do you want for this sequence? For instance, should all integers within a specified range be equiprobable? And regardless of that, what should be the probability distribution of consecutive pairs of integers? Triples of integers? Etc. $\endgroup$ – whuber Jan 23 at 22:56
  • $\begingroup$ That's a good clarification indeed. I haven't thought that far yet, just wanted to find a target I could broaden a search for to ferret out what variants existed that I could evaluate against my use case. I had uniform distribution in mind, using for instance the numpy function randint which starts off uniformly distributed but I realize becomes bias in distribution as I filter the resulting sequence. How its distributed after such an operation is an open question for me. $\endgroup$ – jxramos Jan 23 at 23:10
  • 1
    $\begingroup$ If the filtration is to eliminate all consecutive values (repeatedly) until none exist, that's equivalent to generating all possible such sequences equiprobably. There's a very simple algorithm to generate a sequence of length $n$ in the range $0,1,\ldots,N-1.$ Starting at $0$ (which is discarded), it computes the next number by uniformly generating a difference in the set $1,2,\ldots,N-1$ and adding that to the current number modulo $N$. Here is R code: function(n, N) { cumsum(sample.int(N-1, n, replace=TRUE) %% N) %% N } The first (mathematically superfluous) %% prevents overflow. $\endgroup$ – whuber Jan 23 at 23:17
  • 1
    $\begingroup$ For some insight into the possibilities, look into low-discrepancy sequences. Although much of the focus is in higher dimensions, everything applies to one dimension (your application). $\endgroup$ – whuber Jan 23 at 23:36
0
$\begingroup$

Looks like there's such a thing indeed.

https://en.wikipedia.org/wiki/Biased_random_walk_on_a_graph

In network science, a biased random walk on a graph is a time path process in which an evolving variable jumps from its current state to one of various potential new states; unlike in a pure random walk, the probabilities of the potential new states are unequal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.