Paradoks Bertranda - może mały konkurs?

[Jajcenty 314]

Cześć Wam!

 

Od lat, niejaki Bertrand dręczy mnie, takim oto paradoksem (https://pl.wikipedia.org/wiki/Paradoks_Bertranda). Jakie jest prawdopodobieństwo, że losowa cięciwa okręgu będzie dłuższa od długości boku trójkąta równobocznego wpisanego w tenże okrąg? Bertrand podał trzy różne, na oko prawidłowe, rozwiązania. Osobiście obstawiam wynik 1/3, nawet przeprowadziłem rozumowanie, które tego dowodzi. Postanowiłem zbadać rzecz empirycznie i napisałem program który losuje trochę cięciw i wylicza częstość. I...porażka! Nie mogłem się bardziej mylić.

 

prób 10^9 Bertrand: 0.683362467

 

Uzyskany wynik nie przystaje do żadnego wyniku podanego przez Bertranda (1/3; 1/2; 1/4). Mój wynik to coś w pobliżu 2/3 z kawałkiem Liczba prób nie ma dużego znaczenia:

dla 10^4 Bertrand: 0.6839

 

Celowo nie podaję algorytmu by nie psuć Wam zabawy. Proponuję bowiem konkurs na programik do losowania cięciw i rozstrzygnięcie paradoksu. 

[Gość Astro]

Postanowiłem zbadać rzecz empirycznie i napisałem program który losuje trochę cięciw […] Nie mogłem się bardziej mylić

 

Zapewne "losowałeś" długość z zadanego przedziału. Bertrandowi zapewne chodziło o to, że to również "bes sęsu".

Jeśli wyciągamy te "patyczki", to fundamentalnym pytaniem jest to o zbiór, z którego je wyciągamy (choć oczywiście jest "nieskończony"; nieskończoność ma różne twarze ).

 

Ed.: No i gdyby wziąć 1-0,683… to jesteś blisko.

Edytowane 27 grudnia 2016 przez Astro

[Jajcenty 314]

Zapewne "losowałeś" długość z zadanego przedziału.

Losuję prostą o której wiem, że może być cięciwą i u mnie jest jest ich więcej niż się śniło Bertrandowi. Ale nic to. Jeszcze się nie poddałem

 

 

 

Ed.: No i gdyby wziąć 1-0,683… to jesteś blisko

Tak widzę to Jednak 0,317 to całe kilometry od 0,333 ;D

Edytowane 27 grudnia 2016 przez Jajcenty

[TrzyGrosze 67]

A czy to nie jest czasem quasi paradoks?

Na pytanie: "Jaka jest szansa, że cięciwa będzie dłuższa niż bok trójkąta równobocznego wpisanego w ten okrąg?", Bertrand ustala 3 rodzaje sprzyjających zdarzeń elementarnych i dla każdego rodzaju liczy oddzielnieprawdopodobieństwo.

Przecież na tak postawione pytanie, wszystkie te rodzaje zdarzeń są sprzyjające i powinny być traktowane razem!

[ex nihilo 225]

Tak na szybko:

można chyba wyjść tu z nieskończoności przez "skwantowanie" okręgu, np. co stopień czy radian i obliczenie wszystkich możliwych cięciw rozpiętych pomiędzy tymi punktami. W granicy, czyli przy gęstości punktów = inf., powinno chyba wyjść 1/4.

?

[Gość Astro]

 

 

wszystkie te rodzaje zdarzeń są sprzyjające i powinny być traktowane razem!

 

No to czekamy na ujęcie "formalne".

 

 

 

u mnie jest jest ich więcej niż się śniło Bertrandowi

 

Bertrand nie śnił. Liczył zwyczajnie na czymś więcej niż Ty. Na nieskończonościach.

Ed.: no to liczymy. Pierwsze podejście (nie zasiewam "ziaren"; liczę na dobrego krzemiaka ):

 

void main() {
 int i, j, count=0, min=2*RAND_MAX/3, max=4*RAND_MAX/3;
 int range=100000;
  for (i=0; i<range; i++) {
   j = rand();
   if (j>min && j<=max) count++;
  }
  printf ("Wychodzi: %f \n",(float)count/range);
}

 

Przy jedynie 10⁵ jestem usatysfakcjonowany: 0,33375 daleko od 1/3 nie odbiega.

[pogo 102]

Nie znając opcji rozwiązania tego, to samodzielnie wybrałbym opcję 2 i otrzymał wynik 1/2.

Po przeczytaniu uważam, że nic mi nie pasuje... Moim zdaniem należy losować 2 punkty na okręgu, a to da wynik (prawdopodobnie) 1/3.

 

Czyli algorytm powinien losować 2 punkty w zakresie <0,1) * 2 PI (nie chce mi się szukać symbolu) i liczyć długość cięciwy - nie mam pomysłu jak, zwyczajnie nie chce mi się myśleć.
Jeśli nie wyjdzie z tego coś w okolicach 1/3 to będę zaskoczony.

Problem może polegać na tym, że wciąż nie liczymy na nieskończonym zbiorze opcji.

 

Pomyślmy jednak o tym też w inny sposób: nie da się określić prawdopodobieństwa zdarzenia bez ustalenia warunków brzegowych. Inne masz szanse trafić z łuku do tarczy gdy jest ona ustawiona prostopadle, a inne jak jest pod kątem, a właśnie na tym polega różnica między wersją 1 i 2. Opcję 3 wciąż uważam za bezsensowną.

 

 

Strzelmy opcję 4:
Losujemy punkt wewnątrz koła i losujemy kąt pod jakim pójdzie przez niego cięciwa. Ale będzie zabawa

Albo nie... ten punkt nie musi być wewnątrz. Wylosujmy dowolny punkt w odległości do 3 średnic i z niego strzelajmy. 

 

Zdecydowanie przy zabawach z nieskończonością wypada zacząć się bawić w dodatkowe warunki losowania.

 

 

@

Możesz objaśnić swój kod?

Za licha nie rozumiem co, jak i dlaczego liczy.

[Gość Astro]

 

 

Możesz objaśnić swój kod?

 

Proszę bardzo. Punkt wyjścia:

https://pl.wikipedia.org/wiki/Paradoks_Bertranda#Podej.C5.9Bcie_pierwsze

(pi sobie odpuszczamy, bo jak zbiór zdarzeń sprzyjających razem z omegą pomnożysz sobie/ podzielisz przez pi^z_… to nie ma znaczenia.

 

W ogóle, to się czepiasz. Zmień 2*RAND_MAX/3 na RAND_MAX/3 i 4*RAND_MAX/3 na 2*RAND_MAX/3 i będzie dobrze. Wyniku specjalnie nie zmieni.

Ed.: Nieco poważniej: losujesz liczbę z przedziału od 0 do 1 i pytasz się, jaka część wylosowanych leży w trzeciej części owego zakresu. Trudno spodziewać się czegoś innego niż 1/3.

[pogo 102]

Czyli zwyczajnie liczyłeś dla podejścia 1. Lenistwo.

 

Policzmy dla mojej opcji 4 ale bez ograniczeń:

Przy każdym rzucie losujemy dowolny punkt na płaszczyźnie, a z niego rysujemy losową prostą przecinającą okrąg/koło (co kto woli), czyli zawsze wyjdzie jakaś cięciwa.

Logika mówi, że większość "punktów startowych" będzie bliżej nieskończoności niż kółka, ale przecież nie można mówić o tym, że nieskończoności jest więcej tam niż tu... 

Dowolny algorytm niemal na pewno da wynik dążący do 1/2, ale algebra może dać coś tak absurdalnego jak suma wszystkich liczb naturalnych...

 

Wnioski dzięki rozmowie z bratem, który skończył matmę i wciąż działa w temacie (żyje z udzielania korków)

[Jajcenty 314]

 

 

Moim zdaniem należy losować 2 punkty na okręgu, a to da wynik (prawdopodobnie) 1/3.

Ja losuję 4 double z przedziału 0-1.0 i traktuję jako współrzędne dwóch punktów wyznaczających cięciwę.

W planach mam losowanie jednego punktu i kąta z 0-pi. 

 

 

 

można chyba wyjść tu z nieskończoności przez "skwantowanie" okręgu,

Tak zrobiłem i wyszło mi 1/3, ale widzę że zapomniałem o n-1. znaczy w dyskretnym kole jest n(n-1)/2 cięciw - to trochę zmienia rachunki ;D  

[Gość Astro]

 

 

Czyli zwyczajnie liczyłeś dla podejścia 1. Lenistwo.

 

Cóż. Trochę wcześniej napisałem dość wyraźnie:

 

 

no to liczymy. Pierwsze podejście

 

 

 

Przy każdym rzucie losujemy dowolny punkt na płaszczyźnie, a z niego rysujemy losową prostą przecinającą okrąg/koło (co kto woli), czyli zawsze wyjdzie jakaś cięciwa.

 

Niestety, ale nawet na trzeźwo jestem w stanie ciepnąć poza kołem taki punkt i prostą, która przez kółko nie przejdzie (i cięciwa w d^u_pie… ).

 

 

 

Ja losuję 4 double z przedziału 0-1.0 i traktuję jako współrzędne dwóch punktów wyznaczających cięciwę.

 

Mamy w ten sposób czwartą opcję, obawiam się jednak, że sporo wylosowanych "cięciw" cięciwami nie jest (wylosuj sobie punkt A(0,0.9) i B(0.1,1); ni cholery AB nie chce być cięciwą ).

Ed.: Mogę się Jajcenty oczywiście mylić; jeśli Twoje koło jest kwadratem…

[pogo 102]

Niestety, ale nawet na trzeźwo jestem w stanie ciepnąć poza kołem taki punkt i prostą, która przez kółko nie przejdzie (i cięciwa w d*pie… ).

Celowo i wyraźnie ograniczyłem losowanie prostych do tych, które PRZEJDĄ 

Wiedziałem, że będzie z Tobą ten sam problem co z moim bratem, też zaczął, od tego problemu...

Czyli wszystkie losy gdy nie trafiło w kółko uwalamy jako NIEZAISTNIAŁE! a nawet nie próbujemy ich wykonywać. Wszak interesują nas tylko cięciwy!

 

 

Ed: sądzę, że Jajcentemu chodziło o współrzędne w metryce okrężnej, czy jak ją tam nazwać... czyli zwyczajnie o radiany względem środka okręgu. Czy coś takiego.

[thikim 119]

Tak na razie z grubsza patrząc na problem. Jakkolwiek się nie wysilicie to będziecie musieli robiąc algorytm pójść jedną z tych wskazanych w paradoksie dróg. I musi Wam wyjść rozwiązanie dążące do rozwiązania właściwego dla wybranej drogi.

W ten sposób nic rozstrzygającego nie osiągnięcie bo tworzycie algorytmy w ramach paradoksu.

Edytowane 27 grudnia 2016 przez thikim

[pogo 102]

Moja opcja to który z tych 3 punktów?
Ta ze "strzelaniem" z losowej odległości i kierunku?

[ex nihilo 225]

Chyba trzeci...

[pogo 102]

Nope... moja opcja nie pokrywa się z 3. Nawet się nie zbliża.

[thikim 119]

Oczywiście możecie też próbować wymyślić inne drogi z innymi rozwiązaniami, kwestia kreatywności. Możecie też zrobić błąd w obliczeniach, założeniach, implementacji  - i wyjdzie inaczej

Moim zdaniem jest to rozwiązywalne niejednoznacznie w ramach rozwiązań "geometrycznych".

Jest nieskończenie wiele cięciw które można na takim kole zawiesić. I teraz ilość tych spełniających warunek też jest nieskończona. A proporcje pomiędzy tymi nieskończonościami można wyliczać różne w zależności od przyjętego podziału na zdarzenia elementarne. Każdy z podziałów jest dobry. Każdy wynik jest dobry (no chyba że jak pisałem zrobicie błąd w obliczeniach, założeniach, implementacji).

Edytowane 28 grudnia 2016 przez thikim

[Jajcenty 314]

można chyba wyjść tu z nieskończoności przez "skwantowanie" okręgu, np. co stopień czy radian i obliczenie wszystkich możliwych cięciw rozpiętych pomiędzy tymi punktami. W granicy, czyli przy gęstości punktów = inf., powinno chyba wyjść 1/4.

 

Podejście kwantowe daje mi wynik 1/3. (A jednak )

Dyskretny okręg składa się z punktów ponumerowanych [1,N]. cięciwa między punktami o numerach s i t jest dłuższa od boku trójkąta r. jeżeli  (t-s) > 1/3N i (t-s)< 2/3N (kto nie wierzy ten rysuje) - takich cięciw wychodzących z punktu 1 jest ... 1/3N

Jak widać granica w N->inf nie zależy od N i jest 1/3.

 

Policzmy na palcach wszystkie cięciwy:

 

        private static ulong Count(ulong N)

        {

            ulong hits = 0, _13N = N / 3, _23N = 2 * N / 3, length;

 

            for (ulong s = 1; s <= N; s++)

            {

                for (ulong t = s + 1; t <= N; t++)

                {

                    length = t - s;

                    if (length < _23N && length > _13N) hits++;

                }

            }

            return hits;

        }

 

Wyrażenie p = Count(N)/((N*(N-1)/2); zwraca 0,33333 dla wielu wartości N. Nie radzę tego puszczać dla N > 1e5 - robi nudno.

 

Pozostaje mi wyjaśnić gdzie zmaściłem mój program losowo intuicyjny i zaprojektować parę innych.

 

 

 

Przecież na tak postawione pytanie, wszystkie te rodzaje zdarzeń są sprzyjające i powinny być traktowane razem!

Pierwsza myśl to liczyć średnią, ale wyszło mi bez sęsu

 

 

Każdy z podziałów jest dobry. Każdy wynik jest dobry

Jestem pewien że wniosek z paradoksu B. jest  dokładnie odwrotny: jeśli przyjęty podział jest zły, to uzyskany wynik jest też bardzo... niedobry.

 

 

Mamy w ten sposób czwartą opcję, obawiam się jednak, że sporo wylosowanych "cięciw" cięciwami nie jest (wylosuj sobie punkt A(0,0.9) i B(0.1,1); ni cholery AB nie chce być cięciwą ).

 

Takie przypadki pomijam. Wyróżnik jest ujemny - odpuszczam nie zwiększając licznika prób.

Edytowane 28 grudnia 2016 przez Jajcenty

[Gość Astro]

Wiedziałem, że będzie z Tobą ten sam problem co z moim bratem, też zaczął, od tego problemu...

 

Oj tam. Wynik Twojego algorytmu zdecydowanie zależy od "rozmiaru" pola, z którego losujesz punkty. Jeśli myślisz o "całej" płaszczyźnie (trochę ciężkie w implementacji i niezbyt opłacalne obliczeniowo ), to wynik faktycznie w granicy jest jak w podejściu drugim

http://web.mit.edu/tee/www/bertrand/onehalf.html

czyli 1/2. Stanowi to zresztą najbardziej realistyczne fizycznie podejście

https://en.wikipedia.org/wiki/Bertrand_paradox_(probability)#Physical_experiments

 

sądzę, że Jajcentemu chodziło o współrzędne w metryce okrężnej, czy jak ją tam nazwać... czyli zwyczajnie o radiany względem środka okręgu. Czy coś taki

 

Generalnie nazywa się to układem współrzędnych biegunowych (metryka "klasyczna" ), ale losowanie Jajcentego zdecydowanie temu przeczy.

 

Takie przypadki pomijam. Wyróżnik jest ujemny - odpuszczam nie zwiększając licznika prób.

 

Podeślij (jak można) kod. Lepiej się myśli patrząc na dobry kawałek kodu. Muszę się zastanowić, ale powinieneś chyba z takim losowaniem wbić się w wariant 2, czyli 1/2, ale muszę wziąć jednak klasyczną kartkę i ołówek.

No i spróbowałbym jednak z "metryką okrężną" ( ). Losujesz dwa punkty (r,alfa), gdzie r<=1, alfa <=2π. Odcinek je łączący zawsze leży na średnicy (o ile A nie jest równe B ).

Edytowane 28 grudnia 2016 przez Astro

[thikim 119]

Jestem pewien że wniosek z paradoksu B. jest dokładnie odwrotny: jeśli przyjęty podział jest zły, to uzyskany wynik jest też bardzo... niedobry.

Paradoks polega na tym że nie ma złego podziału. Każdy z podziałów jest dobry. A dokładniej każdy z podziałów liczy coś innego. Dopóki nie określisz co chcesz policzyć to każdy wynik jest równie prawidłowy.

Trochę tak jak w zadaniu:

Ala i Ola mają razem 40 lat. Ile lat ma Ala a ile Ola?

Przyjmując dany algorytm liczenia niejawnie wybierasz któryś ze sposobów określenia zbioru elementów prawdopodobieństwa. Ale możesz tak naprawdę wybrać inny.

Trochę tak jakbyś przyjął że Ala ma 20 to z obliczeń wyjdzie Ci że i Ola ma 20 Ale dopóki nie założysz sobie jednej wersji to może być i: Ala 10, Ola 30.

Edytowane 28 grudnia 2016 przez thikim

[Gość Astro]

 

 

Przyjmując dany algorytm liczenia niejawnie wybierasz któryś ze sposobów określenia zbioru elementów prawdopodobieństwa. Ale możesz tak naprawdę wybrać inny.

 

Zgadza się:

 

 

Jeśli wyciągamy te "patyczki", to fundamentalnym pytaniem jest to o zbiór, z którego je wyciągamy (choć oczywiście jest "nieskończony"; nieskończoność ma różne twarze ).

[Jajcenty 314]

Podeślij (jak można) kod. Lepiej się myśli patrząc na dobry kawałek kodu. Muszę się zastanowić, ale powinieneś chyba z takim losowaniem wbić się w wariant 2, czyli 1/2, ale muszę wziąć jednak klasyczną kartkę i ołówek.

 

wylosowana prosta jest postaci y =_ax +_b; poniższe próbuje znaleźć długość cięciwy. rootofthree = sqrt(3)

 

public int Bertrand()

        {

            double a2 = _a * _a;

            double b2 = _b * _b;

            double minusB = -(2 * _a * _b);

            double twoA = 2 * (a2 + 1);

 

            double delta = 4 * (a2 - b2 + 1);

 

            if (delta < 0)  return -1;

            if (delta == 0) return 0;

 

 

            double x1 = (minusB - Math.Sqrt(delta)) / twoA;

            double x2 = (minusB + Math.Sqrt(delta)) / twoA;

            double y1 = _a * x1 + _b;

            double y2 = _a * x2 + _b;

 

            double len = SegmentLength(x1, y1, x2, y2);

            if ( len > rootofthree) return 1;

 

            return 0;

        }

 

 

i główna pętla:

static double Test()

        {

            Circle c = new Circle();

            long counter = 0;

            int result = 0, success = 0;

 

            do

            {

                result = c.Bertrand(2 * generator.NextDouble() - 1.0d, 2 * generator.NextDouble() - 1.0d,

                                    2 * generator.NextDouble() - 1.0d, 2 * generator.NextDouble() - 1.0d);

 

                if (result >= 0 )

                {

                    if (result > 0) success++;

                    counter++;

                }

                

            } while (counter < repetitions);

 

            return (double)success/ counter;

        }

 

 

A dokładniej każdy z podziałów liczy coś innego. Dopóki nie określisz co chcesz policzyć to każdy wynik jest równie prawidłowy.

Chcę policzyć prawdopodobieństwo że losowo wybrana cięciwa okręgu będzie dłuższa od boku trójkąta równobocznego wpisanego w ten okrąg. Bardzo precyzyjnie postawione zadanie, mające bardzo precyzyjne rozwiązanie w postaci: licznośćsukcesów/licznośćomega. Nie wiem dokładnie co złego jest w rozwiązaniach Bertranda. Podejście drugie i trzecie losują punkt, czyli pęk cięciw, a Bertrand z tego pęku arbitralnie wybiera jedną, fajną, dłuższą od boku trójkąta. Wydaje mi się to podejrzane. 

Edytowane 28 grudnia 2016 przez Jajcenty

[Gość Astro]

 

 

wylosowana prosta jest postaci y =_ax +_b

 

Wierz mi. Prostą można wylosować na wiele sposobów. Ty losujesz 2 punkty i wyznaczasz równanie prostej przez nie przechodzącej. Mogę zaproponować parę innych wariantów, które dadzą nieco inne prawdopodobieństwo.

 

 

 

poniższe próbuje znaleźć długość cięciwy.

 

Po analizie (wybacz, ale mało czytelne ) wyznaczasz długość cięciwy (o ile jest cięciwą) jako odcinka prostej a*x+b tnącej okrąg x²+y²=1. Okrąg wpisany jest w kwadrat [-1,1]x[-1,1], punkty losujesz zaś z kwadratu [0,1]x[0,1]. Może to bez znaczenia, ale metodologicznie kompletnie mi się nie podoba. Z pętli głównej wynika jednak, że wcześniej kłamałeś i losujesz punkty z kwadratu [-1,1]x[-1,1].

Czytanie kodów dobre jest jak chleb…

Jak znajdę czas, to zrobię może coś dla nauki i wezmę jednak kartkę z ołówkiem (w tym samym czasie, jeśli masz czas, zapodaj pomysł z losowaniem punktów w układzie biegunowym (drobnostka)).

 

 

Wydaje mi się to podejrzane.

 

No i słusznie, bo nie ma jednego, danego przez Boga sposobu ujęcia problemu.

[Jajcenty 314]

 

 

Z pętli głównej wynika jednak, że wcześniej kłamałeś i losujesz punkty z kwadratu [-1,1]x[-1,1].

Oj.  Według dokumentacji: 

Random.NextDouble() Returns a random floating-point number that is greater than or equal to 0.0, and less than 1.0.

Ja to se tylko przeskalowałem do wygodniejszego środka układu. Elementarne. Nie kłamałem.

 

 

 

zapodaj pomysł z losowaniem punktów w układzie biegunowym (drobnostka)).

Układ biegunowy zostawiam sobie na koniec. Teraz w planie mam losowanie dwóch kątów z [0, Pi] i znalezienie błędu w pierwszym podejściu

 

 

No i słusznie, bo nie ma jednego, danego przez Boga sposobu ujęcia problemu

Oczywiście, jednak paradoks kładzie teorię. Wyjątek też kładzie teorię.

[Gość Astro]

 

 

Random.NextDouble() Returns a random floating-point number that is greater than or equal to 0.0, and less than 1.0. Ja to se tylko przeskalowałem do wygodniejszego środka układu. Elementarne. Nie kłamałem.

 

A jednak. 2*[0,1)-1 = [-1,1). Twierdziłeś wcześniej coś innego:

 

 

losuję 4 double z przedziału 0-1.0

Jeśli losuję Y równe 42*NextDouble(), to nie losuję liczby z przedziału [0,1); to chyba dość proste. Tak naprawdę wiesz co robi NextDouble?

 

 

 

Układ biegunowy zostawiam sobie na koniec.

 

Polecam od zaraz. Transformacja jest trywialna, czyli x=r*cos(alfa), y=r*sin(alfa). Można dość prosto jako inline (pewnie zrobiłbym makro ).

 

 

 

Teraz w planie mam losowanie dwóch kątów z [0, Pi]

 

Ciekawe… Cóż te kąty reprezentują tak bardziej "fizycznie"?

 

 

 

Oczywiście, jednak paradoks kładzie teorię. Wyjątek też kładzie teorię.

 

Oczywiście.