Jump to content
Forum Kopalni Wiedzy
Jajcenty

Paradoks Bertranda - może mały konkurs?

Recommended Posts

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 :D 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. 

Share this post


Link to post
Share on other sites
Guest 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. ;)

Edited by Astro

Share this post


Link to post
Share on other sites
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 :D

 

 

 

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

Edited by Jajcenty

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites

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.


?

Share this post


Link to post
Share on other sites
Guest 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. ;):D


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 105 jestem usatysfakcjonowany: 0,33375 daleko od 1/3 nie odbiega. ;):D

Share this post


Link to post
Share on other sites

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 :D

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.

Share this post


Link to post
Share on other sites
Guest 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 piz:) 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. ;):D


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. :D

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites

 

 

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  

Share this post


Link to post
Share on other sites
Guest 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 dupie;)).

 

 

 

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… ;)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Edited by thikim

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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 :D

Moim zdaniem jest to rozwiązywalne niejednoznacznie :D 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).

Edited by thikim

Share this post


Link to post
Share on other sites
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 :D
 

 

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.
Edited by Jajcenty

Share this post


Link to post
Share on other sites
Guest 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 ;):D), 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" :D), 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 ;)).

Edited by Astro

Share this post


Link to post
Share on other sites
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.

Edited by thikim

Share this post


Link to post
Share on other sites
Guest 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 ;)).

Share this post


Link to post
Share on other sites
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. 

Edited by Jajcenty

Share this post


Link to post
Share on other sites
Guest 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 x2+y2=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. :D

Share this post


Link to post
Share on other sites

 

 

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ę.

Share this post


Link to post
Share on other sites
Guest 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. :P 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. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...