Wikipedia:Reference desk/Archives/Mathematics/2024 August 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 2

Conditional probability (please check my math)

As measured by recent Polymarket betting odds, Kamala Harris has 45% chance of winning the POTUS election (electoral vote)[1] and 70% chance of winning the popular vote.[2] Let's ignore edge cases like 3rd party candidates and electoral ties. Also, because of how EV's are distributed between red and blue states, while it's theoretically possible for Trump to win the PV and lose the EV, it's unlikely in practice so let's assign that a probability of 0 (polymarket puts it around 1%). So the event "Harris wins EV" is a subset of "Harris wins PV".

Let HP = the event "Harris wins PV", HE = Harris wins EV, TP=Trump wins PV, TE=Trump wins electoral.

So (abusing notation) HP=70% is split into 45% inside HE and 25% in TE. TE itself is 55%.

Does this mean that Pr[HP|TE], the probability of Harris winning the popular vote conditional on Trump winning the electoral vote, is .25/.55 = about .45? Does that sound realistic in terms of recent US politics? I guess we saw it happen in 2016 and in 2008. Not sure about 2012. Obviously whether this possibility is a good one or bad one is subjective and political and is not being asked here. The .45 probability is higher than I would have guessed.

2602:243:2008:8BB0:F494:276C:D59A:C992 (talk) 03:21, 2 August 2024 (UTC)

Your calculation matches mine for the first question in terms of the conditional probability and assuming the assumptions. Whether it's realistic or not is not a math question. Note that Polymarket gives estimated probabilities for all combinations here with P(HP & HE) = .44, P(TP & TE) = .29, P(HP & TE) = .28 and P(TP & HE) = .01, matching your values to within a few percent. I've been following PredictIt myself, which currently gives Harris a 4 point lead over Trump, so there seems to be a fairly large margin of error in these internet odds sites. --RDBury (talk) 04:43, 2 August 2024 (UTC)

Thanks. Can I ask how it is possible that different betting sites can have different odds for the exact same event? Does that create arbitrage potential that should get used immediately? I noticed yesterday that the Iowa Electronic Markets gave a very high probability (like 70%+) of Harris winning the PV and that surprised me, and I wondered why they made no market (as far as I saw) for the EV. I didn't notice til today that Polymarkets also gave around 70% for Harris wins PV (not sure if it is the exact same conditions as IEM)'s. I'm quite surprised by all of this, especially the PV prediction. For the EV, news outlets have been bipolar for weeks (about Biden and more recently Harris) while the prediction markets stayed fairly serene. Now they're swinging more towards Harris and IDK whether anything has substantively changed. 2602:243:2008:8BB0:F494:276C:D59A:C992 (talk) 04:57, 2 August 2024 (UTC)

Suppose two betting markets have substantively different odds for the same event, say $p$ and $q$ expressed as probabilities in the unit interval $[0,1],$ with $p\ll q.$ Given the way bookmakers calculate the pay-off, which guarantees them a margin of profit, betting in one market on the event occurring (at $p$) and at the same time in the other market on it not occurring (at $1{-}q\,$) can only give you a guaranteed net win if $p<{\tfrac {1}{2}}<q.$  --Lambiam 08:22, 2 August 2024 (UTC)

I think you just need p < q (depending on how you distribute the bets) but the difference has to be enough that the profit is more than you'd get just putting your money in the bank and collecting interest. Plus I think that there's a nominal transaction fee with these things. I'm pretty sure it reduces to a minimax problem; find the proportion of bets on E on site a to bets on ~E on site b to maximize the minimum amount you'd win. But I'm also sure plenty of other people have already worked this out and are applying it to equalize the markets. RDBury (talk) 16:46, 2 August 2024 (UTC)

PS. The technical name for this kind of thing is Arbitrage, but it's a bit more complicated than with the usual case with stocks and whatnot. In normal arbitrage you buy X in market A and sell X in market B at a higher amount. In this case we're buying X in market A and not X in market B, then wait until X has been resolved to true or false, which will be months from now. Another factor is that the X in one market may not be exactly the same as the X in the other market, so you have to read the details on each site. For example one site may say "Harris wins" while the other site says "Democrats win". If you don't think it makes a difference then you're not accounting for black swan type events like the presumptive candidate suddenly dropping out of the race. --RDBury (talk) 17:03, 2 August 2024 (UTC)

Probability question

Can someone please help me with this probability question? Say I have 10,000 songs on my iPod, 50 of which are by the Beatles. The iPod can play a sequence of songs at random. Assuming no songs are repeated, what is the probability of two Beatles songs being played consecutively? Thanks, --Viennese Waltz 18:03, 2 August 2024 (UTC)

Just to clarify, do you mean the probability that, if you choose two songs at random, then both will be Beatles songs, or the probability that, if you play all 10,000 songs at random, there will be two consecutive Beatles songs somewhere in the shuffled list? GalacticShoe (talk) 18:11, 2 August 2024 (UTC)

I thought this was a simple question that would not require further elucidation, but apparently not. I don't understand your request for clarification, I'm afraid. Imagine I turn the iPod on and start playing songs at random. What is the probability that two Beatles songs will appear consecutively? I can't be any more specific than that, I'm afraid. --Viennese Waltz 18:14, 2 August 2024 (UTC)

How many songs are you playing total? Are you playing possibly all 10,000, until you hit two consecutive Beatles songs? GalacticShoe (talk) 18:20, 2 August 2024 (UTC)

I have no idea how many I'm playing total. I don't see it as a finite activity. I just want to know the probability that two will pop up consecutively. If the question is unanswerable in this form, please let me know! --Viennese Waltz 18:22, 2 August 2024 (UTC)

Well the problem is that you only have a finite number of songs, so it has to be a finite activity unless you define some behavior for your playlist looping. For example, if the first 10,000 songs are exhausted, then do you reshuffle and play all 10,000 songs again? If that's the case then the probability that you eventually hit two consecutive Beatles songs is essentially 100%. GalacticShoe (talk) 18:25, 2 August 2024 (UTC)

Even if you did manage to get a well-posed version of the problem, I doubt there would be a simple formula. In the ball & urn model, you have m balls in an urn, k of which are colored, and you're selecting n balls without replacement, what is the probability that two colored balls in a row will be chosen? There are well-known formulas for the probability that l of the selected balls will be colored, but they don't say anything about the order in which they appear. Part of the problem may be that "no songs are repeated" is vague. Does it mean a no song is repeated twice in a row or that once a song is played it will never be played again. I think most people here would assume the second meaning, which would imply that the sequence would have to end after all the songs have been played. If it's the first meaning then the sequence could continue forever, but in that case the probability of two consecutive Beatles songs is 1. --RDBury (talk) 19:00, 2 August 2024 (UTC)

Assuming that these are independent events: the odds of a random Beatles song playing is 50:10,000 or 1:200. The consecutive odds is 1:200x200 or 1:40,000. The next step is to subtract the odds they are the same... Modocc (talk) 19:18, 2 August 2024 (UTC)

The odds the same song plays consecutively is 1:10,000x10,000, which is many orders smaller than any two of them. Modocc (talk) 19:31, 2 August 2024 (UTC)

See Probability#Independent_events. Modocc (talk) 19:57, 2 August 2024 (UTC)

The events aren't independent, because they are drawn without replacement. Tito Omburo (talk) 20:04, 2 August 2024 (UTC)

My take is the apps' songs actually repeat (randomly) and from my experience it seems they do, but the OP simply excluded it (as in that doesn't count). Modocc (talk) 20:13, 2 August 2024 (UTC)

Let's assume instead that the app does not repeat any, but plays all of them. The app selects a Beatles song with exactly the same odds initially, and puts every song played into a dustbin. Another similar example should help. Take 10,000 cards with lyrics and randomly assign them to [deal one card to each of the] 10,000 players. With 10,000 non-repetitious events and 50 prized Beatles cards each player has a one in 200 chance of winning a prize card. The chances that any two players (consecutive or not) are assigned these prizes is slightly greater than[differ from] 1:40,000 though because they are no longer independent. Modocc (talk) 22:07, 2 August 2024 (UTC)

I'm not sure how this model relates to the original question. Take the case of an iPod with 3 songs, 2 of which are by the Fab Four. After the first of the 2 Beatle cards has been assigned randomly to one of 3 players, the probability that the player who is randomly selected to receive the second card happens to be the same person is ${\tfrac {1}{3}}.$ Among the possible shuffles of the songs, only those with the non-Beatle song in the middle have no adjacent Beatle songs. The probability of this song randomly being assigned to the middle is ${\tfrac {1}{3}},$ so the likelihood of a random shuffle producing adjacent Beatle songs equals $1-{\tfrac {1}{3}}={\tfrac {2}{3}},$ much higher than the card model suggests.  --Lambiam 14:00, 3 August 2024 (UTC)

I meant one card. It's been 40 years since I aced stats, I'm rusty and I've forgotten some of it. Modocc (talk) 14:46, 3 August 2024 (UTC)

With three independent deals of one card each: 2:3 to win, 2/3x2/3 is 4/9 per pair which is too low. I aced linear algebra too, honors and all that, but I cannot seem to do any of the maths now, but I think the inaccuracy gets smaller with a larger deck because only two consecutive plays are involved.

Modocc (talk) 16:05, 3 August 2024 (UTC)

(ec) One way of interpreting the question is this: given an urn with 10,000 marbles, 9,950 of which are white and 50 of which are black, drawing one marble at a time from the urn, without replacement but putting them neatly in a row in the order in which they were drawn, what is the probability that the final sequence of 10,000 marbles contains somewhere two adjacent marbles that are both black. Generalizing it and taking a combinatorial view, let $P_{n}(m)$ stand for the number of permutations $\sigma (1),\sigma (2),...,\sigma (n)$ of the numbers $\{1,2,...,n\}$ in which no two adjacent elements $\sigma (i)$ and $\sigma (i{+}1)$ are both at most $m,$ where $1\leq m\leq n.$ The answer is then $P_{n}(m)/m!.$ We have $P_{n}(1)=0,P_{n}(2)=2!(n{-}1)!,P_{n}(3)=3!(n{-}2)(n{-}2)!,$ but I don't have a general formula. I suppose, though, that the computation can be made tractable using a (mutual) recurrence relation.  --Lambiam 22:08, 2 August 2024 (UTC)

Experimentally, repeating the process 10,000 times, 2130 runs had adjacent black marbles. So $P_{10000}(50)$ should be in the order of $6\times 10^{35658}.$  --Lambiam 22:53, 2 August 2024 (UTC)

Let n be the number of songs in the playlist, and k the number of beatles songs. Assuming that every song plays exactly once, we count the number of permutations having the property that two beatles songs are played consecutively. First, note that the number of all such configurations is n!, which we write as $n!={\binom {n}{k}}k!(n-k)!$. This can be interpreted as follows: From n songs of the playlist, we first select k positions in ${\binom {n}{k}}$ ways, into which we insert the k beatles songs in k! ways; then the remaining n-k songs are inserted into the remaining n-k slots in (n-k)! ways. We modify this by replacing the binomial coefficient by the quantity $A_{n,k}$, whose definition is the number of ways of selecting k among n objects, at least two of which are adjacent. Now, we have

$A_{n,k}={\binom {n}{k}}-B_{n,k}$

where $B_{n,k}$ is the number of ways of selecting k from the n objects such that none of the k selected are adjacent. We then have $B_{n,k}={\binom {n-k+1}{k}}$. Now the desired probability is just

${\frac {A_{n,k}}{\binom {n}{k}}}.$

When n=10000 and k=50, we get a probability of about 0.21824. Tito Omburo (talk) 16:40, 3 August 2024 (UTC)

The experimentally observed number of 2130 runs out of 10,000 is within 1.3 sigma of the expected value 2182.4, so this is a good agreement.  --Lambiam 19:38, 3 August 2024 (UTC)

Restated as I understand the OP: "what is the probability that two songs played in succession are different Beatles songs?"

I assume that two songs is the minimum they listen to in one session and the odds are small and my mouse iis malfuctioninggg too... Modocc (talk) 16:57, 3 August 2024 (UTC)

The probability is 0.21824 when the entire playlist of 10,000 songs is listened to. There are 5000 (even) + 4999 (even shifted one is odd) consecutive pairs. Supposing their expectation values are equal, that is a probability of about 0.21824/9999 or 2.183e-5 or about 1/45,076. The values are converging then as I thought they would. Modocc (talk) 18:30, 3 August 2024 (UTC)

One can add to the model a variable s, which determines the length of a session. Assuming as before that no song is played more than once, we first insert all songs into a playlist in n! ways. Let S_i denote the event that the number of beatles songs in the first s songs is i. Then, for i from 0 to k, these events partition the probability space. We have $p(S_{i})={\binom {n-k}{s-i}}{\binom {k}{i}}/{\binom {n}{s}}.$ Now, the conditional probability of two consecutive beatles songs is $p(X|S_{i})=1-{\binom {s-i+1}{i}}/{\binom {s}{i}}.$ So we get

$p(X)=\sum _{i=0}^{k}p(X|S_{i})p(S_{i})={\binom {n}{s}}^{-1}\sum _{i=0}^{k}\left(1-{\binom {s-i+1}{i}}/{\binom {s}{i}}\right){\binom {n-k}{s-i}}{\binom {k}{i}}.$

For example, when n=10000, k=50, and s=10000, we get 0.21824; whereas if s=100 (we only listen to 100 songs), we have probability of consecutive beatles songs 0.00241166. Tito Omburo (talk) 20:26, 3 August 2024 (UTC)

For clarity's sake, it's worth noting that when s=n, this simplifies to $1-{n-k+1 \choose k}/{n \choose k}$. GalacticShoe (talk) 20:35, 3 August 2024 (UTC)

Given 2 finite field elements, is it possible to enlarge or decrease the characteristic at the cost of the dimension ?

Simple question : given 2 finite fields elements, is it possible to compute 2 other equivalent elements having a larger or lower characteristics while keeping the same old discrete logarithm between the 2 new elements (through enlarging or decreasing the dimension and without computing the discrete logarithm) ? 82.66.26.199 (talk) 21:48, 2 August 2024 (UTC)

The algebraic notion of characteristic is usually defined for rings (and therefore also for fields). How do you define it for elements of a field?  --Lambiam 08:45, 3 August 2024 (UTC)

Let’s say I have 2 finite fields elements having a discrete logarithm s between them. My aim is to redefine 2 equivalent elements having a larger prime but a lower dimension (with keeping the same discrete logarithm’s) 82.66.26.199 (talk) 10:02, 3 August 2024 (UTC)

If by "prime" you mean the prime number $p$ of the Galois field ${\text{GF}}(p^{k}),$ there is no way to relate its elements algebraically to those of a Galois field with another prime. If you remain in the same field, there is a fair chance that $\log _{(b^{k})}a^{k}=\log _{b}a,$ but the left-hand side may have more solutions in $s$ of the equation ${(b^{k})}^{s}\equiv a^{k}$ than the right-hand side has for the case $k=1.$  --Lambiam 12:58, 3 August 2024 (UTC)

Correct, I was talking about ${\text{GF}}$ where $p$ is a 64 bits large prime and $k$ as a power is even larger. Isn’t it possible to decrease k by increasing p while keeping the same previous m between the 2 equivalent finite field elements ? (without knowing what the discrete logarithm $m$) 2A01:E0A:401:A7C0:9CB:33F3:E8EB:8A5D (talk) 13:35, 3 August 2024 (UTC)

I don't think there is any hope. The algebraic structures of the fields are completely different, so there are no homomorphisms between them.  --Lambiam 14:14, 3 August 2024 (UTC)

Stupid begginer question. Why is pohlig Hellman varients sometimes applicable to elliptic curves but never on Finite fields having a composite dimension ? 2A01:E0A:401:A7C0:F4D5:FA63:12A5:B6B6 (talk) 16:46, 3 August 2024 (UTC)

Pohlig--Hellman is applicable in any finite cyclic group such that the prime factorization of the order is known. It is possible to modify Pohlig--Hellman to any finite abelian group (under the same assumption), but if the rank of the abelian group is greater than one, you need several basis elements rather than just one generator for the discrete log. Notably, the multiplicative group of a finite field is always cyclic, so assuming you know how to factor $p^{n}-1$, you can use regular PH here. For the group of units in a finite ring, you typically need more information. For example, in the units modulo n, where n is composite, you need to be able to compute phi(n) (equivalent to the prime factorization of n), and phi(phi(n)). To answer your original question, if you know that a=b^x (mod p), and have another prime p', just let b' be a primitive root mod p', and define a' as b'^x (mod p'). Tito Omburo (talk) 17:18, 3 August 2024 (UTC)

As I said, I m talking about finite fields of composite dimensions. This excludes $GF(p)$. As far I understand Pohlig Hellman variants don’t apply between elements of ${\text{GF}}(p^{composite\_number})$ unlike ecdlp but why ? 2A01:E0A:401:A7C0:F4D5:FA63:12A5:B6B6 (talk) 19:20, 3 August 2024 (UTC)

It applies if you can determine the prime factorization of p^n-1. The multiplicative group of a finite field is cyclic. Tito Omburo (talk) 20:32, 3 August 2024 (UTC)

It seems to me your are confusing finite fields and finite rings. Finite fields elements of non 1 dimensions are expressed as polynomials like 848848848848487489219*a^4+7378478947844783*a^3+43445998848848898*a^2+87837838383837*a+637837871093836 2A01:E0A:401:A7C0:F4D5:FA63:12A5:B6B6 (talk) 21:46, 3 August 2024 (UTC)

No, I'm not. Any finite (multiplicative) subgroup of *any* field is cyclic. Using PH only requires knowing the prime factorization of the order of the group. In the case of a field with p^n elements, the group of units is cyclic of order is p^n-1. (Of course this may not have many small prime factors, e.g., if n=1 and p is a safe prime). Tito Omburo (talk) 22:37, 3 August 2024 (UTC)

Ok but then how to use the resulting factors on a larger polynomial ? 2A01:E0A:401:A7C0:F4D5:FA63:12A5:B6B6 (talk) 00:12, 4 August 2024 (UTC)

The details of how you do multiplication in the field are irrelevant. PH works if the group multiplication is just considered as a black box. Tito Omburo (talk) 12:13, 4 August 2024 (UTC)

No, I’m meaning once I’ve factored the order, how do I shrink the 2 finite field elements to the lower prime factor in order to solve the ꜰꜰᴅʟᴘ in the lower factor ? For example, in the ᴇᴄᴅʟᴘ this is the matter of dividing each point by the prime factor… Especially if the base prime $p$ is lower than the dimension/power $n$.

Though I admit I would like sample code/pseudocode to understand at that point… 82.66.26.199 (talk) 15:58, 4 August 2024 (UTC)

Suppose you want to solve $g^{x}=y$ where $g\in GF(p^{n})$ is a generator of the group of units. If you have the unique factorization into prime powers $p^{n}-1=q_{1}q_{2}\cdots q_{r}$, then with $q_{i}'=(p^{n}-1)/q_{i}$, the element $g^{q_{i}'}$ generates the group $U(q_{i})$ of $q_{i}$-th roots of unity in $GF(p^{n})$. Then one uses the prime power case of PH to solve $(g^{q_{i}'})^{x}=y^{q_{i}'}$ in $U(q_{i})$. This can be achieved efficiently (provided $q_{i}=p_{i}^{k_{i}}$ is not a large prime) using the Pohlig–Hellman algorithm#Groups of prime-power order. (Basically, you start with $g^{(p^{n}-1)x}=y^{p^{n}-1}$ and successively remove powers of $p_{i}$ inductively. This is a search over $k_{i}p_{i}$ possibilities, so polynomial time in k_i for fixed p_i.) So, we get a solution exponent $x_{i}$ in each group $U(q_{i})$. Finally, let $1=\sum a_{i}q_{i}'$ be an integral combination, and $x=\sum a_{i}q_{i}'x_{i}$ is the solution. Tito Omburo (talk) 17:25, 4 August 2024 (UTC)

So let’s say I want to solve :

$2*z10^{8}+z10^{7}+6*z10^{6}+4*z10^{5}+4*z10^{4}+3*z10^{3}+z10^{2}+6*z10+1$

$4*z10^{8}+z10^{7}+5*z10^{5}+3*z10^{4}+4*z10^{3}+4*z10^{2}+6*z10+2$

in $GF(7^{10})$

How would those 2 elements be written (what does the polynomials would like) in order to solve the subdiscrete log in 2801 ? 82.66.26.199 (talk) 22:28, 4 August 2024 (UTC)

First raise them both to the power (7^10-1)/2801 in the field. And then check which among 2801 possibilities you have g^x=y. Tito Omburo (talk) 22:37, 4 August 2024 (UTC)

So still 10 polynomials elements per finite fields for just 2801 ? 2A01:E0A:401:A7C0:F4D5:FA63:12A5:B6B6 (talk) 01:02, 5 August 2024 (UTC)