Paradoks Bertranda - może mały konkurs?

[Jajcenty 314]

Polecam od zaraz. Transformacja jest trywialna, czyli x=r*cos(alfa), y=r*sin(alfa).

To jaka jest wartość dodana skoro natychmiast wracamy do prostokątnego?  A z losowania [0,2PI] jest taki zysk że obliczenia są prostsze:

 

        private static bool IsLongerThanSide(double ang1, double ang2)

        {

            ang1 = Math.Abs(ang1 - ang2);

            if (ang1 > PI)

                ang1 -= PI;

 

            return (ang1 > PIby3);

        }

 

edit: To dopiero pomysł. Jeszcze nie sprawdziłem poprawności.

Edytowane 28 grudnia 2016 przez Jajcenty

[Gość Astro]

 

 

To jaka jest wartość dodana skoro natychmiast wracamy do prostokątnego?

 

Taka, że zmieniasz sposób losowania, a w kodzie dużo grzebać nie musisz.

 

 

 

To dopiero pomysł. Jeszcze nie sprawdziłem poprawności.

 

Fajne; gdybym jeszcze wiedział cóż oznacza Plby3 i po kiego Ci zwracana zerojedynkowa wartość relacji, to byłoby fajnie.

 

 

return (ang1 > PIby3);

Czy przypadkiem nie chcesz losować punktów na okręgu?

[thikim 117]

 

 

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

Ano się zgadza

Czy Jajcenty dostrzegł już różne twarze?

[Jajcenty 314]

Fajne; gdybym jeszcze wiedział cóż oznacza Plby3 i po kiego Ci zwracana zerojedynkowa wartość relacji, to byłoby fajnie.

a)PI/3

b)bo w ciele głównej pętli będę mógł elegancko napisać: if(IsLongerThanSide(a1,a2)) hits++;  co będzie bardziej czytelne dla purystów. Sam ja wyrobnik, w przypływie szaleństwa oszczędności, na swoje cele napisałem: 

 

        private static byte IsLongerThanSide(double ang1, double ang2)

        {

            ang1 = Math.Abs(ang1 - ang2);

            if (ang1 > PI) ang1 -= PI;

            if (ang1 > PIby3) return 1;

            return 0;

        }

 

By potem w pętli użyć ciasnego: hits+=IsLongerThanSide(double ang1, double ang2); 

Będziemy gadać o moim stylu programowania, albo co gorsza przystosowywać go tak by zyskał Twoją akceptację? 

 

 

Czy Jajcenty dostrzegł już różne twarze?

Niestety nie. Normalnie jak ślusarz do puzonisty: panie!, ja jestem ślusarz, to się musi dać wyjąć.i tego się będę trzymał.

Co ciekawe moje próby losowe nie zbliżają się dają żadnego z rozwiązań Bertranda. Ostatnia próba z kątami daje: 0,5555 - zmusza mnie to do myślenia nad sposobami weryfikacji algorytmów

 

edit:

Oto ostatnia wersja, Wynik 0.555559484 dla 1e9 prób

    class Program

    {

        const double PI = Math.PI;

        const double TwoPI = Math.PI * 2;

        const double PIby3 = Math.PI / 3;

 

        static void Main(string[] args)

        {

            ulong howManyTimes = ulong.Parse(args[0]);

            ulong hits = DoRun(howManyTimes);

            Console.WriteLine(hits);

            Console.ReadLine();

        }

 

        private static ulong DoRun(ulong howManyTimes)

        {

            double ang1, ang2;

            ulong hits = 0;

 

            Random rndm = new Random(DateTime.Now.Millisecond);

 

            do

            {

                ang1 = TwoPI * rndm.NextDouble();

                ang2 = TwoPI * rndm.NextDouble();

                hits += IsLongerThanSide(ang1, ang2);

            } while (--howManyTimes > 0);

 

            return hits;

            

        }

 

        private static byte IsLongerThanSide(double ang1, double ang2)

        {

            ang1 = Math.Abs(ang1 - ang2);

            if (ang1 > PI) ang1 -= PI;

            if (ang1 > PIby3) return 1;

            return 0;

        }

    }

 

Edytowane 28 grudnia 2016 przez Jajcenty

[pogo 102]

Coś mi nie pasuje w Twoim kodzie...

 

Losujesz 2 liczby będące odległością po okręgu od jakiegoś punktu 0.

Liczysz odległość miedzy nimi po obwodzie.

Jeśli jest większe od PI, to odejmujesz PI - tego nie rozumiem, bo na pewno w ten sposób nie liczysz długości po krótszym łuku tylko jakieś cholera wie co...

Sprawdzasz czy wynik jest dłuższy od 1/3 PI, czyli od 1/6 okręgu - tego też nie rozumiem, po co Ci 1/6 okręgu?

 

Raczej powinieneś zrobić tak:

private static byte IsLongerThanSide(double ang1, double ang2)
{
    ang1 = Math.Abs(ang1 - ang2);
    if (ang1 > PI*2/3 && ang1 < PI*4/3) return 1;
    return 0;
}

Ale to nie wymaga nawet uruchamiania, bo od razu widać, że co trzecie trafienie będzie celne.

[Gość Astro]

 

 

Oto ostatnia wersja, Wynik 0.555559484 dla 1e9 prób

 

Wynik 5/9 (0,5555…) nieco mnie dziwi, bo poprawnie powinno wyjść 2/3 (0,6666…) przy tym, co masz na myśli. Proponuję, byś zamienił

 

 

if (ang1 > PI) ang1 -= PI;

na poprawne  if (ang1 > PI) ang1 = TwoPi - ang1;

(zadowolisz nie tyle moje oczekiwania stylu programowania, co oczekiwania stylu myślenia ).

 

Oczywiście, niewiele to ma wspólnego z losowaniem dwóch punktów w układzie biegunowym.

Oczywiście, jak magicznie podzielimy to wszystko przez TWO, to wiesz co.

[Jajcenty 314]

na poprawne  if (ang1 > PI) ang1 = TwoPi - ang1;

A rwał nać. Dzięki. 

 

 

Jeśli jest większe od PI, to odejmujesz PI - tego nie rozumiem, bo na pewno w ten sposób nie liczysz długości po krótszym łuku tylko jakieś cholera wie co... Sprawdzasz czy wynik jest dłuższy od 1/3 PI, czyli od 1/6 okręgu - tego też nie rozumiem, po co Ci 1/6 okręgu?

 

Losuję dwa kąty z przedziału 0-2Pi radianów. Różnica tych kątów to kąt środkowy... i kupa... dzięki.  Właśnie zrozumiałem - pomyliłem kąt środkowy z wierzchołkiem trójkąta. Robiłem poprawkę o PI żeby dostać kąt ostry. Ach, te radiany.

No nic, trzeba będzie jeszcze nad tym popracować. 

 

EDIT:

 

Uff, Wszechświat wrócił na swoje miejsce. 0.333346200 (1e9 prób) Lubię ten wynik.

 

Losuję dwa kąty względem osi X. Jeżeli ostry kąt środkowy między nimi jest większy od 2/3PI to mamy sukces - Cięciwa jest dłuższa. Jeśli wychodzi rozwarty to odejmujemy od 2PI (credits goes to Astro) i znowu mamy ostry.

 

 

ang1 < PI*4/3

hm, a dlaczego?

 

private static byte IsLongerThanSide(double ang1, double ang2)

        {

            ang1 = Math.Abs(ang1 - ang2);

            if (ang1 > PI) ang1 = TwoPI - ang1;

            if (ang1 > PI*2/3) return 1;

            return 0;

        }

Edytowane 28 grudnia 2016 przez Jajcenty

[pogo 102]

Po przekroczeniu PI zaczyna nam maleć cięciwa. 4/3 PI to akurat lustrzany punkt do 2/3 PI. Pomiędzy 2/3 i 4/3 masz akurat cięciwę dłuższą od boku trójkąta.

[Gość Astro]

 

 

Jeśli wychodzi rozwarty to odejmujemy od 2PI (credits goes to Astro) i znowu mamy ostry.

 

Niekoniecznie rozwarty i niekoniecznie ostry.

Raczej wklęsły i wypukły.

[Jajcenty 314]

 

 

Niekoniecznie rozwarty i niekoniecznie ostry. Raczej wklęsły i wypukły.

O to to to! Z ust mnie wyjąłeś.

Skończył mi się czas na zabawę, więc jeszcze tylko - specjalnie dla Astro - wersja w układzie współrzędnych biegunowych. Okrąg o promieniu 1 ze środkiem w biegunie czyli phi=1; Losuję dwa punkty na okręgu.

        private static ulong RunEvenFaster(ulong howManyTimes)

        {

            double ang;

            ulong hits = 0;

            Random rndm = new Random(DateTime.Now.Millisecond);

            do

            {

                ang = Math.Abs(TwoPI * rndm.NextDouble() - TwoPI * rndm.NextDouble());

                hits += (ang > PI23 && ang < PI43) ? 1UL : 0UL;

            } while (--howManyTimes > 0);

            return hits;

        }

 

Wykorzystałem Twój pomysł na inline oraz pomysł Pogo na ifa bez robienia wypukłego z wklęsłego. Urwaliście jakieś 15% czasu wykonania. Pogo urwał 10

Na pewno jeszcze  spróbuje wyjaśnić problem z pierwszym podejściem, które dało dwie trzecie z okładem, ale to już na Wielkanoc. 

Aha, no i jeszcze: A jednak 1/3!

[pogo 102]

Możesz skrócić czas wykonania jeszcze odrobinę jak całkowicie pozbędziesz się PI. Zwyczajnie zapomnij o tym, że musisz znać promień (bo nie musisz, wcale go nie używasz) i zrób okrąg o obwodzie 1.

Nagle zrobi się:

ang = Math.Abs(rndm.NextDouble() - rndm.NextDouble());
hits += (ang > 1/3 && ang < 2/3) ? 1UL : 0UL;

Dla dalszej optymalizacji możesz wartości 1/3 i 2/3 zamknąć w zmiennych.

 

Oczywiście możemy iść jeszcze dalej: po co losować 2 punkty, skoro można wylosować tylko długość odcinka? Ostatecznie to daje to samo. Czyli już jest: ang = rndm.NextDouble();
No i jaki jest sens sprawdzać 2 warunki? I tak to jest 1/3 obwodu, więc od razu: (ang < 1/3) ? 1UL : 0UL;

 

 

Zrobiłem się już bezczelny...

Edytowane 29 grudnia 2016 przez pogo

[Jajcenty 314]

Możesz skrócić czas wykonania jeszcze odrobinę jak całkowicie pozbędziesz się PI.

No nie, chcę mieć elewację od 0 do 2PI. Twój sposób losuje tylko pół okręgu. Wyniku to nie zmieni, ale zarzutów o nie przemiatanie omegi nie odeprę. 

 

Pomyślałem, że wrócę do losowania dwóch punktów (prostej) i połączę to z liczeniem PI z Igły Buffona - to powinno dać pogląd na jakość losowania. 

Edytowane 29 grudnia 2016 przez Jajcenty

[pogo 102]

Zrób inaczej:

Losuj 2 punkty, ale jeden wewnątrz okręgu, a drugi na zewnątrz, w zakresie ile tylko pozwoli double, czyli niemal dowolnie daleko.

Poprowadź prosta przez oba punkty i policz długość tak utworzonej cięciwy.

Bardziej przypadkowego rysowania cięciw nie dam rady wymyślić, a jednocześnie zapewni, że każda powstała prosta będzie zawierała cięciwę tego okręgu. A wynik powinien być w okolicach 1/2, odrobinę poniżej.

[Afordancja 57]

Tak na chłopski rozum sprawa jest trywialna

(patrząc na sposób pierwszy i drugi)

 

w obydwu sposobach chodziło o zakolorowanie kółka(tak aby "kreski" nie miały punktów wspólnych wewnątrz okręgu), tylko zrobiono to różnymi długościami kresek. raz kolorowano więcej kreskami krótszymi, a raz generalnie dłuższymi

 

Dobrze myślę?

[Gość Astro]

Można pomyśleć też o różnych grubościach kresek, by w ich kolory nie wchodzić.

 

Jajcenty, żeby nie było tak łatwo

Aha, no i jeszcze: A jednak 1/3!

to pójdźmy w przypadek drugi. Okrąg jak wcześniej, a prosta o równaniu y=b (b oczywiście od -1 do 1). Prosta wycina cięciwę o długości 2*sqrt(1-b*b). Rozważmy teraz dwa sposoby losowania:

1. losowanie "wprost" b z przedziału (-1,1), co da śliczniutkie 1/2;
2. losowanie kąta alfa z przedziału (-π/2,π/2), gdzie alfa oznacza współrzędną punktu przecięcia prostej i okręgu (w I lub IV ćwiartce oczywiście ). Wówczas wychodzi śliczniutkie 1/3.

Edycja (po pewnym czasie).

Pomyślałem, że może (by nie przeciążać komputerów) jakieś wyjaśnienie analityczne? Spróbuję zatem, choć mały kodzik jest, ale nie piszę tak ładnie jak Jajcenty (bo zdecydowanie w sposób bardziej "skompresowany" ), więc się nie pochwalę.

 

Losujemy zatem prostą y = b, gdzie b jest od -1 do 1. Załóżmy, że losujemy liczbę rzeczywistą, a nasz generator jest dobry, czyli rozkład pdp naszej zmiennej b jest stały. Oczywiście f₁(b) = 1/2, coby całka rozkładu po Ω (od -1 do 1) dawała pewność, czyli 1. Łatwo chyba dojdziemy, że nasze zdarzenie odpowiada zakresowi b od -1/2 do 1/2, bo cięciwa (2.*sqrt(1.-b*b) dla takich b równa jest pierwiastkowi z 3). Nasze prawdopodobieństwo to zatem całeczka z f₁ po odcinku (-1/2,1/2). Wychodzi nic innego jak 1/2.

Teraz losujemy α (z przedziału od -π/2 do π/2). Znów, rozkład zmiennej α jest stały, f₂(α)=1/π (ponownie normalizacja). Ponieważ b = sin(α), to b=1/2 odpowiada α = π/6. Przy takim losowaniu interesujące nas prawdopodobieństwo to całeczka z f₂ po (-π/6,π/6), czyli dokładnie 1/3.

 

Podsumowując: różne sposoby losowania – różne twarze nieskończoności.

 

P.S. Droga KW, kiedy wreszcie LaTeX?

Edytowane 29 grudnia 2016 przez Astro

[Jajcenty 314]

 

 

Bardziej przypadkowego rysowania cięciw nie dam rady wymyślić, a jednocześnie zapewni, że każda powstała prosta będzie zawierała cięciwę tego okręgu. A wynik powinien być w okolicach 1/2, odrobinę poniżej.

No to mózg mi się zlasował. Warunki: kólko x² + y² = 1, losuję 4 punkty z kwadratu o boku czyli: "s = 2 * bok * Rndm.NextDouble() - bok;" losuję tak długo aż uzyskam 1e6 cięciw - przypadki styczne i bezsieczne pomijam.

Wyniki (bok kwadratu, częstość)

1 - 0,683684

2 - 0,54534

4 - 0,511776

8 - 0,503993

16 - 0,500221

32 - 0,499648

64 - 0,499362

128 - 0,500667

256 - 0,499757

512 - 0,499449

1024 - 0,500055

[Gość Astro]

Jest bardzo dobrze. W granicy powinno być dokładnie 1/2.

Poważniej, to podziel sobie sobie π przez 4 (czyli pole koła przez pole kwadratu, w które owo koło wpisaliśmy). Daje jakieś 0,785. Całkiem podobne do 0,684.

Pogo raczej niedoszacował wyniku.

Ed.: ups, chyba niezbyt zrozumiałem:

losuję 4 punkty z kwadratu o boku czyli: "s = 2 * bok *

Policz w takim razie dla boku równego dokładnie średnicy okręgu.

 

Ed.: nie jestem pewien, czy musi to być π/4, ale zdecydowanie powinno być większe od 1/2. Jak znajdę czas, to przemyślę (podsyłając eleganckie analityczne rozwiązanie ).

Ed2.: No dobra. O ile rozkład różnicy zmiennych losowych, czy iloraz różnic nie jest jeszcze kłopotem (mówimy jedynie o rozkładzie współczynnika kierunkowego prostej )

https://en.wikipedia.org/wiki/Ratio_distribution#Uniform_ratio_distribution

to wchodząc w pdp warunkowe tego problemu w prostą całeczkę się raczej nie wbijemy. Jeśli KW odpowiednio dopłaci, to może i pójdę w eleganckie analityczne rozwiązanie.

P.S. Myślę Nihilo, że gdyby pdp zastąpić jednak pdpd, to może i Wilk przychylniej by na to spojrzał.

EdX.: Weźmy bardzo intuicyjny przykład. Jakie jest prawdopodobieństwo (losujemy współczynnik kierunkowy), że prosta przechodząca przez środek okręgu wycina odpowiednią cięciwę?

Chyba każdy czuje, że jest to dokładnie 1.

Edytowane 29 grudnia 2016 przez Astro

[ex nihilo 214]

 

 

Myślę Nihilo, że gdyby pdp zastąpić jednak pdpd, to może i Wilk przychylniej by na to spojrzał.

 

Eee tam, jak kiedyś będzie musiał w czterech zdaniach pięć razy to cholerstwo napisać, to pewnie samo p zostanie

[Jajcenty 314]

 

 

Policz w takim razie dla boku równego dokładnie średnicy okręgu

Tak właśnie to robię.Powinienem napisać: połowa boku. To pierwszy przypadek: 1: [-1.0, 1.0] - czstsc=0,683684

W świetle tej symulacji wychodzi: k/n <> (k*a)/(n*a).

Używam kwadratów double*double. W kwadracie [-1.0, 1,0] jest tyle samo punktów co w ostatnim: [-1024, 1024] przecież uzyskuję go przez bijekcję.

Już widzę tytuły prac: Paradoks Bertranda ujawnia inflację. Okazuje się, że wystarczy rzucić trochę słomy na koło by oszacować prawdopodobieństwo Bertranda, które z kolei jest miarą odległości między węzłami w iloczynie kartezjańskim. Obiecuję, że podzielę się sławą i profitami.

[pogo 102]

Chwilowo nie ogarniam tego co obecnie liczycie...

Ale zauważyłem błąd w mojej propozycji... a nawet dwa:

1. nie eliminuję pokrywających się prostych

2. dla dużych liczb zabraknie nam precyzji w double i zmieniając wartość o najmniejszą dopuszczalną wartość kompletnie nie trafiamy w okrąg, a i na początku pewnie nie trafiliśmy nawet w punkt.

[Jajcenty 314]

Ja liczę: okrąg r=1 ze środkiem w (0,0) na to nakładam kwadraty o wierzchołkach: (a,a), (-a,a), (-a,-a), (a,-a). Z kwadratu losuję dwa punkty (cztery double z przedziału 0,-1 skalowane do (-a,a)) te dwa punkty wyznaczają prostą. Losowanie pomijam jeśli wyznaczona prosta ma mniej niż 2 punkty wspólne z okręgiem.

 

 

 

1. nie eliminuję pokrywających się prostych

I dobrze! realizujemy losowanie ze zwracaniem:D

 

 

2. dla dużych liczb zabraknie nam precyzji w double

Tak, też już odczułem potrzebę sięgnięcia po dłuższe typy, ale 15 cyfr znaczących powinno wystarczyć. No, przynajmniej na razie.  

[Afordancja 57]

ale spodziewacie się innego wyniku czy jak? Tak jak pierwszą myśl rozumiałem, tak teraz nie wiem ku czemu dążycie

[Jajcenty 314]

 

 

ale spodziewacie się innego wyniku czy jak? Tak jak pierwszą myśl rozumiałem, tak teraz nie wiem ku czemu dążycie

Szukamy numerycznej odpowiedzi na pytanie jakie jest prawdopodobieństwo wylosowania cięciwy dłuższej od sqrt(3) w okręgu o promieniu 1. 

[thikim 117]

Cel szczytny ale widzę parę fundamentalnych przeszkód

[Gość Astro]

Przeszkody nie są aż tak fundamentalne. Wystarczy prawidłowo sformułować problem. W zdaniu

Szukamy numerycznej odpowiedzi na pytanie jakie jest prawdopodobieństwo wylosowania cięciwy […]

wystarczy dodać "w zależności od sposobu losowania".

 

Ed. Pogo. Gdyby nie odrzucać, to przy rosnącym polu kwadratu (przy stałym promieniu koła) szansa, że w ogóle ciepniesz w kółko maleje do zera. Jeśli jednak odrzucasz losowanie (nie jest to "losowanie ze zwracaniem" ), to przy rosnącym polu kwadratu dążymy jednak do 1/2 (statystycznie ciepanie z bardzo daleka – przy ustalonym kącie, z którego ciepiemy – odpowiada ciepaniu prostych równoległych, czyli wariant drugi).

Edytowane 30 grudnia 2016 przez Astro