zagadnienie ze statystyki

Mamy losowy ciąg w postaci kluczy, np. o rozmiarze: n = 10 albo 100 tys. - typowy słownik.

Pytanie: jaka jest najbardziej prawdopodobna najdłuższa już 'posortowana' seria - podciąg w takim ciągu = seria?

Posortowana seria znaczy tyle, że kolejne klucze rosną w ramach tej serii, np. taki przykład:
abba < baba < cudo < igła < kra < rasa < rosa;
długość serii = 7;

Albo inaczej: jak długi ciąg (losowy) musi być, aby zawierać w sobie serię o długości k (z prawdop. 50%)?

len_max_seria(n) = k;

Do testowania można wykorzystać prosty random, który generuje ciągi liczb o rozkładzie liniowym.
Wystarczy random 32 bitowy.

Generujemy ciąg n liczb, np. n = milion, i sprawdzamy jaką najdłuższą serię zawiera: k.

Tak czysto naiwnie dla losowego ciągu szansa że para kluczy jest w dobrej kolejności to 50%, bo albo są dobrze albo nie są. To oznacza że szansa że k elementów będzie w dobrej kolejności to (1/2)^k.
Mam wątpliwości czy da się tutaj określić długość ciągu dla której własność ma 50% szans na zajście, chyba że zakładamy że generujemy wszystkie możliwe ułożenia w tym naszym ciągu. Wtedy oczywiście mamy n! możliwości z których co (1/2)^k spełnia własność.

Shalom napisał(a):

Tak czysto naiwnie dla losowego ciągu szansa że para kluczy jest w dobrej kolejności to 50%, bo albo są dobrze albo nie są. To oznacza że szansa że k elementów będzie w dobrej kolejności to (1/2)^k.

Może i dość dobrze wyjdzie (przynajmniej tak z grubsza) ale musisz to chyba jeszcze pomnożyć... przez liczbę prób, nie?

Mam wątpliwości czy da się tutaj określić długość ciągu dla której własność ma 50% szans na zajście, chyba że zakładamy że generujemy wszystkie możliwe ułożenia w tym naszym ciągu. Wtedy oczywiście mamy n! możliwości z których co (1/2)^k spełnia własność.

Inny problemik - dość podobny, ale chyba troszkę łatwiejszy:
ile razy (n) musimy rzucić monetą, aby uzyskać serię orłów długości k?

Może podpowiem że dla serii 8 orłów, trzeba rzucić tylko/aż 510 razy (statystycznie).

wil napisał(a):

Inny problemik - dość podobny, ale chyba troszkę łatwiejszy:
ile razy (n) musimy rzucić monetą, aby uzyskać serię orłów długości k?

Może podpowiem że dla serii 8 orłów, trzeba rzucić tylko/aż 510 razy (statystycznie).

Brakuje mi tu jednej zmiennej. Z jakim prawdopodobieństwem chcesz uzyskać tą serię k orłów? Przy n=510 i k = 8 jakie prawdopodobienstwo uzyskania tej seri orłów założyłeś?

Być może chodziło Ci o to jakie ma być n, by wartośc oczekiwana najdłuższej serii orłów przy n rzutach wynosiła k?
Albo jaka jest wartość oczekiwana n gdy w ciągu pojawia się sieria orłów o długości k. Przy tak sformułowanym problemie wychodzi 2^(k+1)-2.

nalik napisał(a):

wil napisał(a):

Inny problemik - dość podobny, ale chyba troszkę łatwiejszy:
ile razy (n) musimy rzucić monetą, aby uzyskać serię orłów długości k?

Może podpowiem że dla serii 8 orłów, trzeba rzucić tylko/aż 510 razy (statystycznie).

Brakuje mi tu jednej zmiennej. Z jakim prawdopodobieństwem chcesz uzyskać tą serię k orłów? Przy n=510 i k = 8 jakie prawdopodobienstwo uzyskania tej seri orłów założyłeś?

Nie ma tu prawdopodobieństwa, bowiem wartość średnia to... średnia - z prawdopodobieństwem 1... zgodnie z tw. centralnym Kołmogorowa.

Średnia długość ciągu (rzutów) dla uzyskania serii sukcesów o długości k:
n = (1-p^k)/(1-p) * 1/p^k
gdzie: p = prawdopodobieństwo sukcesu w jednym losowaniu, zatem dla rzutu monetą masz: p = 1/2,
a stąd:
n = (1-1/2^k)/(1-1/2) * 2^k;

co dla serii długości k = 8 daje: n = (1-1/256)/0.5 * 256 = 510

Sprawdź to sobie praktycznie, znaczy rzucaj monetą aż do uzyskania serii 8 orłów,
rób tak np. ze 100 razy, a potem wylicz z tego średnią.

Albo jaka jest wartość oczekiwana n gdy w ciągu pojawia się sieria orłów o długości k. Przy tak sformułowanym problemie wychodzi 2^(k+1)-2.

To jest to samo, ale tylko dla p = 1/2.

Zadanie było nieco inne:
losujemy n sztuk liczb losowych, np. z przedziału 0-1.0, i teraz pytanie:
jak długa będzie najdłuższa seria w tym ciągu?

a(i) < a(i+1) < ... < a(i+k);
k(n) = ?
albo odwrotnie: n(k) = ?, czyli średnia liczba prób n dla serii k...

wil napisał(a):

Zadanie było nieco inne:
losujemy n sztuk liczb losowych, np. z przedziału 0-1.0, i teraz pytanie:
jak długa będzie najdłuższa seria w tym ciągu?

a(i) < a(i+1) < ... < a(i+k);
k(n) = ?
albo odwrotnie: n(k) = ?, czyli średnia liczba prób n dla serii k...

Zastanawiałem się nad tym licząc wartość oczekiwaną ze wszystkich możliwych k, ale mi wyszło dziwne równanie:
Wartość oczekiwana K:
K = Sum[k * Pr(k) for k from 0 to n]
Pr(k) = Pr[w ciagu o dlugsci n istnieje rosnąca sekwencja o dlugosci k]
Pr(k) = Sum[Binominal(n,k*j) for j from 1 to n/k]) * Product[n-j*k+2 for j from 1 to n/k] / n!

Chyba się gdzieś pomyliłem. Pytanie czy wszystkie wyrazy w ciągu są unikalne. Założyłem, że są. Dlatego podzieliłem przez n!, jako, że n elementów można ustawić na n! sposbów.
Sum[Binominal(n,k^j) for j from 1 to n/k]) to na ile sposbów mogę ze zbioru n liczb wybrać k*j liczb ... i tu już widzę swój błąd bo jeszcze z tego powiniene wybrać po j par k elementowych ...
Product[n-j^k+2 for j from 1 to n/k] to na ile sposóbw mogę ułożyć j rosnących sekwencji k elementowych, zakladajac ze inne liczby musza maleć.

wil napisał(a):

nalik napisał(a):

wil napisał(a):

Inny problemik - dość podobny, ale chyba troszkę łatwiejszy:
ile razy (n) musimy rzucić monetą, aby uzyskać serię orłów długości k?

Może podpowiem że dla serii 8 orłów, trzeba rzucić tylko/aż 510 razy (statystycznie).

Brakuje mi tu jednej zmiennej. Z jakim prawdopodobieństwem chcesz uzyskać tą serię k orłów? Przy n=510 i k = 8 jakie prawdopodobienstwo uzyskania tej seri orłów założyłeś?

Nie ma tu prawdopodobieństwa, bowiem wartość średnia to... średnia - z prawdopodobieństwem 1... zgodnie z tw. centralnym Kołmogorowa.

Tyle, że to pytanie nie wspomina o średniej. Domyśliłem się o co Ci chodzi, ale nie napisałeś tego jasno. Bo 100% pewności, że wypadnie k orłów przy n rzutach nigdy mieć nie będziesz z definicji.

nalik napisał(a):

Zastanawiaem się nad liczac wartość oczekiwaną ze wszystkich możliwych k, ale mi wyszło dziwne równanie:
Wartość oczekiwana K:
K = Sum[k * Pr(k) for k from 0 to n]
Pr(k) = Pr[w ciagu o dlugsci n istnieje rosnąca sekwencja o dlugosci k]
Pr(k) = Sum[Binominal(n,k*j) for j from 1 to n/k]) * Product[n-j*k+2 for j from 1 to n/k]

Chyba się gdzieś pomyliłem. Pytanie czy wszystkie wyrazy w ciągu są unikalne. Założyłem, że są.

Może wylicz to do końca jak należy, a potem jeszcze sprawdź... za pomocą generatora losowych.

Pewnie wyjdzie to coś zbliżonego do tych serii z rzutu monetą,
czyli na milion prób powinna być seria do 19, a i wiele krótszych: 18, 16... 10 - pewnie z kilkadziesiąt sztuk.

Tyle, że to pytanie nie wspomina o średniej. Domyśliłem się o co Ci chodzi, ale nie napisałeś tego jasno. Bo 100% pewności, że wypadnie k orłów przy n rzutach nigdy mieć nie będziesz z definicji.

Wiadomo że średnia, w ramach jednej serii, ma zawsze 50% szans - stąd też słówko: 'średnia' a nie 'pewna'. :)

Tu jednak znacznie gorzej wychodzi od tych serii Bernoulliego;
chyba dwa razy gorzej około, czyli długość ciągu (losowego) musi być długości n^2.

Np. dla otrzymania serii 'progresywnej' o długości 8 potrzeba aż z 256 tysięcy losowań!, co jest porównywalne właśnie z: 510^2 = 260 tys.

n =~ 2^(2k+2); co dla k = 8 daje: 2^18, czyli coś w pobliżu 260 tysi.