Expected amount of increments of a base-4 number until it has 5 digits, when each digit has a 1/6 chance of being reset to 0

Question

Let's say I have a base-4 number $N$, with the initial value of $N = 00000$. The following function is applied to $N$ iteratively:

1. $N$ is incremented by 1 (i.e. if $N = 02033$, on the next iteration it will be $02100$)
2. Then, each digit has a 1/6 chance of being reset back to 0 ($03210$ might become $00210$, $03010$, $03000$, etc.)
3. Repeat.

On average, how many iterations will it take until $N$ becomes $10000$ (1024) after the first step of the function?

In case it helps at all with clarity, here is a JavaScript equivalent to this scenario:

const array = [0, 0, 0, 0];
function findRight(arr) {
    let index = -1;
    for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== 3) {
        index = i;
        break;
    }
    }
    return index;
}
function next() {
    const val = findRight(array);
    if (val !== -1) {
        array[val] += 1;
        if (val !== 0) array[val - 1] = 0;
    } else {
        return true; // all digits are 3; N = 1024
    }
    array.forEach((val, index) => {
        if (Math.floor(Math.random() * 6) == 5) {
            array[index] = 0;
        }
    })
}

(Apologies if the formatting/writing of this question is strange; I just have no idea how to explain this in proper math format, so a bit of code-like syntax is mixed in. Any edits to make this question more clear or more "mathy" would be greatly appreciated!)

Answer 1

There are two main approaches here, and under the hood they'll both come down to very similar systems of equations. Either way, I'm going to swap the order of your two steps, so we think of one "turn" as a) possibly resetting some digits to 0 and then b) adding 1.

First, you could let $f(n) = $ expected turns until victory if you start with score $n$, and start writing equations involving values of $f$. For example, $f(0) = 1 + f(1)$ since if you're in state 0 you will always move to state 1. $f(1) = 1 + \frac{5}{6} f(2) + \frac 1 6 f(1)$ since after 1 step you have $\frac 1 6$ chance to reset your value and end up at 1 again, and otherwise you'd end up at 2. And so on. This will eventually give a linear system of 1024 equations and you could solve it to compute all the $f$ values. Then $f(0)$ is the answer you want.

Alternatively, you can view this as a Markov chain with 1025 states (from 0 through 1024) where the "10000" state is absorbing. If you build (or write code to build) that transition matrix, then the Wikipedia article I just linked provides a formula for the expected time until reaching the absorbing state. Note for runtime purposes: The formula involves inverting a matrix $Q$ and then multiplying $Q^{-1}$ by a vector of all 1s. Inverting a $1025 \times 1025$ matrix may take a little while depending what solver you're using. Instead of computing that inverse, you could view this as solving a linear system like $Qx = $(vector of all 1s), which can be solved much faster than fully computing $Q^{-1}$.

I don't know whether you're hoping for an exact (fraction) answer vs whether floating point precision is good enough for you, so I won't go further into implementation details. If I were solving this and I wanted an exact answer I'd use Mathematica; if I wanted a floating point answer I'd use Python.

For problems of this type, we could normally at least get a not very accurate floating point answer much more easily, just by actually simulating the process a bunch of times and averaging the result. Unfortunately that doesn't work for this problem because the typical length of one game is so long that you may not even be able to simulate a single full game.

EDIT: Exact answer and implementation

In the question, OP stated: "until N becomes 10000 (1024)". Those numbers don't match up: 10000 would be 256. This makes me not sure whether they meant 10000 (256) vs. 100000 (1024), so I'll include both answers. I'll give the exact answers as fractions just so you can compute more decimal places on the approximations if you want.

For the case where we count up to 10000 (state 256), the answer is $$\frac{399133152090263798547275810543929312656142607992620861180133849347900262273754411261298344932889461431684886365835989699995774143723698586853636562275485685037972443082743099909180178510859768240848030490764236712524498516633924676371154504435198888483674168096706303551884261740641455076970582573137341225096881125208741956251788936041104456847354920594579981542374188762515921164989173186499638395623887695308088079005239108382609367590084940057842559356576274701464339090526846087258769900599300646141837035853769421179528841696271382585325743321817493675959458354318001076191959964304601}{644114876959713330822703650336885250520481331443965633584307570993229323626932756036964628972522561260668856218084914667149474722719046257464573459045222137454532953759080605088049278870725910028634380270567174784034802342593206960279969607058553576679307732915217675557931021411215816397236838071898745173884690323577135426648799114768526685244835066509405979977223259685362507168686533456482953943779752922755991991988237792160551359607713702272919367243410144597503677298931451300659543763292048945690027039745473302900791168212890625}$$ or approximately $\boxed{6.197 \times 10^{53}.}$

For the case where we count up to 100000 (state 1024), the answer is even bigger! It's $$\frac{6327062043854864349490533490775065161766252759298440924496738600000275381712466248096235866756883208444457339775361821129155380965549001060041268860914310793891336362235685316536583917723154807529143379937090258118909872991475682654059807923312020283347055933474181146832379436341018611257277536338307387632085955301590034338252933189667627230367180082881968036483363797441820592401498562418868069562814863760237771034817219903764733204927919963337432735522272206501808452521918354755014670359961514214771351176963753085674450848289787324723262626854509146611336662374744296915328358754177209637586228696517188345942107257858693907663792123685216711315135673809260983585045291409902293097323605753341126813570939465233717676449935382047755727755730807707103021771324473375795697082039107645416457094238517678941590521538452745524788646553647071954490226438609593840339804453656896577905749099810492750716430222154263911287694696980769274891712129634070087307850760582186459149540993838247984789761980605160507196824922256000140416632395514317825732901015012352472611699871755054119008956640040746640264819206814364827986610641138146697711542665419780141104602615683208943774019973927469498542324731331492470219996336221913575707771320624431213030925377883539013665692821467531341236483870605530877839656768636195303668509010950588619196704868773905403532690826735016129132108594813717244683499386492781407119658634027584453963775374500774039784456075281964304070012142180021100994294460021947140236102594422703112980278653887797348099042588581829202902027866990327650318965776720875534193056844621388769323470109511385014661607728071307523039152624162866736806173435359602082386625177894665808436165280432900615191223161489309557652867541592589487241361847095022672048267468510194191342203600214699288356916901261750710035531038440336901075885174846575030237800305350936641864709888982819843994883231405984598432054496120930995224635203854785855785343842350272027466304128152824155620196882555992497416054896800501586320741075139268007215611950626425803697506758865929113590521105846941639500679725244287209512441134782649133941426061131269295453840132698595079084579498580712084554171977574934424652189415990220234243540035040366611459648097446100293159819500678263454496348381237602976952690724064689402172870371364881647012056056381759850594080862166102853118830547404561367673360937744685314701469280387684812381991372590158780726960429057864133531094509449801174656991144166792012356815976041000497280395613920187723015585951766817292741837327637038815181297350953869042097025763157294536544505950839477864893173395565582385657257583002701037651928484074531025075319938761833321531223123557009931795885770958825675171603639341319974585898575009423975338418975275541433920005120489379752556604089416793569368095330322960186463924484371764220806563708369289704210492589042370542619468064294566105313538625356873410031565388169432345425607121977651048281271748371}{110870664460386669401148107528716844199483478539697735775314489588277341473540810508071241213432970834293163741131052295414359445765475494383015341602105474898916797535252132162562253896891890932970680613176120095672183211459748561093828941125651420210458360860300431522878564355560714450041106779035406515939842811954585662117919808325285384086883606846242868326545195353209189664923123037968598669436576513961470320049698936131671479467923703846123174987660987673026519936040191458431124483539930967788648920159159880020905061745603105037649290382813682294673795616228623543963273332503757072694958271477566541003899114604853597333492876765002482510448071851388634582727285459341983242200249677213884394442494999450740895304478485387063984685364575781294593081983111974333825676368502703248301230452091306293845791820014878407234945192770606438613643366184551784275182321716698845716400242315944464444737544027915055945652589029768438589570004942828360885471512909827230119199379136448535654681099622593937852669427035825102773229333593215297011002430525095973394022966357545955937239472721073596602250153491338714888871470939171863318702271495564075747650443780710418851143863363517862876563089799904308352217597219226812358586799708644833907078618419981078680522489837541792454436430521776461061356177123584173939412109940212122326064655559697195766979541250360315795361723273451766887253415181851365749310676269595503787830816660869879548819800761461374773740531135589295961560574191823251607105553234589685188193801804435369634144128491033394158802875427278291158262996257834933851457685220734960953695338136080800943089498374684052719038361209467707009067372906954095179890278316735366834770089066135641826183070300795666069035527007369025976320289562001905299390570711364887047136534065276929886709343657143505536761280543681719516646792313644730154905127726926249936843552661597596276272805170773001392512542024354800388837472305178204632073845923843206663783454961014056302075843758520624203943707909128966362555429165274139223793574086213642043885923343473815168354730808358888656038606592978242659871768311176856639941055275858134620100419899571318780928150704632653744028210480066343312937542971779285540761680084459314815975321843310659886594597113464457932411213164134059264679758527614689449127230167179922244964200293456172313393380880068614658637774360686443607106603643862994850927847696069869521709273436118306533278118383923389244769184872562729339863089453296660913336709517537430992528747444164582973155734969460273365182660299044837586675095224365235080429002799077737021011496973502024108959935929378281979983432298784463976293324094513081945478916168212890625}$$ or approximately $\boxed{5.707 \times 10^{280}.}$

Here is the exact Python code I used to build the transition matrix and dumps it to disk:

import itertools
import copy
from fractions import Fraction as frac

def build_transition_matrix(N, B):
    def sid_to_state(n):
        out = []
        for k in range(N):
            out.append(n % B)
            n //= B
        out.reverse()
        return out, n

    def state_to_sid(q):
        return sum(B**k * q[N-1-k] for k in range(N))
    
    D = B ** N + 1  # dimension
#     mat = np.zeros((D, D))
    mat = [[frac(0) for k in range(D)] for j in range(D)]
    
    # handle the last state separately.
    mat[D-1][D-1] = frac(1)
    for sid in range(D-1):
        state, leftover = sid_to_state(sid)
        for revert in itertools.product(range(2), repeat=N):
            curr = copy.deepcopy(state)
            p = 1
            for k in range(N):
                if revert[k]:
                    p *= frac(1)/6
                    curr[k] = 0
                else:
                    p *= frac(5)/6
            # increment the state.
            curr[-1] += 1
            carry_pos = N-1
            while curr[carry_pos] == B:
                curr[carry_pos] = 0
                carry_pos -= 1
                if carry_pos < 0: break
                curr[carry_pos] += 1
            if carry_pos == -1: new_sid = B**N
            else: new_sid = state_to_sid(curr)
            mat[sid][new_sid] += p
    
    # convert to strings.
    sout = []
    sout.append('dat = {')
    for q in mat:
        scurr = ','
        if len(sout) == 1: scurr = ''
        scurr += '{' + ', '.join(str(x) for x in q) + '}'
        sout.append(scurr)
    sout.append('}')
    sall = '\n'.join(sout) + '\n'

    # dump for mathematica.
    with open('mathdat.dat', 'w') as f:
        f.write(sall)

    return

# build_transition_matrix(4, 4)
build_transition_matrix(5, 4)

and here is the Mathematica code I used to load that result from disk and then solve the system of equations:

ToExpression[ReadString["mathdat.dat"]];
Q = dat[[;; -2, ;; -2]];
Ninv = IdentityMatrix[Length[Q]] - Q;
v = Table[1, {k, 1, Length[Ninv]}];
out = LinearSolve[Ninv, v];
out[[1]]
out[[1]] // N

Answer 2

Calculate the expected number of moves for the lowest digit, starting at 0, to change from 3 to 0.

Calculate the expected number of moves until the second digit changes from 3 to 0. That will be a large number, because the first number has to change from 3 to 0 four times without the 2nd digit changing to 0. That might be a three digit number.

Then the third digit - that will take ages to change from 3 to 0 because it must survive a few hundred moves without being changed back to 0.

The fourth digit will take a massive time. If you simulate it, it’s unlikely to succeed in your lifetime.