Replace Items in List with Random Items from Dictionary of Lists

I have a list of items that may repeat multiple times. Let us say for example

list = ['a', 'b', 'c', 'd', 'b', 'a', 'c', 'a']

I also have a dictionary of lists that defines multiple values for each key. Suppose:

dict = {'a':[1, 2], 'b':[3, 4], 'c':[5, 6], 'd':[7, 8]}

I want to be able to:

1. randomly select a value from the dictionary where the key is equal to the value in the original list, and

2. have this value be randomly selected at each key occurrence in the list.

I attempted to use Pandas to create a DataFrame from my list and leverage pd.Series.map() to randomly map my dictionary like in the following:

df = pd.DataFrame(list, index = [0,1,2,3,4,5,6,7], columns = ['Letters'])
df['Random_Values'] = df['Letters'].map({k:random.choice(v) for k,v in dict.items()})

Output:

         Letters      Random_Values
    0       a              1
    1       b              3
    2       c              5
    3       d              7
    4       b              3
    5       a              1
    6       c              5
    7       a              1

This code is successful in randomly selecting a value where the key matches, but it currently randomly selects the same value for every key (i.e., all instances of 'a' will always be 1 or 2, not a mixture).

How can I alter this code to randomly select the values each time the key is matched? Any advice appreciate, Pandas not essential -- if you have a better way with just lists I want to hear it!