Prawdopodobieństwo, że uda się przesłać pakiety

[MrOmega]

Mam problem, który pewnie Wam wyda się banalny, ale jakoś nie mogę sobie z nim poradzić

Chcę policzyć o ile wzrośnie prawdopodobieństwo, że dane nie zostaną utracone przy przesyłaniu przez internet. Powiedzmy, mamy 8 pakietów. Prawdopodobieństwo, że którykolwiek z nich zostanie utracony wynosi p. Czyli wiadomo, prawdopodobieństwo, że wszystkie zostaną dostarczone wynosi (1-p)^{8}.

Teraz zastosuję pewną sztuczkę: mając pakiety A i B stworzę pakiet C, który pozwoli mi odtworzyć A lub B, kiedy jeden z nich zostanie utracony. Ten pakiet C jest dodatkowy. Przykład:
A: 10101
B: 00110
C: 10011 (XOR)

Mam tyle łącza, że wystarczy mi na wysłanie dodatkowych pakietów C dla połowy moich par. Czyli mając 8 pakietów mam 4 pary, więc dla 2 z nich mogę wysłać po dodatkowym pakiecie. Mam teraz 10 pakietów. Jakie jest prawdopodobieństwo, że dane zostaną dostarczone prawidłowo?

====

Dodatkowe wyjaśnienie na przykładzie. Mamy pakiety 1,2,3,4,5,6,7,8. Dla pakietów 1 i 2 tworzymy pakiet A, który może posłużyć do odtworzenia jednego z pakietów w parze, gdy mamy drugi. Dla pakietów 3 i 4 zrobimy to samo. Dla pakietów 5,6,7,8 już nie damy rady więcej przesłać, więc one są bardziej narażone na niebezpieczeństwo.

Więc wysyłamy pakiety 1,2,3,4,5,6,7,8,A,B.

====

Mój tok rozumowania:

Rozważmy parę pakietów, która ma dodatkowy pakiet pozwalający na odtwarzanie pojedynczego zagubionego pakietu: A, B i C. Kiedy nie będziemy mieli A i B jednocześnie? Tylko jeżeli prześle się wyłącznie A lub B lub C. Czyli prawdopodobieństwo przesłania tylko jednego z trzech wynosi

\(\displaystyle{ (1-p) \cdot p^2}\)

Czyli jedziemy odwrotność i dla wszystkich trzech sumując:

\(\displaystyle{ 1 - 3 \cdot \left((1-p) \cdot p^2 \right) = 3p^3 - 3p^2 + 1}\)

Teraz. Załóżmy dla prostoty obliczeń, że przesyłamy tylko parzystą liczbę pakietów. Niech więc \(\displaystyle{ n}\) jest parzyste. Dla połowy par prawdopodobieństwo, że uda się je przesłać wynosi \(\displaystyle{ \left( 3p^3 - 3p^2 + 1\right) ^{n/4}}\). Dla drugiej połowy tylko \(\displaystyle{ ((1-p)^{2})^{n/4}}\).

Więc zadanie sprowadzałoby się do policzenia tego:

\(\displaystyle{ \left( 3p^3 - 3p^2 + 1\right) ^{n/4} \cdot ((1-p)^{2})^{n/4} > ((1-p)^{4})^{n/4}}\)

Czyli po prostu

\(\displaystyle{ (3p^3 - 3p^2 + 1)*(1-p)^2 > (1-p)^4}\)

Co z kolei jest prawdą już bez liczenia tylko przez proste zależności co musi być większe od czego gdy \(\displaystyle{ p > 0}\). Prawda to?

[SlotaWoj]

Wskazane byłoby przeredagowanie treści Twoich rozważań tak, aby nie było wątpliwości nt. problemu, który chcesz rozstrzygnąć.
W szczególności: co to za pakiet C, skoro nie ma dla niego miejsca w paśmie?
Rozważmy parę pakietów, która ma dodatkowy pakiet pozwalający na odtwarzanie pojedynczego zagubionego pakietu: A, B i C. — to zdanie jest niezrozumiałe.
Przecież pakiety A, B i C są pakietami odtworzeniowymi, a nie odtwarzanymi.
Kiedy nie będziemy mieli A i B jednocześnie? — nie rozumiem jakie to ma znaczenie?
Aby dyskusja była możliwa, problem trzeba zdefiniować poprawnie i w sposób zrozumiały.

[MrOmega]

Już tłumaczę. Pasmo jest wykorzystywane w 80%, więc możemy dać 1/4 więcej danych, aby je wypełnić. Dlatego połowa wszystkich par otrzyma po dodatkowym pakiecie (owy C). Czyli będzie 1/4 więcej pakietów.

Pakiet C jest odtworzeniowy, a pakiety A i B odtwarzane. Oryginalnie mamy np pakiet A=1100 i pakiet B=0011. Dla takiej pary utworzony zostanie pakiet C=1111, który posłuży później do odtwarzania A przy pomocy C, gdy zgubimy B lub B przy pomocy C, gdy zgubimy A (wykonując po prostu XORa).

Kwestia tego kiedy nie będziemy mieli A i B jednocześnie jest potrzebna w moim odczuciu do tego, aby prościej policzyć prawdopodobieństwo. Bo prawidłowo przesłane pakiety mamy w sytuacji, gdy:
- mamy A i C (z tego odtworzymy A i B)
- mamy B i C (z tego odtworzymy A i B)
- mamy A i B (mamy już A i B)
- mamy A i B i C (mamy już A i B)

Więc pozostają przypadki, gdy się nie uda przesłanie pakietu (rozważamy na najprostszym przykładzie pary). A nie uda się gdy dostaniemy wyłącznie A lub B lub C. To z kolei ma jakieś prawdopodobieństwo x. Czyli licząc 1 - x dostaniemy prawdopodobieństwo tego, że się uda.

[SlotaWoj]

Dla mnie to zadanie sprowadza się do porównania prawdopodobieństw dwóch zdarzeń:

1. Prawdopodobieństwo przesłania bez strat dwóch niechronionych pakietów z danymi.
   i jest ono równe: \(\displaystyle{ \left(1-p\right)^2}\) .
2. Prawdopodobieństwo przesłania bez strat dwóch pakietów z danymi chronionych trzecim pakietem.
   Będzie tak, gdy wszystkie trzy pakiety zostały przesłane; prawdopodobieństwo: \(\displaystyle{ \left(1-p\right)^3}\) ,
   lub zostanie utracony jedynie pakiet ochronny; prawdopodobieństwo: \(\displaystyle{ p\ \hbox{·}\left(1-p\right)^2}\) ,
   lub zostanie utracony tylko jeden pakiet z danymi; prawdopodobieństwo: \(\displaystyle{ 2p\ \hbox{·}\left(1-p\right)^2}\) .
   Ww. zdarzenia składowe są rozłączne, więc prawdopodobieństwo sumy tych zdarzeń jest równe sumie prawdopodobieństw i wynosi: \(\displaystyle{ 2p^3-3p^2+1}\) .

Każde bardziej złożone zagadnienie można sprowadzić do kombinacji ww. zdarzeń.

Gdy prawdopodobieństwo utraty jednego pakietu jest równe \(\displaystyle{ p=0,1}\) , to prawdopodobieństwo przesłania bez strat dwóch niechronionych pakietów z danymi wynosi \(\displaystyle{ 0,81}\) , a prawdopodobieństwo przesłania bez strat dwóch pakietów z danymi chronionych trzecim pakietem wynosi \(\displaystyle{ 0,972}\) .