Antal försök för att gissa rätt portkod

Hej,
jag blir inte klok på en fundering jag har så jag slänger ut den här.
Säg att du skall knäcka en portkod, så du bruteforcar helt random, gissar ett tal mellan 0 och 9999 och testar tills du gissar rätt, du gissar aldrig på samma tal som du tidigare gjort. Om du gör detta x antal gånger (olika portkoder alltså), hur många gånger i snitt måste gissa för att knäcka varje kod.

Första gången är sannolikheten att inte gissa rätt 9999/10000, andra gången 9998/10000. Sannolikheten att inte gissa rätt på två försök blir alltså (9999/10000)*(9998/10000). Min tanke är att när sannolikheten att inte gissa rätt på x antal försök är 0,5 bör detta x representera antal gissningar i snitt. Hur ligger det till?

Du kan vända på problemställningen och se det som att du alltid gissar på 0000, 0001, 0002, ... ,9999
och låter portkoden vara slumpmässig mellan 0000 och 9999. Då är det lättare att inse att du i medeltal behöver gissa 5000,5 gånger för att hitta den rätta koden.

Glöm inte att varje port har mer än 1 fungerande kod

0000 - 9999 är 10000 st koder, så i medel 5000 försök.

Nä 5000,5 blir det.

Med ditt sätt att räkna så skulle det med 2 koder (0000-0001) bli i medeltal 1 försök, men det blir i medeltal 1,5 försök, eller hur?

Första gången är sannolikheten att inte gissa rätt 9999/10000, men andra gången är den 9998/9999 och inte 9998/10000.

Sannolikheten att gissa rätt efter n antal försök är med andra ord

1- ((10.000-n)!/(10.000-(n-1))!) = 1- ((10.000-n)!/(9.999-n)!)

Du kan lösa detta med induktion.

Antal att det förväntade antalet gissningar som behövs för N koder är E(N).
Då blir E(N) = P(1)*1 + (1-P(1))*(1+E(N-1))
P(1) = sannolikheten att gissa rätt på det första försöket = 1/N

E(N) = 1/N*1 + (1-1/N)*(1+E(N-1))

Vi vet också att E(1) = 1, dvs om det bara finns en kod så tar det 1 försök att "gissa" den.

E(2) = 1/2 + (1-1/2)*(1+1) = 3/2 = (2+1)/2
E(3) = 1/3 + (1-1/3)*(1+3/2) = 1/3+2/3*5/2 = 1/3+5/3 = 2 = 4/2 = (3+1)/2
E(4) = 1/4 + (1-1/4)*(1+4/2) = 1/4+3/4*6/2 = 1/4+9/4 = 10/5 = 5/2 = (4+1)/2

Man frestad att dra slutsatsen att E(N) = (N+1)/2

Antag att det gäller för något N.

E(N+1) = 1/(N+1) + (1-1/(N+1))*(1+E(N)) = 1+(1-1/(N+1))*(N+1)/2 = (2+N/(N+1)*(N+1))/2 = (N+2)/2

Återstår att visa att det gäller för N=1, men vi vet att E(1) = 1 = (1+1)/2 så det gäller för alla N>0

I ditt fall är N=10000 så det förväntade antalet gissningar blir (10000+1)/2 = 5000,5

Med k fungerande koder blir det förväntade antalet försök innan man hittar någon av dem

E(N,k) = (N+1)/(k+1) för alla N>k-1 (1)

Detta kan visas med induktion. E(k,k) = 1 (det går åt ett försök om alla k koderna fungerar)

E(N,k) = k/N*1 + (1-k/N)*(1+E(N-1,k) = 1+(1-k/N)*E(N-1,k)

Antag att (1) gäller för något N.

Då blir E(N+1,k) = 1+(1-k/(N+1))*E(N,k) = 1+(1-k/(N+1))*(N+1)/(k+1) =
= (k+1+N+1-k)/(k+1) = (N+2)/(k+1)

Eftersom (1) gäller för N=k så gäller det därmed för alla N>k-1

Med 10000 möjliga koder varav 4 koder fungerar blir det alltså (10000+1)/(4+1) = 2000.2 försök.

Det räcker med 10003 knapptryckningar om man trycker i rätt ordning. Googla "de Bruijn sekvens"...

Istället för att trycka in 00000001 för att testa "0000" och "0001" så räcker det med "00001"

Förutsatt att inte varje kod måste avslutas med ett "ok" eller "#" eller motsvarande.