votazioni e $v$-cammini

[Martino]

Salve!

Non ho ancora trovato una soluzione soddisfacente a questo bel problema:

(*) Esercizio: Ad una votazione vi sono solo due candidati $A$ e $B$, e il numero di votanti è $v$. Non vi sono schede nulle o bianche. Lo spoglio avviene una scheda per volta. Qual è la probabilità che ad ogni momento dello spoglio il candidato $A$ sia in vantaggio sul candidato $B$ o alla pari?

Ho tratto questo esercizio da un esercizio su una dispensa di probabilità di Tiziano Vargiolu. L'esercizio originario pone la stessa domanda premettendo che $A$ riceve $n$ voti, $B$ ne riceve $m$ con $n>m$.

A me piacerebbe trovare un metodo diretto di risolvere il problema (*). Si può facilmente osservare che le votazioni sono rappresentate dai numeri in forma binaria da $0$ a $2^v-1$, con $v$ cifre. Per esempio le otto votazioni possibili con tre votanti sono $000$, $001$, $010$, $011$, $100$, $101$, $110$, $111$. La domanda diventa la seguente: quanti sono i numeri binari tra $0$ e $2^v-1$ che se troncati da sinistra ad ogni momento ammettono almeno tanti uni quanti zeri? Possiamo vedere che nel caso $v=3$ tali numeri sono $101$, $110$ e $111$, quindi sono tre (**). La probabilità cercata è allora $3/8$.

Un altro modo di affrontare la cosa è vedere una votazione come un grafico di una spezzata che parte dall'origine $(0,0)$ e va "su" del vettore $(1,1)$ se il candidato corrente vota $A$, va "giù" di $(1,-1)$ se il candidato corrente vota $B$. Chiamiamo $v$-cammino una spezzata siffatta. In questo modo la domanda diventa: quanti sono i $v$-cammini che non vanno mai sotto l'asse delle ascisse? In realtà potremmo chiamare $s_v(0)$ questo numero, e più in generale $s_v(k)$ il numero di $v$-cammini che non vanno mai sotto la retta di equazione $y=k$.
Questo garantisce un metodo "computazionale" per trovare la soluzione: possiamo osservare infatti che si ha

$s_v(0) = s_{v-1}(-1) = s_{v-2}(-2)+s_{v-2}(0)$.

Infatti un $v$-cammino è soluzione a zero (cioè non va mai sotto zero) esattamente quando comincia andando su e il $(v-1)$-cammino successivo è una soluzione a $-1$; ora se questo $(v-1)$-cammino parte andando giù allora ciò che rimane è un $(v-2)$-cammino soluzione a $0$, altrimenti ciò che rimane è un $(v-2)$-cammino soluzione a $-2$.

Osservando che $s_v(-v)=2^v$ e più in generale $s_v(-k)=2^v$ se $k ge v$, otteniamo allora per esempio che

$s_3(0)=s_2(-1)=s_1(-2)+s_1(0)=2+1=3$, e questo è coerente con (**).
$s_4(0)=s_3(-1)=s_2(-2)+s_2(0)=2^2+s_1(-1)=4+2=6$.

Verosimilmente se uno si mette a fare procedimenti per induzione ottiene un problema di ricorsione da risolvere con una matrice $n xx n$, e questo non è molto simpatico.

Che ne pensate? Avete idee in proposito?

Ciao grazie.

[Umby]

A me piacerebbe trovare un metodo diretto di risolvere il problema (*). Si può facilmente osservare che le votazioni sono rappresentate dai numeri in forma binaria da $0$ a $2^v-1$, con $v$ cifre. Per esempio le otto votazioni possibili con tre votanti sono $000$, $001$, $010$, $011$, $100$, $101$, $110$, $111$. La domanda diventa la seguente: quanti sono i numeri binari tra $0$ e $2^v-1$ che se troncati da sinistra ad ogni momento ammettono più uni che zeri? Possiamo vedere che nel caso $v=3$ tali numeri sono $101$, $110$ e $111$, quindi sono tre (**). La probabilità cercata è allora $3/8$.

Un errorino.
Considerato che le cifre sono dispari (3), è impossibile che il numero degli 0 sia uguale a quelli dei 1. Pertanto per ogni terzetto o vince l'uno o l'altro. Da qui si puo' intuire che la probabilità sia al 50%.
Nel tuo esempio, hai dimenticato $011$

Per cifre pari, invece, bisogna eliminare prima le combinazioni di cifre uguali, e poi sempre dividere al 50%.

[Martino]

Un errorino.
Considerato che le cifre sono dispari (3), è impossibile che il numero degli 0 sia uguale a quelli dei 1. Pertanto per ogni terzetto o vince l'uno o l'altro. Da qui si puo' intuire che la probabilità sia al 50%.

No: non sto chiedendo qual è la probabilità che vinca A, ma che A sia non in svantaggio per tutta la durata della votazione.

Nel tuo esempio, hai dimenticato $011$

Non l'ho dimenticata: nella votazione $011$ dopo il primo voto $A$ è in svantaggio, quindi la votazione $011$ non va considerata.