Meddelande

Du befinner dig just nu på en äldre version av Pluggakuten, gamla.pluggakuten.se. Nya Pluggakuten lanserades den 6 februari 2017 och du finner forumet på www.pluggakuten.se.

På gamla.pluggakuten.se kan du fortfarande läsa frågorna och svaren som ställts, men du kan inte skapa ett nytt konto eller nya trådar. Är du redan medlem kan du däremot fortfarande logga in och svara i befintliga trådar. Nya frågor och nytt konto skapar du på det nya forumet, välkommen dit!

[Kluring] Förväntat antal maxima

Russell
Moderator

Offline

Registrerad: 2013-08-22
Inlägg: 2608

[Kluring] Förväntat antal maxima

I en slumpmässig permutation av talen 1, 2, ..., n (där n>1) kallar vi ett tal k för ett lokalt maximum om talet inte står intill ett större tal—dvs k är ett lokalt maximum omm det inte finns något tal m direkt bredvid k sådant att m>k.

Vad är det förväntade antalet lokala maxima?


The road to wisdom?—Well, it's plain and simple to express:
Err and err and err again, but less and less and less.
 
albiki
Medlem

Offline

Registrerad: 2008-05-25
Inlägg: 6403

Re: [Kluring] Förväntat antal maxima

Ett steg på vägen (kanske)?

Låt slumpvariabeln X_k = 1 om talet på plats nummer k är ett lokalt maximum; i annat fall är X_k = 0. Det sökta väntevärdet är lika med summan

    E(X_1) + ... + E(X_n) = P(X_1 = 1) + ... + P(X_n = 1).

Notera att slumpvariablerna är beroende.

 
JohanB
Medlem

Offline

Registrerad: 2014-05-16
Inlägg: 739

Re: [Kluring] Förväntat antal maxima

Trillar inte det ut rätt omedelbart från albikis argument? Slumpvariablerna må vara beroende, men deras väntevärde är inte det. Väntevärdena är rätt lätta att räkna ut (man får se upp för randfallen).

 
Russell
Moderator

Offline

Registrerad: 2013-08-22
Inlägg: 2608

Re: [Kluring] Förväntat antal maxima

Någon som har lust att snickra ihop en hel lösning...? Annars gör jag det så småningom.


The road to wisdom?—Well, it's plain and simple to express:
Err and err and err again, but less and less and less.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: [Kluring] Förväntat antal maxima

Om a_n är förväntat antal max så gäller a_(n+1)=a_n + 1/3 varav a_n= (n+2)/3. Rekursionen följer om man ser på dom tre sista talen i permutationen: ...,x,y,z. Av deras sex permutationer är det två där z höjer antalet max med 1.

 
Russell
Moderator

Offline

Registrerad: 2013-08-22
Inlägg: 2608

Re: [Kluring] Förväntat antal maxima

Jag är inte säker på hur du kommer fram till (n+2)/3, eller om jag missförstår dig. Om väntevärdet för n tal var (n+2)/3 så skulle väntevärdet för n=2 vara 4/3, men i det fallet kan vi bara få exakt 1 lokalt maximum så väntevärdet där måste vara 1. Men hur som helst så är (n+2)/3 jävligt nära rätt svar.

Här är en lösning:

Spoiler (Klicka för att visa):

Vi börjar precis som albiki med indikatorvariabler LaTeX ekvation där LaTeX ekvation om siffran på plats LaTeX ekvation är ett lokalt maximum och LaTeX ekvation annars. För LaTeX ekvation så är väntevärdet LaTeX ekvation, för av talen LaTeX ekvation så är det en tredjedels chans att det största talet står i mitten (albiki noterade mycket riktigt beroendet här—annars kan man förledas att tänka att sannolikheten blir 1/4). För LaTeX ekvation och LaTeX ekvation blir väntevärdena 1/2 eftersom de bara har en granne vardera.
    Det förväntade antalet lokala maxima är alltså det förväntade värdet av summan av dessa indikatorvariabler, och eftersom väntevärden är linjära så har vi att väntevärdet för summan är summan av väntevärdena:

LaTeX ekvation

Det här är för övrigt en uppgift från den ökänt svåra Putnam-tävlingen. Maxpoängen där är 120 men medianen är ofta 0 poäng. :p


The road to wisdom?—Well, it's plain and simple to express:
Err and err and err again, but less and less and less.
 
Smutsmunnen
Medlem

Offline

Registrerad: 2010-04-18
Inlägg: 868

Re: [Kluring] Förväntat antal maxima

Det här är snarare en variation på russels lösning än en ny, men möjligen kan någon tycka det är intressant. Antag först att vi istället för att placera talen 1 till n längs en linje placerar dem runt en cirkel. Sedan definierar vi ett maximum som ett tal större än sina grannar, ett minimum som ett tal mindre än sina grannar och ett medium som ett tal som är större än en granne och mindre än en granne.

Antag nu att på tre positioner bredvid varandra har vi talen a<b<c. Det finns sex olika permutationer, två av dem gör den mittersta positionen till ett maximum, två till ett minimum och två till ett medium. Det förväntade antalet för ar och en av de tre möjligheterna är 1/3 per position och n/3 för alla n positioner.

Nu kan vi betrakta linjen som en cirkel som klippts av mellan position 1 och position n. På dessa positioner kan vi alltså inte ha ett medium och det förväntade antalet medium faller därför med 2/3. I gengäld ökar det förväntade antalet maxima och minima med 1/3 vardera.  Övriga positioner förblir oförändrade så det i slutändan får vi (n+1)/3 maxima och minima och (n-2)/3 medium.

Senast redigerat av Smutsmunnen (2016-04-22 18:07)

 


Sidfot

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson

Powered by Mattecentrum
 |  Denna sida använder cookies |  Kontakta oss |  Feedback |